알고리즘 공부 시작하기 좋은 조합

요즘 든 생각인데, 알고리즘 공부 시작하기 좋은 조합으로

http://www.digitalculture.or.kr/koi/StudyBook.do 에서

"문제해결을 위한 창의적 알고리즘" 책을 받아서 연습 문제 풀이 공부한 후에,

Baekjoon Online Judge (https://acmicpc.net) 에서 문제 풀어 보는 것이네요.

책에서 각 문제별로 상세한 문제 풀이를 하고 있기 때문에 유사한 문제인 경우에 쉽게 응용할 수 있고, (이해를 잘 해야 응용이 가능).

검색 메뉴를 통해서 문제 검색해서 없으면, 알고리즘 분류에서 해당 기법의 문제를 찾아서 풀어 보면 됩니다.


* 책 내용을 설명하는 동영상 강의도 있으니 보시길..
  http://www.digitalculture.or.kr/koi/StudyOnline.do#

* Visual Studio 사용자라면 왼쪽 카테고리에서 [004], [020], [072] 글 보시고 입출력을 편하게 하기 위한 환경 준비하시길..

문제해결을 위한 창의적 알고리즘 - 초급

• 여기에는 풀 문제가 없는 듯

문제해결을 위한 창의적 알고리즘 - 중급

• 42 page 문제 1 최댓값
• 2562번: 최대값 (https://www.acmicpc.net/problem/2562)
• 49 page 문제 2 3의 배수 게임
• ?
• 53 page 문제 3 linear structure search
• 1920번: 수 찾기 (https://www.acmicpc.net/problem/1920)
• sort 만 해주면 동일
• 57 page 문제 4 lower bound
• ?
• 62 page 문제 5 upper bound
• ?
• 77 page 문제 1 두더지 굴(S)
• 2667번: 단지번호붙이기 (https://www.acmicpc.net/problem/2667)
• 거의 비슷한 문제로 dfs 로 풀 수 있다
• 85 page 문제 2 n-queen
• 9663번: N-Queen (https://www.acmicpc.net/problem/9663)
• N size 가 다르나 문제 없음
• 96 page 문제 3 두더지 굴(L)
• dfs 아닌 bfs 푸는 방식을 보여준다
• 100 page 문제 4 미로 찾기
• 2178번: 미로 탐색 (https://www.acmicpc.net/problem/2178)
• 거의 비슷한 문제로 bfs 로 풀기
• 108 page 문제 1 약수의 합 구하기1
• 9506번: 약수들의 합 (https://www.acmicpc.net/problem/9506)
• 약간의 응용.. 합이 n 인지
• 2501번: 약수 구하기(https://www.acmicpc.net/problem/2501)
• 같지는 않지만 약간의 응용(합 대신 몇 번째)만 필요
• 100 억 단위로 커지는 경우
• 258 page 문제 1 약수의 합
• 110 page 문제 2 최댓값(L)
• 2566번: 최댓값 (https://www.acmicpc.net/problem/2566)
• 10818번: 최소, 최대 (https://www.acmicpc.net/problem/10818)
• 비슷한 형식으로 풀 수 문제
• 2562번: 최대값 (https://www.acmicpc.net/problem/2562)
• 비슷한 형식으로 풀 수 문제
• 115 page 문제 3 삼각화단 만들기(S)
• 2622번: 삼각형만들기 (https://www.acmicpc.net/problem/2622)
• N 사이즈가 달라서 완전 탐색은 안 되고, 문제 출처 설명 참고할 것
• O(N) 복잡도로 계산가능
• 121 page 문제 4 고기잡이(S)
• 125 page 문제 5 고기잡이(L)
• 7573번: 고기잡이 (https://www.acmicpc.net/problem/7573)
• 좀 더 복잡한 문제이나, 좌표 기준으로 검색하지 말고, 물고기가 숫자가 작다는 점을 이용해서 물고기별로 가능한 모든 그물을 던지는 방식을 이용하면 된다
• 128 page 문제 6 오목
• 2615번: 오목(https://www.acmicpc.net/problem/2615)
• 134 page 문제 7 연구활동 가는 길(S)
• 10971번: 외판원 순회 2(https://www.acmicpc.net/problem/10971)
• 대략 비슷한 완전 탐색 문제
• 140 page 문제 8 리모컨
• BFS category 문제?
• 146 page 문제 9 오른편 절단 가능 소수
• 2023번: 신기한 소수(https://www.acmicpc.net/problem/2023)
• 152 page 문제 10 minimum sum(S)
• ?
• 157 page 문제 11 앱(S)
• 7579번: 앱(https://www.acmicpc.net/problem/7579)
• 고급편 112 page 참조할 것.. DP 적용 필요
• 161 page 문제 12 치즈
• 2638번: 치즈(https://www.acmicpc.net/problem/2638)
• 2636번: 치즈(https://www.acmicpc.net/problem/2636)
• 좀 더 간단한 형태의 치즈 문제
• 171 page 문제 13 두 색 칠하기 (bicoloring)
• 13265번: 색칠하기 https://www.acmicpc.net/problem/13265
• 비슷한 문제이나, BOJ 의 문제는 아래 내용이 추가가 되어야 합니다.
• TC 를 여러 개 처리할 수 있도록 하고 (변수 초기화 추가), 
• 그래프가 연결되어 있지 않을 수 있어서, 4 가지 상태를 처리해야 합니다.
• 원래 코드의 조건 체크구문에 문제가 좀 있어서 추가 수정이 필요합니다.
• 참고 코드
• 178 page 문제 14 maximum sum(S)
• ?
• 181 page 문제 15 계단 오르기
• 2579번: 계단 오르기(https://www.acmicpc.net/problem/2579)
• N 크기 차이로 DP 적용 필요
• 184 page 문제 16 거스름 돈(S)
• 229번: 동전 2 (https://www.acmicpc.net/problem/2294)
• N 크기 차이로 DP 적용 필요
• 190 page 문제 17 예산 관리
• ?
• 193 page 문제 18 0/1 배낭 문제(S)
• ?
• 208 page 문제 22 전깃줄
• LIS (Longest Increasing Subsequence) 최장증가부분수열 응용문제
• 2631번: 줄세우기(https://www.acmicpc.net/problem/2631)
• N^2 방식 DP 로 가능
• 1365번: 꼬인 전깃줄(https://www.acmicpc.net/problem/1365)
• 2565번: 전깃줄(https://www.acmicpc.net/problem/2565)
• 1365 번, 2565 번은 N^2 시간복잡도를 가지는 알고리즘으로 LIS 를 찾는 코드로 제출시 타임아웃(TLE)발생해서 NlogN 방식으로 변경 필요
• 참고: [최장 증가 수열] LIS http://jason9319.tistory.com/113
• 220 page 문제 23 경찰차
• 2618번: 경찰차(https://www.acmicpc.net/problem/2618)
• 사건의 개수가 완전 탐색으로 해결할 수 없는 숫자로 커지기 때문에 DP 적용 필요
• 226 page 문제 24 좋은 수열
• 2661번: 좋은 수열(https://www.acmicpc.net/problem/2661)
• 232 page 문제 25 경비행기
• 2585번: 경비행기(https://www.acmicpc.net/problem/2585)
• ...
• 238 page 문제 26 돌다리 건너기
• 2602번: 돌다리 건너기(https://www.acmicpc.net/problem/2602)
• 입력값의 범위가 커서 DP 적용 필요
• 243 page 문제 27 공주 구하기
• 2507번: 공주 구하기(https://www.acmicpc.net/problem/2507)
• 입력값의 범위가 더 크다
• 249 page 문제 28 소방차
• 2586번: 소방차(https://www.acmicpc.net/problem/2586)
• 입력값의 범위가 더 크다

문제해결을 위한 창의적 알고리즘 - 고급

• 12 page 예 진법 변환 
• 1212번: 8진수 2진수(https://www.acmicpc.net/problem/1212)
• 11005번: 진법 변환 2(https://www.acmicpc.net/problem/11005)
• 20 page 숫자 뒤집기
• 80 page 숫자 뒤집기(L)
• 5648번: 역원소 정렬(https://www.acmicpc.net/problem/5648)
• 문자를 숫자로 변화 후 정렬해서 출력
• 24 page 문제 2 별 그리기
• 2438번: 별찍기 - 1(https://www.acmicpc.net/problem/2438)
• 29 page 문제 3 combinations(S)
• 11050번: 이항 계수 1(https://www.acmicpc.net/problem/11050)
• 35 page 문제 4 타일채우기(S)
• 149 page 문제 11 타일채우기(L)
• 1793번: 타일링(https://www.acmicpc.net/problem/1793)
• C++ 의 경우에 long long int 를 초과하는 값을 다루는 코드가 필요
• 113 page 문제 6 앱(L)
• 7579번: 앱(https://www.acmicpc.net/problem/7579)
• 131 page 문제 9 색상환
• 2482번: 색상환(https://www.acmicpc.net/problem/2482)
• 171 page 문제 14 경찰차(L)
• 2618번: 경찰차(https://www.acmicpc.net/problem/2618)
• 178 page 문제 15 돌다리 건너기(L)
• 2602번: 돌다리 건너기(https://www.acmicpc.net/problem/2602)
• 191 page 문제 17 공주 구하기(L)
• 2507번: 공주 구하기(https://www.acmicpc.net/problem/2507)
• 207 page 문제 2 두부모판 자르기
• 10937번: 두부 모판 자르기(https://www.acmicpc.net/problem/10937)
• 219 page 문제 1 제자리멀리뛰기
• 6209번: 제자리 멀리뛰기(https://www.acmicpc.net/problem/6209)
• 290 page 문제 3 경비행기(L)
• 2585번: 경비행기(https://www.acmicpc.net/problem/2585)