최신 글
기술과 일상을 함께 기록합니다.
[BaekJoon-11052] 카드 구매하기
마지막에 구매한 카드 팩의 크기로 경우를 나누어 최대 지불액 점화식을 만든다. 팩 조합과 계산 순서를 예제로 추적한다.
[BaekJoon-9095]-123 더하기
마지막에 더한 수가 1·2·3인 경우로 나누어 합의 가짓수 점화식을 만든다. 작은 수의 초기값부터 계산한다.
[BaekJoon-11727]-2xN 타일링 2
마지막 폭 2를 채우는 가로 타일 두 장과 정사각형 한 장을 따로 세어 점화식을 만든다. 작은 폭과 나머지 계산을 확인한다.
[BaekJoon-11726]-2xN 타일링
마지막 타일이 세로 한 장인지 가로 두 장인지로 경우를 나누어 점화식을 만든다. 작은 폭을 추적하고 10007로 나눈다.
[BaekJoon-1463] 1로 만들기
작은 수의 최소 연산 횟수부터 채우는 DP로 1 빼기와 2·3으로 나누기를 모두 비교한다. 탐욕 선택의 반례도 확인한다.
5. 다이나믹 프로그래밍(Dynamic Programming)
중복 부분 문제를 저장하는 동적 계획법의 상태·점화식·계산 순서를 피보나치와 LCS로 익힌다.
[BaekJoon-17087] 숨바꼭질 6
시작점에서 각 동생까지의 거리의 최대공약수를 구해 가능한 최대 보폭을 찾는다. 양방향 거리와 한 명인 경우를 다룬다.
[BaekJoon-9613] GCD 합
서로 다른 두 입력 위치의 모든 쌍을 한 번씩 순회하며 GCD를 누적한다. 큰 합계의 정수형 범위도 확인한다.
[BaekJoon-6588] 골드바흐의 추측
에라토스테네스의 체로 소수를 미리 구하고 작은 소수부터 짝을 시험한다. 첫 분해와 실패 출력 조건을 처리한다.
[BaekJoon-1929] 소수구하기
에라토스테네스의 체에서 소수의 제곱부터 배수를 지우고 M부터 N까지 남은 수를 출력한다. 1과 범위 경계를 다룬다.
[BaekJoon-2609] 최대공약수와 최소공배수
유클리드 호제법으로 최대공약수를 구하고 두 수의 곱 관계로 최소공배수를 계산한다. 나머지가 0인 경계를 추적한다.
[BaekJoon-11656] 접미사 배열
문자열의 모든 시작 위치에서 접미사를 만들고 사전순으로 정렬한다. 접미사 개수와 문자열 복사·비교 비용을 따진다.