백준
[백준] 1562. 계단 수 - Python
[Gold I] https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스킹을 이용한 DP 문제. 기본적인 아이디어는 2차원 DP를 생각하면 쉽게 떠올릴 수 있는데, dp[N][i] 일 때, dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1] 과 같은 점화식(i==0, i==9 예외) 으로 풀이할 수 있다. 다만 위의 경우는 0부터 9까지 숫자가 모두 등장하는 계단 수 라는 조건을 무시했을 때의 풀이법. 이 문제는 위 조건을 만족하는 수의 개수만을 구해야 하므로, 기존 풀이를 응용하여 풀이할 수 있다. 기존 2차원 배열이 아닌, 3차원 배열로 선..
[백준] 13460. 구슬 탈출 2 - Python
[Gold I] https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 조금 복잡했던 BFS 시뮬레이션 문제. 이동 시 빨간 구슬과 파란 구슬이 겹쳤을 때, 각각의 이동 횟수를 계산하여 처리하는 방식이 키포인트. BFS의 visited 처리는 빨간 구슬과 파란 구슬의 좌표를 이용한다. 몇 번째 이동인 지는 visited로 확인할 필요 없음. 자세한 풀이는 코드의 주석을 참고하여 확인하면 쉽게 이해..
[백준] 9328. 열쇠 - Python
[Gold I] https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 시간초과와 메모리 초과를 몇 번 받다가, 이리저리 최적화하여 Accepted 받은 문제. 처음엔 [백준] 1194. 달이 차오른다, 가자. 와 비슷해 보여, 비슷하게 Bitmasking을 이용해 풀이할까 생각했지만, 가능한 열쇠의 개수가 26개이므로, 2^26의 경우의 수를 모두 저장할 수는 없어, 다른 방법을 생각했다. 우선 그래프(지도)의 형태를 입력받을 때, 겉을 빈 공간('..
[백준] 17387. 선분 교차 2 - Python
[Gold II] https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 작년 2학기 알고리즘 수업때 배웠던 CCW 알고리즘을 이용한 선분 교차 판별 문제. 그 때 강의 교안을 다시 보면서 기억을 되살리며 풀었다. CCW의 곱이 둘 다 0일 때, 선분이 포개어져 있는 경우 교차하는 것으로 판단한다. 이 케이스만 주의하면 나머지는 알고리즘을 그대로 적용하여 쉬이 풀이할 수 있다. AC. x1, y1, x2, y2 = map(int, input().split()) x3, y3, x4, y4 = map(int,..
[백준] 1719. 택배 - Python
[Gold III] https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 풀이 모든 노드에서 시작하여, 다른 모든 노드로까지의 최단 경로를 구해야 하는 문제이므로, 플로이드-와샬(Floyd-Warshall) 로 풀이할까- 생각했다. 그러나 음의 가중치를 가지는 간선이 존재하지 않았고, 플로이드-와샬의 Time Complexity는 O(V^3), 다익스트라로 풀이한다면 O(E*VlogV) 정도이기 때문에, 다익스트라로 풀이하기로 하였다. 모든 노..
[백준] 1194. 달이 차오른다, 가자. - Python
[Gold I] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 기본적으로 상하좌우 4방향으로 뻗어 나가는 흔한 BFS 형식으로 풀이하면 된다. 그런데 이제 비트마스킹을 곁들인. 열쇠와 문이 없다면, 각 row와 column, 그러니까 아래 코드에서는 visited[r][c] 2차원 배열만 채우며 진행하면 될 것이다. 그러나 열쇠가 있으므로.. 예를 들어, a열쇠를 가지고 (0,0)에 도달한 경우와, a열쇠가..
[백준] 1948. 임계경로 - Python
[Platinum V] https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 풀이 1 (오답) 문제를 보자마자, 그냥 크게 생각하지 않고 DFS(혹은 BFS..?) 느낌? 그냥 그래프 탐색으로 풀어본 결과. MLE가 나오긴 했지만, 다시 보니 지난 거리 개수를 셀 때 중복을 허용했기 때문에 틀린 코드다. MLE. (메모리 초과) / WA. from collections import deque n = int(input()) ..
[백준] 3584. 가장 가까운 공통 조상 - Python
[Gold IV] https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 처음 보는 LCA (Lowest Common Ancestor) 문제. DFS를 통해 Root 노드부터 각 노드의 깊이(depth)를 저장하고, 입력된 두 노드의 depth를 맞춘 후, 공통 조상이 나올 때까지 그대로 거슬러 올라가는 식으로 해결하였다. 이 풀이의 경우 O(N)의 Time Complexity로 해결한 경우이며..