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. 어떻게 해결할지 계획: 사용할 알고리즘, 자료구조 선택 -> 체계적 접근을 위한 질문 - 비슷한 문제를 푼 적이 있나? - 단순(무식)하게 풀 수 있을까? - 문제 푸는 과정을 수식화할 수 ..

정점(vertex)과 간선(edge)로 표현되는 그래프 자료구조에 대해 이해하고, 구현해보자. 그래프의 이해 정점(vertex): 연결의 대상이 되는 개체 또는 위치를 의미한다. 간선(edge): 이들 사이를 연결하는 선을 의미한다. 다음과 같이 정점과 간선으로 구성된 자료구조를 그래프라고 한다. 그래프의 종류 무방향 그래프와 방향 그래프 무방향 그래프(undirected graph): 연결 관계에 있어서 방향성이 없는 그래프를 의미한다. 방향 그래프(directed graph) or 다이그래프(digraph): 간선에 방향정보가 포함되어 있는 그래프를 의미한다. 완전 그래프(complete graph): 각각의 정점에서 다른 모든 정점을 연결한 그래프를 의미한다. 방향 그래프의 간선의 수는 무방향 간선..

테이블의 핵심 주제라 할 수 있는 충돌 문제의 해결책을 몇 가지 알아보고, 구현해보자. 열린 어드레싱 방법 열린 어드레싱 방법(open addressing method): 충돌이 발생하면 다른 자리에 대신 저장하는 방법 선형 조사법, 이차 조사법, 이중 해쉬가 이에 속한다. 선형 조사법 선형 조사법(Linear Probing): 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 방법이다. 옆자리가 비어있지 않을 경우, 옆으로 한 칸 더 이동을 해서 자리를 살핀다. 그러나, 이런 구조는 충돌의 횟수가 증가함에 따라 '클러스터(cluster) 현상(특정 영역에 데이터가 집중적으로 몰리는 현상)'이 발생하기 쉽다. 이런 선형 조사법의 단점을 극복할 수 있는 방법이 이차 ..

빠른 탐색의 성능을 보이는 테이블 자료구조와 테이블에 의미를 부여하는 해쉬 함수를 이해하고, 두 개념이 합쳐진 해쉬 테이블을 구현해보자. 테이블 자료구조의 이해 테이블(Table): 저장되는 데이터의 키(key)와 값(value)이 하나의 쌍을 이루는 자료 구조를 의미한다. 키(key)가 존재하지 않는 '값'은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다. 하나의 키(key)에 대응되는 값(value)는 하나이기 때문에, 테이블 자료구조의 탐색 연산은 $O(1)$의 시간 복잡도를 가진다. 배열을 기반으로 하는 테이블 #include typedef struct _empInfo { int empNum; int age; } EmpInfo; int main(void) { EmpInfo empInfoArr..