[알고리즘] 그리디 문제

그리디 개념 :: https://ujink.tistory.com/10

(18/50)
ATM
동전 0
회의실배정 ( 괜춘한 문제)
거스름돈
로프
30 ( String vs Stringbuffer)
대회 or 인턴 
문자열
신입 사원
기타줄

잃어버린 괄호
행렬(next() vs nextLine()) 0000 vs 0 0 0 0 차이 
도체 설계 LIS(최장증가수열구하)dp- https://mygumi.tistory.com/69,
                                           https://dyngina.tistory.com/16?category=339178
부등호
병든 나이트
한 줄로 서기
저울
멀티탭 스케줄링
궁금한 민호
수리공 항승

https://whereisusb.tistory.com/250?category=746475
생각하는

한국정보올림피아드(KOI) 문제 정리

전에 한국정보올림피아드에 있는 교재를 정리한 적이 있는데,
http://gooddaytocode.blogspot.kr/2016/03/blog-post.html

한국정보올림피아드 기출문제가 연도별로 정리되어 있고
문제별로 간단한 설명과 정답 코드(아쉽게도 없는 것도 있다)가 있는 것을 알게 되어 우선
이 문제부터 풀어보려고정리를 시작했는데...

먼저, BOJ 에서 풀어보고 해설과 정답을 참고하도록 하면 배울 점이 많네요.

기출문제 주소

https://www.digitalculture.or.kr/koi/selectOlymPiadDissentList.do

BOJ Category

지역본선: https://www.acmicpc.net/category/57
전국본선: https://www.acmicpc.net/category/55

지역예선 기출문제

• 초등부
• 문제풀이 없음
• 중등부
• 풀이문제 없음
• 고등부
• 풀이문제 없음

지역본선 기출문제

• 초등부
• 2016
• 
  
