알고리즘 (44) 썸네일형 리스트형 KMP 알고리즘 Goal 여러 문자열 문제에 응용될 수 있는 KMP 알고리즘의 아이디어에 대해 설명할 수 있다. KMP 알고리즘에서 사용되는 키워드를 설명할 수 있다. KMP 알고리즘을 구현할 수 있다. KMP 알고리즘이란? 문자열 검색 알고리즘으로, 검색 과정에서 불일치가 일어났을 때, 다음으로 검색을 시도할 시작 위치를 빠르게 찾아내는 문자열 검색 최적화 알고리즘이다. 검색 과정에서 얻는 정보를 버리지 않고 활용하는 방법으로, 불일치가 일어났을 때 지금까지 일치한 글자의 수를 이용해 다음 검색을 시도할 위치를 찾아낸다. (커누스-모리스-프렛(Knuth-Morris-Pratt) 알고리즘, 흔히 KMP 알고리즘이라고 한다) 비교하는 두 문자열의 길이가 각각 N과 M일 때, 시간 복잡도 : O(N + M) 접두사, 접미사.. 해시 테이블(Hash Table) Goal연관 배열과 해시 테이블에 대한 이해해시 테이블 관련 용어에 대한 이해해시 함수를 구현해본다.해시 충돌 처리 기법에 대해 몇 가지 설명할 수 있다.해시 테이블(hash table)이란?연관 배열(associative array)의 일종으로, 키(key)를 값(value)에 매핑할 수 있는 자료구조이다. *연관 배열 vs 해시 테이블더보기연관 배열(associative array) : (키, 값) 쌍으로 구성된 추상 자료형으로 연관 배열에서 키는 유일한 값을 갖는다.맵(map), 사전(dictionary)으로 불리기도 한다.참고) https://en.wikipedia.org/wiki/Associative_array 구현 형태 해시 테이블 관련 용어해시 테이블연관 배열(associative array.. 탐욕 알고리즘(greedy algorithm) Goal 탐욕 알고리즘과 특징에 대해 설명할 수 있다. 탐욕 알고리즘으로 최적해를 구할 수 있는 경우에 대해 설명할 수 있다. 탐욕 알고리즘(greedy algorithm) 현재 순간 최적(local optimal)이라고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법 탐욕법(greedy method)이라고도 한다. 특징 순간 최적 선택한 결과가 전체 문제의 최적이라는 보장이 없다. 현재의 선택이 앞으로 남은 선택에 어떤 영향을 끼칠지는 고려하지 않는다. 다음 그림은 탐욕 알고리즘이 항상 최적을 보장하지 않음을 나타낸다. 그렇다면, 항상 최적의 결과라는 것을 보장하지 못하는데 왜 탐욕 알고리즘을 사용하는가? 그 이유는 다음과 같다. 빠르다 : 탐욕 알고리즘을 사용해도 항상 최적해를 구할 수 있는.. 동적 계획법(Dynamic Programming) Goal 동적 계획법에 대해 설명할 수 있다. 동적 계획법(Dynamic Programming) 복잡한 문제를 여러 개의 작은 문제로 나누어 푸는 방법을 말한다. 분할 정복과의 차이점 동적 계획법과 분할 정복의 가장 큰 차이점은 계산 결과의 재활용이다. (부분 문제를 각각 독립적으로 나눠지지 않음) 동적 계획법의 경우 두 번 이상 계산되는 중복되는 부분 문제(overlapping subproblems)의 계산 결과를 캐시에 저장함(재활용)으로써 여러번 계산되는 것을 막아 속도 향상을 꾀할 수 있다. 이때, 한번 계산된 결과같은 캐시에 저장하는 최적화 기법을 메모이제이션(momoization)이라고 한다. 구분 하자면 다음과 같다. 부분 문제를 비슷한 크기로 나누고, 각각을 독립적으로 나누어 푼다. 큰 문.. 분할 정복(Divide and Conquer) Goal 분할 정복에 대해 설명할 수 있다. 분할 정복 한 문제를 둘 이상의 부분 문제(sub-problem)로 나누어 해결하고 이를 합쳐 원래 문제를 해결하는 기법 분할 정복 알고리즘은 다음과 같이 세 부분으로 나누어서 생각해볼 수 있다. 분할 정복의 단계 분할(Divide) : 원래 문제를 분할하여 더 작은 하위 문제들 나눈다. 정복(Conquer) : 하위 문제 각각을 재귀적으로 해결. (정복 과정에서 더이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제를 기저 사례(base case)라 한다.) 병합(merge) : 하위 문제들의 답을 합쳐서 원래 문제를 해결 분할 정복을 적용하기 위해서는 문제에 다음과 같은 몇 가지 특성이 성립해야 한다. 부분 문제로 나누는 자연스러운 방법이 있어야 한다. 부.. [BOJ 9663] N-Queen 문제 : https://www.acmicpc.net/problem/9663 분류 : 백트래킹 N * N 체스판에 N개의 퀸을 놓는 경우의 수를 찾는 문제이다. 가장 빠른 방법은 미리 구해놓은 값을 리턴하는 경우이다. N이 15 이하의 자연수 이므로 15개의 값만 미리 배열에 저장해 놓고 입력값에 따른 경우의 수를 리턴한다. 다음 그림은 n의 값에 따른 경우의 수의 개수이다. 예를 들어 N = 8일 경우, 8*8체스판에 8개의 퀸을 놓을 수 있는 경우의 수는 총 92가지가 된다. 가장 빠른 방법이긴 하지만, 알고리즘을 공부를 하는 입장에서는 도움이 되지 않는 방법이므로 백트래킹 방법으로 문제에 접근해보자 퀸 배치하기 우선, 퀸을 놓을 수 있는 상황에 대해 알아보자 퀸은 가로, 세로, 대각선 방향으로 이동이.. [BOJ 2231] 분해합 , [BOJ 4673] 셀프 넘버 분해합 : https://www.acmicpc.net/problem/2231 분류 : 브루트 포스 셀프 넘버 : https://www.acmicpc.net/problem/4673 분류 : 에라토스테네스의 체 두 문제가 유사한 부분이 있어서 같이 설명하려고 한다. 분해합 입력된 수가 되게 하는 생성자를 찾는 문제이다. (생성자 : 원래 수와 각 자리 수의 합 => 분해합) 예를 들어 216의 생성자로 198과 207이 될 수 있다. 198 + 1 + 9 + 8 = 216 207 + 2 + 0 + 7 = 216 생성자를 찾기 위해서 1~n까지 모든 수의 분해합이 N이 되는지 확인하는 방법도 있겠지만, 좀 더 최적화 할 수 있는 방법이 있다. 각 자리숫자가 최대 9라는 점을 이용하면 좀 더 쉽게 풀 수 있다... [BOJ 1002] 터렛 문제 : https://www.acmicpc.net/problem/1002 문제 분류 : 수학 원의 위치 관계를 따져보는 문제이다. 두 원의 위치 관계 두 원이 일치하는 경우 => d = 0, r1 = r2 만나지 않는 경우 1) 내부에서 만나지 않는 경우 : d 차 차 < d < 합 */ while (T--) { scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2); if (x1 == x2 && .. 이전 1 2 3 4 5 6 다음
