오늘 한 일
분할 정복 개념 정리
분할정복은 동적계획법과 함께 문제를 해결하는 알고리즘 패러다임 중에 하나다. 문제가 최적부분구조이고 큰 문제를 작은 문제로 쪼갤 때 그 해결책들을 쌓아서 큰 문제를 해결할 수 있을 경우 분할정복 알고리즘을 사용할 수 있다. 분할 정복 알고리즘을 사용할 경우, 해답 간의 재귀형태를 찾아야한다. 병합정렬, 이진탐색의 경우 분할정복 알고리즘을 해결할 수 있다.
동적계획법 정리
동적계획법은 분할 정복 알고리즘과 함께 문제를 해결하는 알고리즘 패러다임 중에 하나다. 문제가 최적부분구조이고 큰 문제에서 하위문제 해결책이 중복해서 호출이 될 경우에는 동적계획법을 사용하는 것이 효율적이다. 동적계획법은 하위 문제의 연산 결과를 별도로 저장한 후 큰 문제에서 작은 문제를 여러번 해결해야할 때 중복계산을 피하고 계산 결과만을 활용할 수 있다. 피보나치 수열, 외판원 문제, LCS 문제 등에서 동적계획법을 사용할 수 있다.
백준 9251번 풀이
LCS 문제를 정리했다. 동적계획법과 LCS 문제풀이를 익힌 후에 백준 9251번을 풀었다. 동적 프로그래밍은 큰 문제를 작은 문제로 분해하고 두 문제 간의 재귀형태를 표현하고 테이블만 그릴 수 있다면 개념적으로 쉽게 해결할 수 있다. 하지만 개념을 코드로 옮기는 것은 쉽지가 않았다. 특히, 2차원 리스트에 연산결과를 기록하려고 하니까 인덱스가 맞지 않아서 자꾸 오류가 나서 디버깅을 계속해야했다. 디버깅 툴을 계속 사용해도 눈에 보이지 않아서 결국에는 노트에 일일이 인덱스를 적어가면서 오류가 난 부분이 어디인지 확인했다. 기기로도 해결이 안된다면 수작업으로 하나씩 해결하는 것도 방법임을 알게 되었다.
플로이드 와샬 알고리즘
그래프의 모든 정점에서 다른 모든 정점으로 가는 최소 경로를 찾는 알고리즘이다. 동적계획법을 통해 테이블을 갱신하여 정점들의 최소경로를 추적한다.