곰탱이의 공부정리

https://www.acmicpc.net/problem/17070 이 문제는 파이프를 정해진 방식대로 밀어서 끝까지 가는 경로가 몇 개인지 구하는 문제이다. 이 문제에서 파이프는 3가지 상태를 가지고 있다. 가로,세로,대각선이다. 그리고 이 세가지 상태에 따라 다음칸으로 움직일 수 있는 방법이 나뉜다. 가로의 경우에는 가로로 한칸 대각선으로 한칸, 세로의 경우에는 세로로 한칸 대각선으로 한칸, 대각선의 경우에는 가로로,세로로,대각선으로 한칸 움직일 수 있다. 이렇게 움직일 때 꼭 비어있어야 하는 칸들은 아래와 같다.우리는 시작이 있고 끝으로 가는 경우의 수란 점에서 그래프 경로 찾기라는 걸 알게된다. 그렇다면 경로 찾기하면 BFS 아님 DFS인 것을 알 수 있다. 그런데 이 문제의 추가시간이 엄격한걸..

https://www.acmicpc.net/problem/2206  이 문제는 벽을 한번만 뚫을 수 있을 때, 0,0에서 시작해서 N-1,M-1까지의 최단거리를 구하는 문제이다.  이 문제는 간단한 BFS로 풀 수 있을것만 같았지만, 필자는 나름 헤맸다. 맨 처음의 생각은 그래프 위를 지나가는 어떠한 인자가 벽을 뚫을 수 있는가,거리는 얼마인가를 들고 다니면서 계산을 하는 것이었다. 하지만 이렇게 한다면 방문처리나 거리 같은 것을 일일이 큐에 저장해야 하기에 메모리에 부담이 된다. 그렇기에 아예 방문처리와 거리를 하나로 처리해버리고, 방문 리스트를 3차원으로 만들어 벽을 뚫었을 때, 벽을 안 뚫었을 때를 따로 기록하고, BFS의 특징 상 가장 먼저 N-1,M-1에 도착하면 그것이 최소거리이기에 바로 리턴..

https://www.acmicpc.net/problem/1865  이 문제는 양방향 도로와 단방향 웜홀(시간이 뒤로감) 이 주어지고 이 때 음의 사이클이 존재하는지 물어보는 문제이다. 음의 사이클이 있는지를 알아내려면 벨만-포드 알고리즘을 쓰는 것이 제격이다.   벨만 - 포드 알고리즘은 그래프의 노드의 개수만큼 반복하며, 다익스트라 알고리즘처럼 경유하는 경우가 더 짧을 경우 계속해서 갱신하는 방식이다. 얼핏보면 쓸데 없는 계산을 더하는 것처럼 보이지만, 이 알고리즘의 장점은 이미 그래프의 노드의 개수만큼 반복하여 최적의 거리를 구했다고 생각했을때, 한번 더 돌려서 이때 최적경로가 갱신된다면, 음의 사이클이 생긴 것이라는 것을 알아챌 수 있단 점이다.   필자는 본디 처음엔 거리 리스트를 math.in..

https://www.acmicpc.net/problem/1238  이 문제는 단방향 엣지가 주어진 그래프에서, 모든 노드에서 특정 노드로  최단거리로 왕복했을 때의 최댓값을 구하는 문제이다.   이 문제는 다익스트라 알고리즘을 사용하면 간편하게 풀 수 있다. 다만 오고 갈 때가 다르기에, 필자는 올때의 그래프, 갈때의 그래프를 따로 만들고 시작점을 X로 하여 모든 노드로 가는 최단거리를 구하고 각 인덱스에서 더해서 최댓값을 구했다. X를 도착으로 하든 시작으로 하든, 어차피 그래프만 거꾸로 뒤집으면 X를 시작으로 하여, 오고가는 것을 다 커버할 수 있다.import sysinput = sys.stdin.readlineimport mathimport heapqdef dijkstra(start,graph)..

https://www.acmicpc.net/problem/11404  이 문제는 말 그대로 플로이드 워셜 알고리즘을 구현하는 문제이다. 플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점으로 향하는 최단거리를 구할 때 사용한다. 이 알고리즘은 중간으로 경유하는 점들을 하나하나 검사해, 시작과 끝의 최단거리를 구한다. 그렇기에 시간복잡도는 O(n^3)이다.   이 때 유의할 점이, 가장 바깥쪽의 for문에는 중간 경유하는 점을 넣어야 한단 점이다. 만약 그렇지 않다면, 완벽히 계산되지 않은채로, 어느 정점에서는 시작과 끝이 끝나버리고, 새로운 최단거리가 발견되어도 갱신하지 못하기 때문이다. 그렇기에 시작과 끝의 계산을 최대한 뒤로 미루어서 항상 갱신할 수 있도록 해야한다. import sysinput ..

