본문 바로가기

Algorithm/Baekjoon117

1774. 우주신과의 교감 (Python) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 최소 신장 트리(MST)를 이용하여 해결하는 문제이다. MST를 만드는 방법에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 자세한건 검색을 통해 알아보자. 간단하게 설명하면 다음과 같다. * 크루스칼 알고리즘 : 모든 간선을 길이에 따라 오름차순으로 정렬하여 크기가 작은 간선부터 사용한다. 간선을 사용했을 때 사이클이 발생하지 않는지를 체크한다. * 프림 알고리즘 : 시작 정점을 기준으로 선택할 수 있는 간선 중 가장 크기가 작은.. 2022. 6. 10.
17071. 숨바꼭질 5 (Python) 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 시간 제한이 0.25초로 빡빡하기 때문에 일반적인 방문체크로는 정답을 구할 수 없다. 이때 필요한 것이 짝수초와 홀수초로 나누어 방문 체크를 하는 것이다. 예를 들어 수빈이가 10의 위치에 2초에 도착했다고 가정해보자. 수빈이는 X-1이나 X+1을 이동할 수 있다. 즉, 10에서 왼쪽으로 한 번 이동하고 오른쪽으로 한 번 이동하는 방식으로 다시 같은 위치로 이동할 수 있다. 10의 위치에 2 + 2초, 2 + 4초, 2 .. 2022. 6. 9.
17136. 색종이 붙이기 (Python) https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 1이 적힌 칸에서 1x1 크기의 색종이부터 5x5 크기의 색종이까지 붙일 수 있는지를 체크한다. 색종이를 붙이고 나면 색종이로 덮어진 부분을 체크해주고 다음 1이 적힌 칸으로 넘어가서 색종이를 붙일 수 있는지를 체크하는 과정을 반복한다. 모든 1이 적힌 칸을 색종이로 덮고 나면 사용한 색종이의 개수들을 비교하여 그 중 최소 개수를 기록하면 된다. 코드 # size * size 색종이.. 2022. 6. 7.
2240. 자두나무 (Python) 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 3차원 dp 배열을 이용하여 문제를 해결할 수 있다. 3차원 dp 정보는 다음과 같다. dp[t][w][p] : t시간에 w번 이동하여 p번 나무에 있을 때 받을 수 있는 자두의 최대 개수 처음에는 1번 자두 나무에 위치하므로 이에 대하여 따로 처리해준다. 만약 처음으로 떨어지는 자두의 위치가 1일 경우에는 이동하지 않고 자두를 받을 수 있으므로 dp[1][0][1]을 1로 설정한다. 처음으로 떨어지는 자두의 위치가 2일 경우에는 한 번 이동해야 받을 수 있으므로 .. 2022. 6. 6.
2141. 우체국 (Python) 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 풀이 그리디에 해당하는 문제인데 모르겠어서 다른 사람의 풀이를 참고했다. 우체국의 위치를 구하려면 우체국을 세운 지점 기준으로 왼쪽에 위치한 사람의 숫자와 오른쪽에 위치한 사람의 숫자의 차가 최소가 되는 지점을 찾아야 한다. 먼저 입력으로 받은 마을 위치를 기준으로 오름차순 정렬한 후 처음부터 끝까지 우체국을 세워가며 왼쪽과 오른쪽 사람의 수를 누적합을 사용하여 체크한다. 두 누적.. 2022. 6. 4.
10282. 해킹 (Python) 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 다익스트라를 사용하여 문제를 해결할 수 있다. 입력으로 주어지는 의존성은 그래프에서 방향성이 있는 간선이라고 생각하면 된다. 예를 들어 1, 2, 3이라는 의존성이 주어지면 2번에서 1번으로 가는 비용이 3인 간선인 것이다. 예제에서 주어진 케이스 중 두 번째 케이스를 보자. 이를 그래프로 표현하면 다음과 같다. 처음에 1번 컴퓨터가 감염되어있고 의존성에 따라 다른 컴퓨터로 전염되기 시작한다. 먼저 1번 컴퓨터에서 2번 컴퓨터로 전염되는데 2초의 시간이 걸린다... 2022. 6. 3.