랄뚜기의 코딩일기

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 트리를 공부 중이라면 꼭 풀어야 할 문제라고 생각한다. 전위 순회, 중위 순회, 후위 순회의 관계를 알아야 풀 수 있는 문제이다. 위와 같은 트리를 중위 탐색 후위 탐색한 결과이다. 위를 보고 재귀를 사용하면 쉽게 풀 수 있을 것이라 생각했다. 중위 순회은 루트노트 1의 기준으로 보았을 때, 1의 왼쪽에는 왼쪽 서브트리의 노드들이 오른쪽에는 오른쪽 서브트리의 노드들이 있음을 알 수 있었다. 후위 순회는 처음에 직관적으로 중위 순회..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp의 대표문제인 LCS문제를 풀었다. dp의 핵심은 dp배열이 무엇을 의미하는지 알아내는 것이 핵심이다. i=첫번째 문자열(s1)의 인덱스, j=두번째 문자열(s2)의 인덱스라고 할 때, dp[i][j]는 s1의 i번째 s2의 j번째까지 비교했을 때 LCS2의 최대 크기를 의미하게 된다. LCS를 구하는 알고리즘은 다음과 같다. 1. s1[i]==..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 처음에 보고 이게 왜 그래프 이론인지 생각했다. '그냥 조건 몇 개 넣고 돌리면 되겠네!'라는 안일한 생각을 가지고 10분 만에 짜서 제출했지만 바로 뜨는 틀렸습니다... 한 20분 정도 혼자 끄적이다 결국 다른 분들의 풀이를 봤다. 역시 내가 넣은 조건에는 예외가 존재했다. 모든 조건을 넣는 것은 매우 힘들기 때문에 필수 조건을 넣어주고 BFS를 돌리면 됐다. 경우의 수를 구..