알고리즘 문제해결전략

6. 무식하게 풀기

• 재귀 호출 - 1부터 n까지의 합을 계산하는 반복 함수와 재귀 함수
• 중첩 반복문 대체하기 - n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
• 보글 게임 (문제 ID: BOGGLE, 난이도: 하)
• 소풍 (문제 ID: PICNIC, 난이도: 하)
• 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)
• 여행하는 외판원 문제를 해결하는 재귀 호출 알고리즘
• 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

7. 분할정복

• 행렬의 거듭제곱을 구하는 분할 정복 알고리즘
• 두 큰 수를 곱하는 O(n^2) 시간 알고리즘
• 카라츠바의 빠른 정수 곱셈 알고리즘
• 쿼드 트리 압축을 해제하는 재귀 호출 알고리즘
• 쿼드 트리 뒤집기 문제를 해결하는 분할 정복 알고리즘
• 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중) - O(n^2) 알고리즘
• 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중) - 분할 정복 알고리즘
• 팬미팅 (문제 ID: FANMETTING, 난이도: 상) - 카라츠바의 빠른 곱셈을 이용해 팬미팅 문제를 해결하는 함수

8. 동적 계획법

• 재귀호출을 이용한 이항 계수의 계산
• 메모이제이션을 이용한 이항 계수의 계산
• 메모이제이션의 사용 예
• 외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하) - 재귀 호출 알고리즘
• 외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하) - 동적 계획법 알고리즘
• 와일드카드 (문제 ID: WILDCARD, 난이도: 중) - 완전 탐색 알고리즘
• 와일드카드 (문제 ID: WILDCARD, 난이도: 중) - 동적 계획법 알고리즘1 - O(n^3)
• 와일드카드 (문제 ID: WILDCARD, 난이도: 중) - 동적 계획법 알고리즘2 - 다른 분해 방법 O(n^2)
• 삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도: 하) - 완전탐색으로 시작하기
• 삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도: 하) - 무식하게 메모이제이션 적용하기
• 삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도: 하) - 동적 계획법 (입력 걸러내기)
• 최대 증가 부분 수열 문제 (문제 ID: LIS, 난이도: 하) - 완전 탐색에서 시작하기
• 최대 증가 부분 수열 문제 (문제 ID: LIS, 난이도: 하) - 동적 계획법 알고리즘1 (입력 손보기)
• 최대 증가 부분 수열 문제 (문제 ID: LIS, 난이도: 하) - 동적 계획법 알고리즘2 (시작 위치 고정하기)
• 합친 LIS (문제 ID: JLIS, 난이도: 하)
• 원주율 외우기 (문제 ID: PI, 난이도: 하)
• Quantization (문제 ID: QUANTIZE, 난이도: 중)
• 타일링 방법의 수 세기 (문제 ID: TILING2, 난이도: 하)
• 삼각형 위의 최대 경로 개수 세기 (문제 ID: TRIPATHCNT, 난이도: 중)
• 우물을 기어오르는 달팽이
• 장마가 찾아왔다 (문제 ID: SNAIL, 난이도: 하)
• 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하) - tiling을 활용해서 풀기
• 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하) - 직접 비대칭 타일링의 수 세기
• 폴리오미노 (문제 ID: POLY, 난이도: 중)
• 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중) - 완전 탐색 알고리즘
• 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중) - 동적 계획법 알고리즘
• 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중) - 동적 계획법 알고리즘2, 반대 방향에서 풀기

9 동적 계획법 테크닉

• 최대 증가 부분 수열 실제로 출력하기
• [여행 짐 싸기 (문제 ID: PACKING, 난이도: 중) - 동적 계획법 알고리즘]
• [여행 짐 싸기 (문제 ID: PACKING, 난이도: 중) - 답 역추적하는 재귀 호출 알고리즘]
• [광학 문자 인식 (문제 ID: OCR, 난이도: 상) - 동적 계획법 알고리즘]
• [광학 문자 인식 (문제 ID: OCR, 난이도: 상) - 실제 답 계산하기]
• [모든 모스 신호를 만드는 완전 탐색 알고리즘]
• [k-1개 건너뛰기]
• [k-1개 건너뛰기 - 좀더 똑똑하게 건너뛰기]
• [k-1개 건너뛰기 - 좀더 깔끔한 구현]
• [k번째 최대 증가 부분 수열 (문제 ID: KLIS, 난이도: 상): LIS의 개수 세기]
• [k번째 최대 증가 부분 수열 (문제 ID: KLIS, 난이도: 상): K번째 LIS 계산하기]
• [드래곤 커브 (문제 ID: DRAGON, 난이도: 중)]

. . .