KMP : 크누스 - 모리스 - 프랫 어쩌구. 이전 단계에서 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘 불일치가 발생하기 직전까지 같았던 부분은 다시 비교하지 않고 패턴 매칭을 진행 비교 횟수를 줄여, 검색 알고리즘의 효율성을 높임 검사 부분 내에 패턴의 일부와 동일한 부분이 있는지 판단 그 위치만큼 밀기 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구해, 패턴의 이동을 최대한 크게 한다. KMP 테이블 생성 패턴과 패턴을 서로 겹치도록 맞추고 검사를 시작할 곳을 테이블에 작성한다. 미리 나온 패턴에 대해 겹치는 부분이 있는 지 검사한다. KMP 법에서 사용하는 패턴 문자열 만들기 접두사 배열과 접미사 배열..

최대공약수 math 내장 함수 사용하기 math.gcd(n, m) 유클리드 호제법 | a와 b 의 최대공약수는 (a를 b로 나눈 나머지)와 b 의 최대공약수와 같다. # a a) : a,b = b,a while(b!=0): a=a%b a,b=b,a 큰 수를 작은 수로 나누고 나누어 떨어질 때까지 계속 반복 최소공배수 math 내장 함수 사용하기 math.lcm(n, m) python 3.9부터 지원된다! 직접 구현하기 import math def lcm(a,b): return (a * b) // math.gcd(a,b)

Programmers. 거리두기 확인하기 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr [파이썬(python) - DFS & BFS] 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 ..

에라토스테네스의 체 다수의 자연수에 대하여 소수 여부를 판별 1. 2부터 N까지의 모든 자연수를 나열한다. 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.) 4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 이후 남아있는 수들은 모두 소수가 된다. python 구현 코드 import math n = 1000 array = [True for _ in range(n + 1)] # 소수일 경우 True, 소수가 아닐 경우 False로 표현 for i in range(2, int(math.sqrt(n)) + 1): if array[i] == True: j = 2 while i * j m c. a >..

최단 경로(Shortest Path) 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로 구하기 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 간선 간의 가중치가 있을 경우 활용 그리디, DP의 한 유형 다익스트라(Dijkstra) 특정 한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 ⭐️ 음의 간선이 없는 경우 사용 현실 세계의 프로그래밍을 할 때 많이 사용 매 상황 가장 비용이 적은 노드를 선택하므로 그리디 알고리즘으로 분류하기도 한다. 한번 방문한 노드일 경우 이후에 해당 노드에 대해 최단 경로가 다시 갱신되는 일은 없다. 1. 출발 노드 설정 2. 최단 거리 테이블 초기화(기본 무한) 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4. 해..

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Baekjoon 1629. 곱셈 [파이썬(python) - 분할정복] 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 입력 예시 10 11 12 출력 예시 4 ❧ 정답 🔎IDEA) 분할정복 완전탐색 풀이 : 시간초과 발생 짝수 일 경우..

11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net Baekjoon 11727. 2xn 타일링 2 [파이썬(python) - DP] 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 입력 예시 2 출력 예시 3 ❧ 정답

1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net Baekjoon 1072. 게임 [파이썬(python) - 이분 탐색] 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다. 이제 형택이는 앞으로의 모든..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net Baekjoon 2630. 색종이 만들기 [파이썬(python) - 분할 정복] 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 ..