곰탱이의 공부정리

https://www.acmicpc.net/problem/13549  이 문제는 누나가 동생을 찾을 때 지금 위치에서 2배로 순간이동하면 0초, +-1로 이동하면 1초 걸려서 하나씩 탐색을 한다. 이때 동생을 찾는 가장 빠른 시간을 구하는것이 문제이다.  이 문제는 언뜻보면 그냥 보통의 BFS로 풀어야하거나, 다익스트라 알고리즘으로 풀어야 할 것처럼 보인다. 그런 식으로 풀어도 괜찮지만 문제의 의도는 0-1 너비우선탐색 방법을 쓰는 것이 의도이기에 0-1 너비우선탐색을 알아보자.  0-1 너비우선 탐색이란 그래프에서 모든 노드 사이의 엣지의 웨이트가 0혹은 1로 이루어져 있을 때 사용할 수 있다. 이 알고리즘의 작동을 간편히 설명하면, 일단 거리를 저장할 배열 뭐 dist를 정의한다. 그리고 우리가 통상..

https://www.acmicpc.net/problem/9251  이 문제는 두 문자열의 가장 긴 공통서열을 구하는 문제이다.   이 문제는 전에 ROSALIND에서 풀어본적이 있으므로, https://jangbearbio.tistory.com/41 자세한 사항은 이 링크에 들어가여 참조하길 바란다. import sysinput = sys.stdin.readlineA = ' '+input().rstrip()B = ' '+input().rstrip()lcs_map = [['' for _ in range(len(B))] for _ in range(len(A))]for i in range(len(A)): for j in range(len(B)): if i==0 or j==0: ..

https://www.acmicpc.net/problem/2096  이 문제는 주어진 매트릭스의 맨 위에서 아래로 내려가며 더했을 때 가장 큰 값과 가장 작은 값을 구하는 문제이다. 이 때 내려갈때는 바로 아래로 내려가거나 바로 아래와 붙어있는 칸으로만 내려갈 수 있단 점이다.  이 문제는 그동안 풀어온 다이나믹 프로그래밍처럼 풀면 max_matrix[i][0] = max(max_matrix[i-1][:2]) + graph[i][0]max_matrix[i][1] = max(max_matrix[i-1]) + graph[i][1]max_matrix[i][2] = max(max_matrix[i-1][1:]) + graph[i][2]  와 같은 점화식으로 구할 수 있을 것만 같다.  하지만 이 문제는 그동안 메..

https://www.acmicpc.net/problem/1916  이 문제는 도시 간의 버스비용이 최소로 해서 출발지와 도착지로 가는 버스비용 중 가장 최소비용을 구하는 문제이다. 이 문제는 정확히 데이크스트라 알고리즘(다익스트라 알고리즘이라고도 불림)을 사용하는 문제이다. 데이크스트라 알고리즘은 거칠게 설명하자면 그래프를 탐색하면서 내가 지나온 비용을 들고 탐색하고, 도시에 도착할 때 마다 그 전의 최소비용과 비교하며 지금이 더 최소라면 새로 업데이트 하는 식으로 한 도시에서 다른 도시로 가는 최소비용을 구하는 알고리즘이다. import sysinput = sys.stdin.readlineimport heapq cities = int(input().rstrip())buses = i..

https://www.acmicpc.net/problem/11660  이 문제는 정수가 쓰여진 표가 주어지고 x1,y1부터 x2,y2까지의 구간합을 구하는 문제이다. 이 문제에서 구해야 하는 횟수가 최대 십만번 이므로 필자는 미리 각 점에서의 구간합들을 구하고, 표에서 구해야 하는 구간합만 구하는 식을 이용하여 답을 찾아냈다. 이 식은 다음 표를 이용하여 구했다. 먼저 우리는 0,0부터 x,y까지의 구간합을 구한 테이블을 구해야 한다. 이는 간단히 구할 수 있으니 패스하겠다. 위 그림을 보면 x2,y2와 x1,y1 사이의 구간합은 노란색이다. 이 노란색을 구하는 법은 (x2,y2) - (x1-1,y2)-(x2,y1-1) + (x1,y1)이다. 이러한 것들을 그냥 코드로 구현하면,import sysinpu..

