백준알고리즘
-
[BOJ - 17070] 파이프 옮기기 1백준알고리즘 2020. 5. 7. 23:07
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net DP,DFS,BFS 그 어떤것으로 해도 C/C++일때 배열의 크기가 작아서 AC할 수 있을것같다. 근데 DFS로 짜면 시간이..
-
[BOJ - 14503] 로봇 청소기(재)백준알고리즘 2020. 5. 1. 06:02
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 이번엔 다른 STL쓰지않고 stdio만 써서 했다. 최대한 코드 줄수를 줄일수있을만큼 줄여보았고, 문제의 지시를 최대한 그대로 이..
-
[BOJ - 1240] 노드 사이의 거리백준알고리즘 2020. 5. 1. 01:27
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 이 문제는 풀이가 여러개 있을텐데 BFS, 다익스트라, 부모를 찾아가게 하는 DFS응용풀이 근데 그냥 그중에서 다익스트라 풀이를 써서 문제를 풀었다. 별로 설명할것은 없고, N,M의 범위가 상당히 작은편이라 그냥 케이스마다 다익스트라를 돌려도 시간초과가 절대 나지 않는 문제다.
-
[BOJ - 16236] 아기 상어(재탕)백준알고리즘 2020. 5. 1. 01:22
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 이전에 작성했던것 보다 훨씬 더 깔끔하게 작성했다. 쓸데없는 코드는 최대한 지양하면서 필요한 코드만 작성했는데 일단 문제를 제대로 ..
-
[BOJ - 1647] 도시 분할 계획 ( 순수 C언어 )백준알고리즘 2020. 4. 27. 22:03
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다. www.acmicpc.net 문제를 제대로 읽고 그림을 그려보면서 이해해야 조금 편할것 같다는 생각을 했다. 지문에는 "마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록..
-
[BOJ - 11812] K진 트리백준알고리즘 2020. 4. 26. 09:14
https://www.acmicpc.net/problem/11812 11812번: K진 트리 문제 각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다. 트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다. 아래 그림은 노드 9개로 이루어져 있는 3진 트리이다. 노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 www.acmicpc.net 아 .. 열심히 작성된 글이 지워져서 처음부터 다시쓴다. 문제 자체의 숫자 범위가 굉장히 크기때문에 일반적인 DFS를 쓰기에는 무리라..
-
[BOJ - 5719] 거의 최단 경로(Python,파이썬)백준알고리즘 2020. 4. 23. 01:28
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 전에 C++로 풀어보았던 문제다. C++로 했을때는 중복을 허락하는 BFS를 두번 써서 해결을 했던것으로 기억한다. 그런데, Py..
-
[BOJ - 16234] 인구 이동(Python,파이썬)백준알고리즘 2020. 4. 23. 01:23
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 굉장히 간단한 시뮬레이션 문제다. 일단 조건 제시 값들이 적당히 작기 때문에 시간 복잡도에서 터지지 않을것이란 확신이 있었고 그렇기에..