지식이 홀쑥

KMP (Knuth-Morris-Pratt) Algorithm KMP 알고리즘은 주어진 문자열(M)에서 찾고자 하는 문자열(N)을 빠르게 찾아내는 알고리즘이다. KMP 알고리즘은 O(N+M)으로 문자열을 전체비교하는 문자열 완전검탐색 (Brute Force, 시간복잡도 : O(NM))보다 더욱 빠르게 원하는 문자열을 검색할 수 있다. KMP 알고리즘 이해 KMP 알고리즘의 이해는 다음 글들을 참고하면 좋을 것 같다. KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을 bowbowbow.tistory.com [알고리즘/ 파이썬] KMP..

오늘은 백준에서 1018번문제 체스판 다시 칠하기를 풀어보았다. MN개의 단위 정사각형으로 나뉜 M X N 크기의 보드가 있다. 정사각형들은 검은색 또는 흰색으로 칠해져있고, 이 보드를 잘라 8 X 8 크기의 체스판으로 만들어야 한다. 변을 공유하는 두개의 사각형은 다른 색으로 칠해져 있는, 즉 체스판은 검은색가 흰색이 번갈아서 칠해져 있어야 한다. 결국 체스판을 색칠하는 경우는 맨 왼쪽 위칸이 흰색 또는 검은색인 경우 두 가지로 나뉜다. 보드는 그런 형식이 지켜져있다는 보장이 없기에 보드를 8 * 8크기의 체스판으로 잘라 몇개의 정사각형을 다시 칠한다. 이 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제이다. N과 M이 첫째 줄에 주어지고 8 fix_cnt : min_fix = fix_cnt ..

2231번 문제 분해합 구하기이다. 구하려고 하는 수가 M이다. 어떤 자연수 N이 있을 때, 그 자연수의 분해합은 N은 M + M의 각 자리수별 숫자 를 더한 값이다. 1

달팽이가 막대기를 올라가고 싶단다. 높이가 v 인 나무 막대를 달팽이가 올라가는데 낮에는 a미터 올라가고 밤에는 b미터 미끄러진다. v : 높이 a : 낮에 움직이는 거리 b : 밤에 미끄러지는 거리 d : 올라가는데 걸리는 날 중요한 점은 낮에 올라가면 다시 미끄지지 않기 때문에 먼저 d 를 1 올려주고 v 를 a만큼 먼저 내리고 계산한다. ( a * d ) - ( b * d ) = ( v - a ) ( a - b ) * d = ( v - a ) d = ( v - a ) / ( a - b ) 이다 나머지가 0이라면 ( v - a ) / ( a - b ) + 1 이 답이고 나머지가 있다면 ( v - a ) / ( a - b ) + 2 가 답이다. 코드는 import java.io.BufferedReade..