https://www.acmicpc.net/problem/9465  이 문제는 가로로 N줄 세로로 2줄인 스티커 배열이 주어진다. 스티커 배열 안의 스티커는 각자 점수가 있다. 어떠한 스티커를 떼어낸다면 그 스티커와 변이 맞닿아있는 스티커는 못 쓴다는 설정이다.  이러한 경우 스티커 배열에서 가장 점수가 높게 스티커를 떼어낼 때의 점수를 출력하는 것이 문제이다.  이 문제는 언뜻 보면 브루트포스처럼 모든 것을 해야할 것 처럼 보이지만, 이 문제 또한 일종의 다이나믹 프로그래밍 문제이다. 이 문제를 왼쪽부터 훑어가면서 특정 스티커를 뽑을 때, 이 스티커를 뽑을 수 있게하는 직전 스티커들 중, 가장 점수가 높은 것들을 따라가는 식으로 하면된다. 이게 말로하면 복잡한데 그림으로 그려주자면  내가 지금 체크표시..

https://www.acmicpc.net/problem/1991  이 문제는 A가 뿌리로 시작하는 트리를 전위,중위,후위 순회한 결과를 출력하는 문제이다.   전위순회는 루트,왼쪽서브트리,오른쪽서브트리 순으로 순회하는 것이고 중위순회는 왼쪽서브트리,루트,오른쪽서브트리 순으로 순회하는 것이고, 후위순회는 왼쪽서브트리,오른쪽서브트리,루트 순으로 순회하는 것이다.   이 문제는 필자는 먼저 딕셔너리를 이용하여, 트리를 구현하고, 재귀를 이용하여 왼쪽,오른쪽 서브트리를 계속해서 호출하여 잎에 닿을 때까지 깊숙이 내려가 잎에서 재귀를 멈추고 리턴하는 식으로 풀었다. 이 때 간단하게 순서만 조금 바꿔주면 전위,중위,후위를 각각 구현할 수 있다. import sysinput = sys.stdin.readlinede..

https://www.acmicpc.net/problem/1932  이 문제는 정수 삼각형이 주어지고 피라미드의 맨 위부터 오직 맞닿아 있는 아래 오른 대각선, 아래 왼 대각선으로 쭈욱 내려갔을 때, 그 경로에 있는 숫자의 합이 최대인 값을 구하는 문제이다. 이 문제 또한 간단하게 다이나믹 프로그램으로 그 점에서 최댓값이 되게하는 값을 순간순간 저장해가며 전진해나가 끝의 값 중 가장 큰 값을 출력하면 된다. import sysinput = sys.stdin.readlinedef finding_max(pyramid): matrix = [[0]]+[[0]*n for n in range(1,N+1)] for i in range(1,N+1): for idx in range(len(matr..

https://www.acmicpc.net/problem/1629  이 문제는 A,B,C가 주어지고 A의 B승을 C로 나눈 나머지를 구하는 문제이다.  이 문제는 A,B,C가 매우 큰 수가 나오므로 통상적으로 거듭제곱을 한다면, 시간복잡도가 O(n)이므로 시간초과가 뜨게 된다. 또한 정수형의 범위도 초과할 수 있으므로 여기서는 분할정복 알고리즘을 응용해야 한다. 필자는 분할정복 알고리즘을 처음 써보기에, https://hbj0209.tistory.com/43 이 블로그를 참고하여 코드를 짰다.  분할정복 알고리즘이란, 복잡한 문제들을 간단한 문제로 쪼개고 쪼개서 간단한 문제 여러 개를 푼 다음 그것을 다시 합쳐서 문제를 해결하는 알고리즘이다. 이러한 분할정복 알고리즘은 기본적으로 아래와 같은 방식으로 짜..

https://www.acmicpc.net/problem/1149  이 문제는 RGB 거리에 직선으로 나열되어 있는 집들이 빨강,초록,파랑 색 중 하나로 색칠 되는데 서로 이웃인 집의 색깔은겹쳐서는 안 되고, 집마다, 색마다 색칠하는 비용이 주어지고, 모든 집을 규칙대로 칠했을 때 최소비용으로 색칠했을 때의 최소비용을 구하는 문제이다.  이 문제는 얼핏보면 모든 경우의 수를 구해서 최솟값을 구하는것 같다만 경우의 수만 3x2의 n승인지라 시간을 무조건 초과하게 되어있다. 이 때 우리는 여기서 다이나믹프로그래밍을 이용하여, 시간을 초과하지 않을 수 있다.  필자는 다이나믹 프로그래밍으로 풀겠다는 느낌은 일종의 매트릭스를 만들어 기록하며 훑으며 처리할 수 있고, 이 처리라는 것이 모든 인덱스에서 똑같이 시행..