SYDev

문자열 검색 문제를 위한 KMP 알고리즘과 자료 구조 접미사 배열(suffix array)을 알아보고, 이들로 해결할 수 있는 문제의 예를 살펴보자. 용어 정리 문자열 S의 i번 글자부터 j번 글자까지로 구성된 문자열을 S의 부분 문자열(substring)이라 부르고, S[i...j]로 표기 문자열 S의 0번 글자부터 a번 글자까지로 구성된 부분 문자열 S[0...a]를 S의 접두사(prefix)라고 부르고, S[...a]로 표기 문자열 S의 b번 글자부터 끝까지로 구성된 부분 문자열 S[b...|S|-1]을 S의 접미사(suffix)라고 부르며, S[b...]로 표기 문자열 검색 문자열 검색 문제: 주어진 긴 '짚더미(haystack)' 문자열 H가 '바늘(needle)' 문자열 N을 부분 문자열로 포..

가장 유명한 알고리즘 디자인 패러다임인 분할 정복(Divide & Conquer)을 이해하고 예제를 통해 구현해보자. 분할 정복 분할 정복(Divide & Conquer): 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 얻어내는 방법이다. 부분 문제와 나머지를 나눌 때 거의 같은 크기로 나눈다. 분할 정복 설계 divide: 문제를 더 작은 문제로 분할하는 과정 conquer: 해결이 용이한 수준까지 분할된 문제를 해결하는 과정 merge: 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 수열의 빠른 합과 행렬의 빠른 제곱 #include using namespace std; int fastSum(int n) { if(n == 1){ return 1; } if(n ..

문제풀이 과정에서 가장 간단하면서 틀릴 가능성이 낮은 '완전 탐색(exhaustive search)' 알고리즘과 이를 구현하는데 유용한 '재귀 호출(recursion)'을 이해하고 문제를 통해 직접 구현해보자. 완전 탐색과 재귀 호출 완전 탐색 완전 탐색(exhaustive search): 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 경우의 수가 커지더라도 컴퓨터의 계산 능력을 고려하면 생각보다 훨씬 간편하게 문제를 풀 수도 있다. 재귀 호출 재귀 함수(recursive function): 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 재귀 함수에는 "더이상 쪼개지지 않는" 최소..

참고자료 구종만, , 인사이트, 2012.11.01

c++, 자료구조까지 공부를 끝내고, 다음으로 알고리즘을 어떻게 공부할지 고민을 많이 하다가 c++을 다루는 알고리즘 서적인 [프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략]을 선택했다. 일명 종만북이라고 불리는데, 난이도가 상당하다고 하니 열심히 공부해보자..! How to Solve the Problem 1. 문제를 읽고, 이해: 작은 조건까지 완벽하게 이해하자 -> 사소한 거 하나 틀려도 오답처리 2. 문제를 나에게 익숙한 용어로 재정의: 문제의 추상화 -> 다루기 쉬운 수학적/전산학적 개념으로 표현 3. 어떻게 해결할지 계획: 사용할 알고리즘, 자료구조 선택 -> 체계적 접근을 위한 질문 - 비슷한 문제를 푼 적이 있나? - 단순(무식)하게 풀 수 있을까? - 문제 푸는 과정을 수식화할 수 ..