나를 위한 기록

https://www.acmicpc.net/problem/16639 문제 접근 파일합치기 문제와 비슷한 방식으로 DP를 통해 해결하려고 시도했다. 내가 생각해내지 못했던 것은 연산자에 대한 인덱스 처리와 연산자에 따라 최솟값을 이용해서 최댓값을 만들 수 있는 경우가 있다는 것을 놓치고 있었고 검색을 통하여 힌트를 얻어 문제를 해결했다. 풀이 과정 문제를 푸는 핵심 개념은 Bottom-Up 방식으로 수식을 작은 범위부터 큰 범위로 확장해나가면서 계산하면 된다. 각 구간별 최댓값을 DP 배열에 저장하면서 구간을 확장하면 결국 DP[n][n]에 우리가 구하고자 하는 값이 저장될 것이다. 위의 그림을 코드로 표현하면 아래와 같을 것이다. n은 전체 수식에서 피연산자 갯수를 구한 것이고 (수식의 길이 + 1) /..

https://www.acmicpc.net/problem/17182 문제 접근 이 문제는 플로이드 워셜 + 순열로 해결해야 하는 문제이다. 출발하는 행성에서 모든 행성을 탐사하는데 걸리는 시간을 구해야 하므로, 최단경로를 구할 때 출발 행성에서 다른 행성까지의 최단경로를 구하는 다익스트라나 밸만포드보다는 모든 행성 간 최단경로를 구할 수 있는 플로이드 워셜 알고리즘을 이용해야 한다. 모든 행성 간 최단경로를 구했으면 방문하는 순서를 결정해야 한다. permutations 함수를 통해 출발 행성을 제외한 나머지 행성들의 순열을 구하고 거리의 합이 가장 작은 경우를 구해주면 된다. 풀이 과정 1. 플로이드 워셜을 통한 모든 정점 간 최단경로 계산 for k in range(N): for i in range(..

https://www.acmicpc.net/problem/2573 문제 접근 오랜만에 정답을 안보고 푼 문제이다. BFS를 이용한 구현문제였다. BFS를 통해 4방향에 인접한 빙산을 탐색하여 빙산의 그룹이 분리되었는지 확인하고 iceberg에 저장된 빙산들을 4방향에 인접한 물의 갯수만큼 빙산의 높이를 빼주면 된다. 풀이 과정 1. 빙산이 분리되었는지 확인 빙산의 위치에서 BFS를 통해 방문한 위치의 갯수와 미리 iceberg 배열에 저장해두었던 빙산의 위치의 갯수가 같으면 분리되지 않은 것이고 다르면 분리된 것이다. 하나의 빙산의 위치에서 BFS를 통해 탐색하면 모든 빙산을 방문할 것이기 때문에 위치의 갯수가 다르면 분리된 것으로 판단한다. def bfs(x, y): visited = [[False] ..

https://www.acmicpc.net/problem/11657 문제 접근 시작 노드에서 각 노드별로 최단경로를 구하는 문제이다. 최단경로를 구하는 알고리즘은 다익스트라와 벨만포드가 있다. 이 문제는 Edge의 음수 가중치가 존재하므로 다익스트라를 이용해서 최단경로를 구하면 제대로된 거리를 구할 수 없다. 따라서 음수 가중치가 있어도 최적해를 찾을 수 있는 벨만포드 알고리즘을 이용해서 문제를 해결해야 한다. 풀이 과정 벨만포드 알고리즘 순서 출발 노드 설정 dist 배열 초기화 모든 간선에 대해 각 간선을 거쳐 다른 노드로 가는 최단 거리 갱신 -> (정점의 갯수 - 1)번 수행 3번이 끝난 후에도 최단 거리가 갱신된다면 음수 사이클이 존재하는 것이다. 이 과정을 코드로 구현해보자. def bellm..

https://www.acmicpc.net/problem/1717 문제 접근 분리집합 문제이다. 분리집합문제는 Union-Find를 이용하여 해결할 수 있다. 이 문제는 문제 입력에 따라 Union연산을 하거나 같은 집합인지 확인하면 되는 문제였다. 주의할 점은 find 함수 작성할 때 최적화를 하지 않으면 시간 초과가 발생할 수 있다. 풀이 과정 1. 합집합 연산 def union(u, v): u = find(u) v = find(v) if u < v: parent[v] = u else: parent[u] = v 2. 최상위 부모 검색 최상위 부모를 검색할 때 루트가 제대로 저장되지 않은 경우는 검색하면서 다시 저장해주어야 시간 초과를 해결할 수 있다. 그냥 재귀를 호출하여 최상위 부모를 검색하면 시간..

