KOI 정리

문제가 너무 많아서 천천히 추가해나갈 예정

 

★ : 응용 문제가 많은 유형? 알아두면 쓸 데 많아보이는 것들

☆ : 너무 식상하지 않으면서 좀 재밌는 문제? (개인적으로 추천하는 것)

DP는 사실 다 좋은 것 같다.

 

<1996년>

초1: 단지번호붙이기(2667) #DFS

☆초2: 숫자고르기(2668) #사이클

★초3: 직사각형 네개의 합집합의 면적 구하기(2669) #구현 #배열에 마킹

 

★중1: 연속부분최대곱(2670) #브루트포스(N 작음) #DP(N)

중2: 잠수함식별(2671) #오토마타

★중3: 여러 직사각형의 전체 면적 구하기(2672) #좌표압축 #스위핑

 

고1: 잠수함식별(2671)

고2: 교차하지 않는 원의 현들의 최대집합(2673) #DP(N^3)

고3: 삼각퍼즐(2674) #백트래킹   *미해결. 풀 수 있을듯

 

<1997년>

초1: 직각이등변삼각형찾기(2658) #구현(좀 빡셈)

초2: 십자카드 문제(2659) #구현

초3: 회장뽑기(2660) #BFS #플로이드-워셜☆

 

중1: 좋은수열(2661) #백트래킹

★중2: 기업투자(2662) #DP(M*N)(배낭채우기)

중3: 간척지 만들기(2663) #구현+DFS(좀 빡셀듯. N * 좌표범위^2 ?)   *미해결

 

고1: 다각형의 확장(2664) #구현(좀 빡셀듯)   *미해결

☆고2: 미로만들기(2665) #그래프로 바꿔 풀기+BFS #다익스트라

★고3: 벽장문의 이동(2666) #DP(2^N * M. 쿼리 번호와 문 열렸는지를 상태값으로)

 

<1998년>

초1: 교차점개수(2650) #구현(96년 고2에서 교차 판별하는 방법 사용하면 될듯? 예전의 나는 1차원으로 핀듯)   *다시풀기

초2: 자동차경주대회(2651) #DP(N^2)

초3: 블록맞추기(2652) #구현(공포)

 

중1: 안정된 집단(2653) #그래프

중2: 연결 사각형(2654) 몰?루 백트래킹+가지치기로 되나 이게

중3: 가장높은탑쌓기(2655) #DP(N^2)역추적