코딩하는 신학생의 넋두리

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다. 8.1 도입 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나이다. 동적 계획법(Dynamic Programming)이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(Dynamic), 혹은 프로그래밍(Programing)이란 단어와는 아무런 관련이 없습니다. 따라서 동적 프로그래밍이 아니라 동적 계획법이 적절한 번역이다. 중복되는 부분 문제 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이..

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다. 7.1 도입 분할 정복(Divede & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것에 있다. 분할 정복 알고리즘은 다음과 같은 세 가지 구성 요소를 가지고 있다. Divide : 문제를 더 작은 문제로 분할하는 과정 Merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 Base Case : ..

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다. 6.1 도입 전산학에서 무식하게 푼다(Brute-Force)는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(Exhaustive Search)이라고 부릅니다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 완전 탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법입니다. 실제 프로그래밍 대회에서도 프로그램을 빠르고 정확하게 구현하는 능력을 검증하기 위해 입력의 크기를 작게 제한한 문제들이 흔히 출제되며, 완전 탐색은 더 빠른 알고리즘의 기반이 되기도 하기 ..