[알고리즘설계] 퀵소트의 ‘평균’시간복잡도
[알고리즘설계] 퀵소트의 ‘평균’ 시간복잡도 개요 퀵소트의 시간복잡도는 O(nlogn)으로 알려져있지만, 최악의 경우 O(n^2)일 수있다. 그래서 퀵소트의 ‘평균’ 시간복잡도 를 구해보려 한다. 최악의 경우인 O(n^2)의 상황은 사실 극히 드물다. 피벗의 선택기준...
최근 포스트
[알고리즘설계] Interval Graph - 1 (Scheduling)
[알고리즘 설계] Interval Graph - 1 (Scheduling) 문제 영화배우가 ‘한편의 영화당 촬영의 시작과 끝’ 을 알고 있을 때, 촬영할 수 있는 영화의 최대 개수 를 구하는 문제이다. 구간이 겹치는 영화들은 선택할 수 없다....
[BOJ16234] 인구이동
[BOJ16234] 인구이동 문제링크 문제 설명 처음 필드 한칸 마다 국경선이 존재하고, 나라가 하나씩 존재한다. 필드 한칸에는 그 나라에 살고 있는 인구수가 적혀있다. 인구 이동이 시작되면 아래 그림과 같이 진행된다. (출처: 백준 온라인저지) 더 이...
[BOJ15683] 감시
[BOJ15683] 감시 문제 링크 문제 설명 CCTV는 종류가 5가지가 있고, 각각의 CCTV는 감시할 수 있는 방법이 다르다. 각각의 CCTV를 설치할 때는 회전을 90도로 하며 설치할 수 있다 (그림 출처 : 백준 온라인 저지). ...
[BOJ15685] 드래곤커브
[BOJ15685] 드래곤커브 문제 링크 문제 설명 드래곤 커브는 시작 점, 시작 방향, 세대의 세가지 속성 으로 이루어져있다. 다음 그림은 시작 점이 (0,0)이고 방향이 오른쪽인 0세대이고 길이가 1인 드래곤 커브이다(0세대 드래곤 커브는 길이가 1인 선분...