곰탱이의 공부정리

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

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

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

https://www.acmicpc.net/problem/11053 이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이다. 예를 들어 [10,20,10,30,40] 이란 수열이 있다면 이중 가장 긴 증가하는 부분수열은 [10,20,30,40]으로 길이가 4이다. 이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다. 수열 위를 훑어가며 지금 이 인덱스에서 가장 길게 형성된 수열을 자신의 앞에서 찾으며 더 이어갈 수 있는지를 체크하며 풀면 된다. def lgis(seq,l): p = [-1] * l #거리 for i in range(l): for j in range(i): if seq[j] p[i]:#증가하고, 더 길다면 ..

https://rosalind.info/problems/glob/ ROSALIND | Global Alignment with Scoring MatrixIt appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Global Alignment with Scoring Matrix solved by 868 Generalizing the Alignment Score The edit alignment score in “Edit Distance Alignment” courosalind.infoProblemTo penalize symbol substitutions different..

https://rosalind.info/problems/ctea/ ROSALIND | Counting Optimal AlignmentsIt appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Counting Optimal Alignments solved by 460 2013년 1월 18일 4:24:30 오후 by Rosalind Team Topics: Alignment, Combinatorics Beware of Alignmentrosalind.infoProblemRecall from Topics: Alignment, Dynamic Programming">“Edit..