https://www.acmicpc.net/problem/13913 문제 접근 BFS를 이용하여 목적지에 도달할 때까지 계속해서 탐색하는 방식으로 문제를 접근했다. 무조건 current - 1, current + 1, current * 2에 해당하는 좌표와 지금까지의 경로를 같이 큐에 삽입하도록 했는데 메모리 초과가 발생했다. 이미 방문한 위치를 또 방문할 뿐더러 중복되는 모든 경로까지 큐에 삽입하게 되기 때문이다. 따라서 dist배열을 통해 이미 방문한 위치를 체크하면서 해당 위치까지 도달하는데 걸리는 시간을 같이 저장했다. 또 경로를 트래킹하기 위해서 foot_print배열에 해당 위치에 이전 위치를 저장하도록 문제를 해결했다. 틀린 코드 ... def bfs(): q = deque() q.appen..

https://www.acmicpc.net/problem/11779 문제 접근 다익스트라를 이용한 최단경로를 찾는 문제이다. 풀이 과정 다익스트라 알고리즘을 통해 start와 end 사이의 최단경로를 구하도록 한다. 경로도 같이 저장해야 하므로 dist배열을 갱신할 때 부모 노드를 parent배열에 저장하도록 한다. 정답 코드 """ 백준 11779번 최소비용 구하기2 """ import sys import heapq def dijkstra(): dist[start] = 0 queue = [] heapq.heappush(queue, [dist[start], start]) while queue: cost, node = heapq.heappop(queue) if dist[node] < cost: contin..

https://www.acmicpc.net/problem/2252 문제 접근 위상 정렬(Topological Sorting)을 이용하는 문제이다. 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행할 때 사용할 수 있는 알고리즘이다. 위상 정렬에 대한 자세한 설명은 풀이 과정을 통해 다루도록 한다. 풀이 과정 1. 위상 정렬이란? -> 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 위상 정렬은 다음의 조건을 만족해야 적용될 수 있다. 그래프는 방향성을 가진 그래프여야 한다. 그래프에 Cycle이 없어야 한다. 위 두 조건을 한 문장으로 표현하면 위상 정렬은 DAG(Directed Acyclic Graph)인 경우에만 적용이 가능하다는 것이다. 2. ..

https://www.acmicpc.net/problem/3584 문제 접근 처음에는 DFS를 통해 자식 노드를 모두 찾으면 해당 노드 번호를 반환하도록 구현했다. 따라서 부모 노드의 자식을 저장하도록 트리를 만들었다. 하지만 결과는... 사실 노드의 갯수가 최대 10000개이기 때문에 메모리 초과가 나올 줄 몰랐다... 고민 끝에 최근 풀었던 Union-Find 문제를 풀었던 기억을 되살려 트리를 만들 때 부모의 자식을 저장하는 것이 아니라 자식의 부모를 저장하도록 하여 문제를 해결하였다. DFS를 이용할 때는 탐색하지 않아도 될 노드를 탐색했는데 트리를 저장하는 방식을 바꾸니까 찾고자 하는 자식의 노드만 탐색하므로 시간 복잡도도 O(logN)으로 해결할 수 있었다. 풀이 과정 문제 풀이 과정을 그림으..

https://www.acmicpc.net/problem/14725 문제 접근 트리를 생성하면 풀 수 있는 문제이다. 트리를 만들 때 딕셔너리나 리스트를 이용해서 만들 수 있는데 이 문제는 노드의 값이 정수형이 아닌 문자열이므로 Dictionary를 이용하여 트리를 생성하도록 한다. 풀이 과정 1. 트리를 생성한다. 주어진 입력에서 depth별 노드의 정보를 받을 수 있다. 재귀를 통해 입력받은 리스트를 하나씩 트리에 추가한다. def add_tree(tree, nodes): if not nodes: return if nodes[0] not in tree: tree[nodes[0]] = {} add_tree(tree[nodes[0]], nodes[1:]) 2. 트리를 출력한다. 트리를 출력할 때 DFS를..