https://www.acmicpc.net/problem/1167  이 문제는 트리에서 가장 먼 두 정점 사이의 거리를 구하는 문제이다.   트리에서 가장 긴 지름은 무조건 말단 노드와 말단 노드 사이일 것이다. 그리고 임의의 노드에서 가장 먼 노드가 그 지름의 말단 노드일 것이다. 자세한 증명은 https://blog.myungwoo.kr/112 이 블로그를 참고하길 바란다.  아무튼 결국 우리는 임의의 노드(루트노드)에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구하면 된다. import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def find(cur_n,cur_w): for next_w,next_n in tree[cur_..

https://www.acmicpc.net/problem/9663  이 문제는 전통적인 알고리즘 문제이다. 이 문제를 푸는 법은 결국엔 하나하나 다 놔봐서 되는 경우의 수를 찾는 백트랙킹으로 풀어야한다.  먼저 우리는 1행을 기준으로 아래행으로 나아가면서 퀸을 하나하나 놔 볼것이다. 근데 퀸이 서로를 겨누게 두면 안 되기에, 다른 퀸과 같은행,같은열,같은 대각선에 두면 안된다. 같은행은 우리가 행을 내려갈 것이므로 크게 신경 쓰지 않아도 되고, 같은 열은 그냥 검사하면 되고, 같은 대각선은 체스 보드판을 일종의 좌표계로 보고 x+y=t, x-y=t에 걸리는지 아닌지를 검사하면 된다.  본래 필자는 이를 2차원 배열로 직관적으로 풀려했으나, 0,1을 하나하나 건드려야 한다는점, 메모리가 부족하단 점 등 때..

https://www.acmicpc.net/problem/1753  이 문제는 간편하게 시작지점에서 다른 모든 지점으로의 최소경로의 길이를 구하는 문제이다.   이 문제는 그냥 데이크스트라 알고리즘을 충실히 구현하면 풀린다. 데이크스트라 알고리즘에 관해서는 https://jangbearbio.tistory.com/102 이 글에서 자세히 다뤘으므로, 이 글에서는 자세히는 다루지 않겠다.  이 문제를 풀면서, 필자는 무의식적으로 데이크스트라 알고리즘을 구현할 때 큐를 말그대로 덱으로 하여, bfs의 큐처럼 사용했지만, 무게를 기준으로 최솟값이 항상 앞으로 튀어나오게 하는 heapq 자료형을 사용하는 것이 시간적이나 알고리즘적으로 더 낫다는 것을 기억하게 되었다. 가장 작은 무게가 먼저 나오기에, 같은 경로..

https://www.acmicpc.net/problem/15686  치킨거리란 집과 가장 가까운 치킨집 사이의 거리이다. 그리고 도시의 치킨거리란 모든 집의 치킨거리를 합한 것이다. 우리가 주어진 치킨집 중 M개의 치킨집만을 남겨야 할 때, 도시의 치킨거리가 최소가 되게하는 경우의 도시의 치킨거리를 출력하는 문제이다. 이 때 0은 빈곳, 1은 집, 2는 치킨 집으로 인풋이 주어진다.  이 문제는 딱 봐도 복잡한 형식이다. 그렇기에 사실 마땅한 알고리즘보단 하나하나 차분히 나누어 충실히 구현하여 문제를 풀어야한다. 먼저 우리는 집과 치킨집 사이의 치킨거리를 구해서 2d 배열로 저장해놓을 필요가 있다. 그래야 치킨집을 하나씩 없애보며 도시의 치킨거리를 구할 수 있다. 그리고 M개가 될 때까지 치킨집들을 없..

https://www.acmicpc.net/problem/12865  이 문제는 평범한 0-1 배낭 문제이다. 0-1 배낭 문제란, 각 물건마다 가치와 무게가 주어지고 무계 한도가 있는 배낭에 물건을 넣을 때 최대의 가치를 구하는 문제이다.  이 문제는 여러 가지 알고리즘으로 풀 수 있지만, 필자는 통상적인 다이나믹 프로그래밍 알고리즘으로 풀기로 했다. 먼저 우리가 어떤 물건 n을 넣어 최대의 가치를 구하고자 한다면, 그 물건n을 빼고 나머지 물건들의 최적해를 구하고, 그 최적해에 n을 넣느냐 마느냐 중 무엇이 더 큰지 구하면 구할 수 있다. 이를 점화식으로 나타내면이 와 같이 나타낼 수 있다. 자세한 설명은 https://hi-guten-tag.tistory.com/160 이 블로그 링크를 참고하길 바..