• 2015
• 문제1: 10부제 (https://www.acmicpc.net/problem/10797)
• 문제2: 세로읽기 (https://www.acmicpc.net/problem/10798)
• 문제3: 쇠막대기 (https://www.acmicpc.net/problem/10799)
• 문제4: 컬러볼 (https://www.acmicpc.net/problem/10800)
• 2014
• 문제1: 과자 (https://www.acmicpc.net/problem/10156)
• 문제2: 자리배정 (https://www.acmicpc.net/problem/10157)
• 문제3: 개미 (https://www.acmicpc.net/problem/10158)
• 문제4: 저울 (https://www.acmicpc.net/problem/10159)
• 2013
• 문제1: 그릇 (https://www.acmicpc.net/problem/7567)
• 문제2: 덩치 (https://www.acmicpc.net/problem/7568)
• 문제3: 토마토 (https://www.acmicpc.net/problem/7569)
• 문제4: 줄 세우기 (https://www.acmicpc.net/problem/7570)
• 문제5: 점 모으기 (https://www.acmicpc.net/problem/7571)
• 2007
• 문제1: 최대값 (https://www.acmicpc.net/problem/2562)
• 문제2: 색종이 (https://www.acmicpc.net/problem/2563)
• 문제3: 경비원 (https://www.acmicpc.net/problem/2564)
• 문제4: 전깃줄 (https://www.acmicpc.net/problem/2565)
• 문제5: 비숍 (https://www.acmicpc.net/problem/1799)
• 중등부
• 2016
• 
  
• 2015
• 문제2: 초등부 문제3
• 2014
• 문제1: 초등부 문제2
• 문제2: 초등부 문제3
• 문제3: 초등부 문제4
• 문제4: 암호 (https://www.acmicpc.net/problem/10160)
• 고등부
• 2016
• 
  
• 2015
• 2014
• 문제1: 중등부 문제1
• 문제2: 중등부 문제3
• 문제3: 중등부 문제4
• 문제4: 톨게이트

전국본선 기출문제

• 초등부
• 2016
• 문제1: 방배정 ()
• 문제2: 타일 ()
• 문제3: 리조트 ()
• 문제4: 장애물 ()
• 2015
• 2014
• 문제1: 전자레인지 (https://www.acmicpc.net/problem/10162)
• 문제2: 색종이 (https://www.acmicpc.net/problem/10163)
• 문제3: 격자상의 경로 (https://www.acmicpc.net/problem/10164)
• 문제4: 버스 노선 (https://www.acmicpc.net/problem/10165)
• 2013
• 문제1: 올림픽 (https://www.acmicpc.net/problem/8979)
• 문제2: 택배 (https://www.acmicpc.net/problem/8980)
• 문제3: 입력숫자 (https://www.acmicpc.net/problem/8981)
• 문제4: 수족관 1(https://www.acmicpc.net/problem/8982)
• 중등부
• 2016
• 문제1: 초등부 문제1
• 문제2: 주유소 ()
• 문제3: 트리 ()
• 문제4: 레이저센서 ()
• 2015
• 2014
• 문제1: 초등부 문제3
• 문제2: 관중석 (https://www.acmicpc.net/problem/10166)
• 문제3: 초등부 문제4
• 문제4: 금광 (https://www.acmicpc.net/problem/10167)
• 2013
• 문제1: 사냥꾼 (https://www.acmicpc.net/problem/8983)
• 문제2: 초등부 문제3
• 문제3: 막대기 (https://www.acmicpc.net/problem/8984)
• 문제4: 수족관 2 (https://www.acmicpc.net/problem/8985)
• 고등부
• 2016
• 문제1: 초등부 문제3
• 문제2: 중등부 문제2
• 문제3: 중등부 문제3
• 문제4: 먼 별 ()
• 2015
• 2014
• 문제1: 중등부 문제2
• 문제2: 중등부 문제3
• 문제3: 파발마
• 문제4: 안전한 비상연락망
• 2013
• 문제1: 중등부 문제1
• 문제2: 중등부 문제3
• 문제3: 전봇대 (https://www.acmicpc.net/problem/8986)
• 문제4: 수족관 3 (https://www.acmicpc.net/problem/8987)

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

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

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

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

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

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

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


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

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

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

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

• 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)
• ?
• 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)

알고리즘을 어떤 순서로 공부해야 할 지 모르는 분들께

알고리즘을 어떤 순서로 공부해야 할 지 모르는 분들께

라는 백준님의 글입니다.

출처: https://www.acmicpc.net/board/view/5557

참고를 위한 요약 버전

1. 알고리즘과 입/출력

알고리즘을 공부하는 방법

시간 복잡도

입/출력을 받는 방법

2. 자료구조 1

스택

큐

덱

문자열 

3. 다이나믹 프로그래밍 1

4. 수학 1

나머지 연산

최대 공약수와 최소 공배수

소수

소인수분해

진법 변환

팩토리얼 

5. 정렬

STL의 sort를 응용하는 방법

O(NlgN) 정렬 알고리즘

퀵 소트와 머지 소트는 '분할 정복' 챕터

힙 소트는 '자료구조 2' 챕터 

6. 그래프 1

그래프를 저장하는 방법 세 가지 - 인접 행렬, 인접 리스트, 간선 리스트

인접 리스트: 시간과 공간이 더 효율적

효율적인 알고리즘 구현을 위해서 STL의 vector를 사용해서 인접 리스트를 구현

간선 리스트라는 자료구조

그래프의 탐색 - DFS / BFS

DFS와 BFS의 응용 - 연결 요소 / 이분 그래프

그래프에서 가장 중요한 것 => 문제를 그래프로 모델링

그래프 모델링을 연습하기 위해서 사이클을 찾는 연습

이차원 배열 상에서 플로드 필 알고리즘

7. 트리 1

트리를 순회하는 방법: 프리 오더, 인 오더, 포스트 오더

그래프와 마찬가지로 트리를 저장하는 방법 세 가지

트리의 부모에 대한 내용과 트리의 지름

8. 그리디 알고리즘

어렵지만 풀 수 있다

증명이 중요

잘하는 방법은 다양한 문제를 푸는 것 

9. 분할 정복

문제를 분할한 다음 합쳐서 문제를 푸는 알고리즘

대표: 이분 탐색 알고리즘 / 머지 소트 / 퀵 소트

가장 가까운 두 점을 찾는 방법: 분할 정복 알고리즘의 하이라이트

10. 이분 탐색으로 정답 찾기

정렬된 리스트에 어떤 수가 있는지 없는지를 조사하는 알고리즘

주로, 정답을 구하기는 어려운데 정답을 검증하기 쉬운 경우에 이 알고리즘을 사용 

11. 완전 탐색 1 (모든 경우 다 해보기)

여섯 가지

• 부르트 포스(Brute Force)
• N중 for문을 이용해서 문제를 푸는 방법
• 순열을 이용해서 모든 경우를 중복 없이 다 해보는 방법
• 가장 중요한 알고리즘 중의 하나인 BFS를 이용해서 모든 경우를 다 해보는 방법
• 재귀 호출을 이용해서 백트래킹
• 비트마스크를 이용해서 모든 경우를 중복 없이 다 해보는 방법

12. 완전 탐색 2

정답이 될 수 있는 것만 다 해보는 (일부 경우만 다 해보는) 알고리즘

완전 탐색 1에서 배운 BFS를 덱을 사용해서 하는 방법

탐색의 규모가 너무 큰 경우에 문제의 크기를 절반으로 나누어서 푸는 중간에서 만나는 알고리즘 (Meet in the Middle) 알고리즘

13. 자료구조 2

스택을 조금 더 화려하게 사용

그래프 알고리즘 중에서 크루스칼을 배울 때 필요한 Disjoint-set

비트마스크

힙 - 최대 힙과 최소 힙 / 힙을 구현, 힙 소트

이진 검색 트리 (BST)

14. 다이나믹 프로그래밍 2

15. 수학 2

다른 문제를 풀 때 필요한 경우가 많아서 배우는 부분

a^b 제곱 연산

• 분할 정복 알고리즘을 이용해서 구하는 방법
• 이진수의 원리를 이용해서 구하는 방법

행렬

피보나치 - 피보나치 수를 구하는 다양한 방법, 피사노 주기, 피보나치 수의 다양한 성질, 피보나치 수를 행렬을 이용해서 구하는 방법

이항 계수 - 파스칼의 삼각형

카탈란 수

오일러 피 함수

두 수를 나눌 때, 나머지 연산을 어떻게 해야하는지 배움

확장 유클리드 알고리즘

순열 - 다음 순열 / 이전 순열 / 모든 순열 / 순열의 순서

16. 그래프 알고리즘 2

위상 정렬

최소 스패닝 트리 (MST) - 프림 / 크루스칼

최단 경로 알고리즘 -벨만 포드 알고리즘 / 다익스트라 알고리즘 / 플로이드 와샬 알고리즘

17. 트리 2

가장 가까운 공통 조상(LCA) - 직관적 구현 / 다이나믹 프로그래밍

임의의 두 정점 사이의 거리를 BFS 알고리즘보다 빠르게 구하는 방법

18. 구간의 최소값 구하기

그냥 다 해보는 방법

이차원 배열에 저장해서 구하는 방법

루트 N으로 나눠서 구하는 방법 (sqrt decomposition)

다이나믹 프로그래밍을 이용해서 구하는 방법

세그먼트 트리를 이용해서 구하는 방법

슬라이딩 윈도우 알고리즘 

19. 구간의 합 구하기

누적합을 이용

세그먼트 트리를 이용

펜윅 트리(바이너리 인덱스 트리)를 이용

구간을 업데이트하는 경우: 세그먼트 트리 나중에 업데이트 하기 (Segment Tree Lazy Propagation)

세그먼트 트리

BIT 

20. 세그먼트 트리 활용하기

구간의 최소값과 합을 구할 때 사용

분할 정복과 함께 세그먼트 트리를 사용

최소값을 찾는 방법을 이용해서 K번째를 찾는 방법 

21. 다이나믹 프로그래밍 3

비트마스크를 이용해 상태를 나타내고 그 상태를 다이나믹에 이용

한 문제를 5가지 서로 다른 점화식으로 풀기

22. 네트워크 플로우

네트워크 플로우: 가장 중요한 알고리즘

최대 유량을 구하는 두 가지 알고리즘 - Ford-Fulkerson / Edmond-Karp

이분 매칭, 민 컷, 최소 버텍스 커버, 최대 독립 집합

그래프 모델링을 연습

23. 최소 비용 유량 (MCMF)

최대 유량 문제에서 최소 비용문제가 추가되면 최소 비용 유량 문제

그래프 모델링하는 연습

24. 그래프 알고리즘 3

오일러 회로를 구하는 방법

강한 연결 요소 (SCC)을 구하는 Kosaju's Algorithm과 Tarjan's Algorithm

DFS Tree

Tarjan's Algorithm 을 응용해 단절점과 단절선을 구하는 방법

2-SAT 문제 

25. 다이나믹 프로그래밍 4

트리 다이나믹

왼쪽과 오른쪽을 왔다갔다 하면서 푸는 다이나믹

다이나믹 점화식을 통해서 정답을 역추적하는 방법

확률 다이나믹

왼쪽과 오른쪽에서 시작해서 가운데로 모이는 다이나믹

26. 문자열 알고리즘

문자열 매칭 알고리즘: KMP, Trie, Aho-corasick, Suffix Array

27. 기하 알고리즘

원, 직선, 선분과 같은 도형에 대한 내용

다각형에 대한 내용

CCW 알고리즘: 선분의 교차를 판별하는 방법

어떤 점이 다각형의 내부에 있는지 아닌지, 다각형의 넓이를 구하는 방법

볼록 껍질(Convex Hull)을 구하는 방법인 그라함 스캔(Graham Scan)

라인 스위핑 알고리즘(Line Sweeping Algorithm) - 가장 가까운 두 점

로테이핑 캘리퍼 알고리즘(Rotating Calipers) - 가장 먼 두 점

겹치는 선분 문제

직사각형 N개의 합집합 

28. 알고리즘 게임

조합 게임(Combinatorial Game) 문제 중에서 Impartial Game 문제를 푸는 방법 

돌 게임(Subtraction Game)

님 게임 (Nim Game)

The Sprague-Grundy Function을 이용해 조합 게임 문제를 푸는 방법

다양한 님 게임 변형 문제의 Grundy Number