지식이 홀쑥

[KMP Algorithm] 문자열 검색 KMP 알고리즘

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번 체스판 다시 칠하기 Python

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

[백준 알고리즘] 2231번 문제 분해합 구하기 Python

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

[백준 알고리즘] 2869번 달팽이는 올라가고 싶다 Java

달팽이가 막대기를 올라가고 싶단다. 높이가 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..

[백준 알고리즘] 1193번 분수찾기 Java

분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> ... 과 같이 지그재그 순서로 차례대로 1~..번 분수라고 한다. x가 주어졌을 때 x번째 분수를 구하란다. 일단 저 표대로 보려니까 너무 어려워서 그림을 돌려봤다. 피라미드처럼 본다고 그리고 볼 수 있다고 생각하자. 첫번째 라인은 1/1 두번째 라인은 2/1 1/2 세번째 라인은 3/1 2/2 1/3 ... 순서는 1 3 2 4 5 6 .. 이다 여기서 발견한 규칙은 짝수 행은 오른쪽에서 왼쪽, 홀수 행은 왼쪽에서 오른쪽으로 순서가 커지고 행 번호 + 1 = 분모 + 분자, 행의 번호와 그 행의 분수의 숫자는 같다. a : 원하는 분수 번호 cnt : 개수 n : 행 번호 n에 1씩 더할 때 마다 cnt에 n을 더하고..

[백준 알고리즘] 2839번 설탕 배달 Java

설탕을 배달하는데 3킬로그램 봉지와 5킬로그램 봉지에 딱맞게 최소한의 봉투로 담고싶단다. a : 담고 싶은 설탕 kg b : 5kg 설탕봉투 result : 총 봉투의 개수 5kg 봉투로 최대한 담고 남은 양을 3kg에 담아야 가장 최소한의 봉투로 담기 때문에 먼저 5kg봉투로 담는다는 가정을 한다. 5kg으로만 가득 담고 남은 양이 3kg으로 나눠지는지 확인하고 안나눠진다면 5kg봉투 하나를 빼고, 또 3kg으로 나눠지는지 확인하고 안나눠지면 또 5kg봉투를 빼고 반복하다가 만약 3kg으로 나눠지면 총 봉투의 수를 b + ( a - b * 5) / 3 로 계산했다. 따라서 코드를 import java.util.Scanner; public class back2839 { public static void ..

[백준 알고리즘] 1712번 손익 분기점 Java

손익 분기점 계산 문제이다. 내가 생각한 공식은 a : 고정비용 b : 가변비용 c : 상품가격 i : 손익분기점 판매량 만약 b >= c 일 경우에는 손익분기점이 발생할 수 없고 결과는 -1이 출력되어야 한다. 우리가 구하고 싶은 것은 i 이다. a + ( b * i ) = ( c * i ) 의 순간 손익분기점이 발생한다. a = ( c * i ) - ( b * i ) a = ( c - b ) * i a / ( c - b ) = i 일 때 손익 분기점이 발생하다. 그리고 문제는 손익분기점을 넘겨야 하기 때문에 +1한다. 따라서 코드를 import java.util.Scanner; public class back1712 { public static void main(String[] args) { Scan..