KMP 알고리즘(Knuth-Morris-Pratt Algorithm) KMP 알고리즘(Knuth-Morris-Pratt Algorithm) 문자열 검색 알고리즘의 하나로, 고지식한 알고리즘을 한 차례 개선할 수 있습니다. 찾을 단어의 접두사와 접미사를 이용하여 탐색횟수를 줄여줍니다. 우선, KMP를 본격적으로 설명하기 전, 고지식한 알고리즘으로 문자열에서 단어를 찾는 경우를 살펴보겠습니다. 고지식한 알고리즘으로 탐색 :: O(MN) 탐색할 문자열 : ABABAABAABAA 찾을 단어 : ABAABA 고지식한 알고리즘은 단어를 한칸씩 이동하면서 문자열을 탐색합니다. 탐색 결과, 찾을 단어의 시작 위치를 7번 변경하여 모든 문자열을 탐색할 수 있었습니다. 이 알고리즘은 단어의 길이가 M이고 문자열의 길이가 N일 때, big-O 표기법으로 O(MN)의 시간복잡도를 갖습니다. 이.. [SW Expert Academy] 1213. String [SW Expert Academy] 1213. String 문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14P0c6AAUCFAYi&categoryId=AV14P0c6AAUCFAYi&categoryType=CODE 나의 풀이 String에서 특정 단어를 찾는 알고리즘은 아래와 같이 분류할 수 있다. 1. 고지식한 검색2. 라빈카프3. KMP4. 보이어-무어 나는 라빈카프 방식과 KMP 방식으로 풀어보았다. 라빈카프 : 찾을 단어의 HASH 값을 이용하여 동일한 HASH 값을 갖는 단어를 찾는다. O(N) KMP : 찾을 단어의 접두사와 접미사가 동일한 길이를 저장한 벡터를 이용하여, 탐색 .. [C/C++] BOJ 16235 :: 나무 재테크 BOJ 16235 :: 나무 재테크 문제 링크 : https://www.acmicpc.net/problem/16235 나의 풀이 문제를 구현할 때 특별히 어려운 기술을 요구하는 문제는 아니다. 문제를 잘 읽고 그대로 코딩하면 된다! * 코드를 다 짜고 한 가지 간과했었던 점을 발견했는데가을의 경우, 갱신을 하면서 배열을 탐색하여, 지금 갱신된 값들도 탐색을 하는 오류를 범한 점이다.물론, 갱신되는 나무의 나이는 1이고 탐색 시에는 나무의 나이가 5의 배수인 것을 탐색하기 때문에 결과에는 아무런 지장이 없지만, 이건 아주 중대한 실수였다..!!! 따라서, 봄에 나무가 존재하는 위치를 새로운 벡터에 저장해두고, 가을에 이 벡터를 탐색함으로써 문제를 해결하였다. * 죽게 되는 나무를 벡터에서 제거하기 위하여,.. [C/C++] BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy) BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy) 나의 풀이 바둑판의 값이 0인 것들의 위치를 순차적으로 벡터 v에 저장한다. 벡터를 돌면서 0의 위치의 값을 1로 바꾸고 2개가 바뀌었을 때, 죽일 수 있는 상대 돌의 개수를 센다. bfs방식으로 바둑판의 값이 2인 곳의 탐색을 시작하면서 상하좌우에 2가 있으면 죽일 수 있는 돌의 개수를 1 증가시킨다. 상하좌우에 0이 있으면 탐색을 마쳤을 때, 죽일 수 있는 돌의 개수를 갱신하지 않는다. 모든 탐색을 마친 후, 이전 ans와 비교하여 죽일 수 있는 돌의 개수가 더 많을 때 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Dal.. [C/C++] BOJ 3/2 코딩테스트 대비 모의고사 A번 - 계란으로 계란치기 BOJ 3/2 코딩테스트 대비 모의고사 A번 - 계란으로 계란치기 문제 링크 : https://www.acmicpc.net/contest/problem/396/1 나의 풀이 계란이 들어있는 판을 모두 탐색하면서, 내가 들고있는 계란이 아니고 깨진 계란이 아니면 들고 있는 계란과 충돌시킨다. 충돌시킨 후 각 계란의 내구성과 깨짐 여부를 갱신시킨다. 다음에 들 계란을 오른쪽으로 이동하며 깨지지 않은 계란으로 결정한 후, 이를 반복한다. 모든 계란이 깨졌거나 마지막 계란까지 탐색을 마친 경우, 깨진 계란의 개수를 계산하여 답을 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_prob.. [C/C++] BOJ 16234 :: 인구 이동 BOJ 16234 :: 인구 이동 문제 링크 : https://www.acmicpc.net/problem/16234 나의 풀이 flag를 여러 군데에 사용하다 보니 코드가 좀 지저분한 감이 있긴 하다 ㅠㅠ 1. 배열을 방문하지 않았을 때, 너비 우선 탐색으로 인구 이동이 가능한 지역끼리 clustering을 한다. 2. 각 그룹은 숫자 1, 2, 3.. 으로 지정하고, 그에 맞는 인구 수를 계산하여 일차원 배열 group에 저장해 둔다. 3. 전체 배열의 탐색을 마치면, clustering 된 그룹의 인구 수를 미리 계산해 둔 group의 각 값으로 대체한다. 4. 탐색한 횟수를 증가시킨다. 5. 종료 조건 : 탐색 시, clustering이 한번도 되지 않았다면, flag가 변화하지 않아 종료. 나의 .. [SW Expert Academy] 1211. Ladder2 [SW Expert Academy] 1211. Ladder2 문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh&categoryId=AV14BgD6AEECFAYh&categoryType=CODE 나의 풀이 1. 출발지점을 찾아야 하기 때문에 도착지점에서부터 탐색한다. 2. 출발지점까지 움직이면서 움직인 거리를 저장한다. 3. 출발지점에 도달했을 때, 움직인 거리가 저장된 최소 거리보다 작다면 최소 거리와 출발 지점을 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Al.. [SW Expert Academy] 1210. Ladder1 [SW Expert Academy] 1210. Ladder1 문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE 나의 풀이 1. 도착지점인 마지막 행에서 2를 찾아 위로 올라가면서 출발지점을 찾아나간다. 2. 왼쪽, 오른쪽, 위쪽 순으로 탐색하며 사다리의 범위를 벗어나는지, 0인지를 확인하고 continue 한다. 3. 지나간 곳을 0으로 바꾸고 현재 지점을 갱신한 후 반복한다. 4. 가장 윗 행에 도달했을 때, 그 행의 열의 좌표를 반환한다. 나의 코드 Github : https://g.. 이전 1 2 3 4 5 6 ··· 17 다음
