9번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

● 분할정복 (Divide & Conquer)

어떤 문제가 있을 때, 문제를 나눠서 나눈 문제를 풀고, 푼 결과를 이용해서 우너래 문제를 푼다.

다이나믹과의 차이점 : 다이나믹은 작게 나눈 문제가 중복이 된다. 그래서 중복을 없애기 위해 배열을 사용해 값을 저장한다.(메모이제이션) 그러나 분할정복은 중복이 발생하지 않는다.

 

§ 대표적인 분할정복 알고리즘

• Binary Search
• 퀵 소트
• 머지 소트
• 큰 수 곱셈 (카라추바 알고리즘)
• FFT

 

○ 이분탐색

정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘

시간복잡도 O(logN). 크기가 N인 리스트를 계속해서 절반으로 나누기 때문

L과 R을 설정하고 중간을 M이라 한뒤 잧고자 하는 값이 M보다 작으면 R=M-1, M보다 크면 L을 M+1로 설정한 뒤 다시 찾는 것을 반복한다.

 

상한과 하한

이분탐색으로 구할 수 있다.

상한 : 상한 : 큰 수 중 첫번째 수

하한 : 크거나 같은 수 중 첫번째 수

상한은 수를 찾았으면 나가면 되지만, 하한은 같은 수가 여러개 있을 수 있으니, 좀 더 왼쪽으로 가야한다.

정렬되어있는 배열에서 같은 수가 몇개 있는지도 구할 수 있다.

상한 index에서 하한 index를 빼면 된다.

 

○ 머지소트 (병합정렬)

먼저 최대한 나누고 합치면서 정렬하는 알고리즘

배열 A의 크기가 N, B의 크기가 M일때 합치는데 걸리는 시간은 O(N+M)

원소를 하나씩 비교했으므로 나눌때 logN, 합칠때 logN번 한다.

이때 각각 N이라는 시간이 걸리므로 총 시간복잡도는 O(NlogN)

 

§ 구현

나누는 함수 : sort

합치는 함수 : merge

merge함수 구현

1. 왼쪽 = start, 오른쪽 = mid+1 로 설정
   
2. 각각의 배열을 따로 보고 추가배열을 만들어 값을 거기에 넣는다. 작은 수를 먼저 추가한다.
3. 어느 한쪽의 배열이 남으면 차례대로 붙여넣는다.
   
4. 마지막으로 정렬한 수를 옮겨준다.

 

● 정렬

선택, 버블, 삽입 : N^2

퀵, 힙, 병합 : NlogN

무조건 뒤에 걸 쓰면 된다.

 

○ 언어에 있는 알고리즘을 쓸 때 조심해야될 것

§ C++

sort(first, last)를 오름차순으로 정렬

first부터 last'전'까지 정렬한다.

따라서 A[0]~A[99]까지 정렬하려면 sort(A[0], A[100])을 넣어줘야함

§ JAVA

보통 시간복잡도가 NlogN이 나오나 가끔 N^2이 나온다. => 안사용하면 된다.
Array.sort는 퀵소트로 구현되어있다.

퀵소트는 최악이 N^2이다. 따라서 사용함에 있어 조심해야 한다.

Collection.sort는 머지 소트다.

§ Python은 그냥 sort 함수 사용하면 된다.

 

○ Stable Sorting

같은 것이 있는 경우에 (기준이 같은 때) 정렬하기 전의 순서가 유지되는 정렬 알고리즘을 Stable Sorting 알고리즘이라 한다.

 

○ 퀵소트

최악의 경우에는 O(N^2)이라 잘 사용 안한다.

피벗(pivot)이라는 기준을 하나 정한다음 기준보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 보낸 뒤 다시 왼쪽, 오른쪽에서 각각 정렬한다.

평균적으로는 O(NlogN), 최악의 경우(정렬이 되어있는 경우에 피벗이 첫번째 수)에는 O(N^2)의 시간이 걸린다. 

피벗을 잘 정하면 시간을 줄일 수 있다. 대개 가운데로 정하면 괜찮다.

 

§ 다른방법

퀵으로 정렬하다가 어떤 기준을 넘어가면 다른 정렬 알고리즘(힙)을 쓰는 것 = '인트로 소트'라고 한다.

C++ STL에 있는 sort 함수는 인트로 소트다

 

○ 퀵 셀렉트

정렬되지 않은 리스트에서 k번째 작은 수를 찾는 알고리즘.

퀵소트와 같지만 한 쪽만 호출된다.

따라서 시간복잡도가 O(N)으로 줄어들지만, 최악의 경우에는 O(N^2)이다.

 

△ 하노이 탑 이동순서

※ 대표적인 분할정복 문제

위의 것이 아래 것보다 작아야 한다는 규칙이 중요.

5번 원판이 3번탑으로 가는 과정이 반드시 필요하다.

그리고 그걸 위해선 위의 1,2,3,4 원판이 없어야 한다.

즉, 1,2,3,4 원판을 2번 탑으로 옮겨야 한다.

 

1~5까지의 원판은 1 => 3으로 이동

└  1~4까지의 원판을 1 => 2로 이동

└  5 원판을 1 => 3으로 이동

└  1~4 원판을 2 => 3으로 이동

재귀적인 형태를 띄고 있다.

↓↓↓

1~4 원판을 1 => 2로 이동

└  1~3 원판을 1 => 3으로 이동

└  4 원판을 1 => 2로 이동

└  1~3 원판을 3 => 2로 이동

§ 일반화

1~N 원판을 x=>y로 이동

└  ① 1~(N-1) 원판 x=>z로 이동

└  ② N 원판을 x=>y로 이동

└  ③ 1~(N-1) 원판 z=>y로 이동

 

코드로 구현

① solve(n-1, x, z)

② 그냥 이동

③ solve(n-1, z, y)

 

△ 트리의 순회

인오더와 포스트 오더가 주어졌을 때 프리오더를 구하는 문제

포스트오더에서 마지막에 순회하는 숫자는 루트다.

인오더에서 루트를 기준으로 left와 right를 나눌 수 있다.

이를 이용해 포스트 오더에서 루트를 구하고, 인오더에서 left와 right를 구한다.

다시 이걸 left와 right에서 반복해서 구한다.

 

△ 버블소트

앞에서부터 계속 비교,교환하면서 정렬하는 알고리즘

두가지 문제가 있다.

1. 이 작업을 했을 때 교환을 한 횟수를 구하는 문제

2. 몇단계가 필요한지 구하는 문제

N=10만이라 버블소트로 구할 수는 없다. 머지소트로 풀어야 한다.

 

§ 1번 경우

각 수에 대해 뒤에 그 수보다 작은 수가 몇개나 있는지 세면 된다.

예1)

3 5 2 9가 있다.

머지소트에서 나누고 합치는 과정에서

(3, 5) (2, 9)에서 2가 먼저 이동하는데,

이때 3>2, 5>2를 의미한다.

2	3	5	9
+2	+0	+0	+0

= 2번

예2)

1 5 2 3

(1, 5) (2, 3)

1	2	3	5
+0	+1	+1	+0

= 2번

교환 = 오른쪽 배열에 있던 수가 이동할 때 왼쪽 배열에 수가 몇개 남았는가를 의미

버블소트도 Stable Sorting이라 머지 소트로 풀 수 있다.

 

§ 2번 경우

한 단계에서 뒤에 있는 수가 앞으로 오는 거는 한칸만 가능한데 뒤로 가는거는 얼마든지 가능하다.

아무 방법으로 정렬을 했을 때, 앞으로 몇칸이나 왔는가 세보자

10	1	5	2	3
1	2	3	5	10
+1	+2	+2

따라서 2단계

 

● 이분탐색

이분탐색으로 정답 찾기

- 정답을 구하는 문제

- 가능한지 살펴보는 문제, YES냐, NO냐?

 

다음을 정해야 한다.

1. 가능한 정답의 최솟값

2. 가능한 정답의 최댓값

3. 정답을 하나 결정했을 때, 문제의 조건에 맞는지 검사하는 방법

4. 조건에 맞는 경우 정답을 더 크게 해야할지, 더 작게 해야할지 결정

 

△ 수 이어쓰기 2

N ≤ 1억. 1부터 N까지의 수를 이어붙였을때 새로운 수를 만들 수 있다.

이때, k번째 수가 무엇인지 찾는 문제.

수의 길이를 이용해 구할 수 있다.

k번째가 없다가 나오는 순간을 찾으면 된다.

정답의 최소와 최대를 결정할 필요 없다. 1≤k≤N이다.

이분 탐색으로 N을 결정하고 그때마다 수의 길이를 재보고 K보다 작은지 큰지 비교해서 N을 조정한다.

 

△ 랜선 자르기

랜선 4개

802, 743, 457, 539

랜선을 같은 길이로 잘라서 N개 이상을 만들어야한다.

100cm로 자르면 8+7+4+5 = 24개

300cm로 자르면 2+2+1+1 = 6개

50cm로 자르면 16+14+9+10 = 49개

 

길이 X로 잘랐을 때, N개 이상을 만들 수 있으면 X를 크게 만들어야 한다.

N개 이상을 만들 수 없다면 X를 작게 만들어야 한다.

 

가능한 정답 (위의 경우)

최소 : 1

최대 : 802

 

△ 중량제한

N개의 섬과 M개의 다리로 이루어진 나라

각 다리에는 중량 제한이 있다.

한번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 구하는 문제

 

이분탐색으로 풀 수 있다.

가능한 정답의 최솟값과 최댓값을 구한다.

이동 가능 -> 무게 크게

이동 불가능 -> 무게 작게

최솟값은 1, 최댓값은 간선의 가중치의 최댓값

최소, 최댓값을 정하고 그래프 알고리즘 BFS, DFS 이용해서 이동할 수 있는지 판단

 

△ 기타 레슨

N개의 레슨을 M개의 블루레이에 연속으로 담을때 블루레이 크기의 최솟값 구하는 문제

1	2	3	4	5	6
7	2	6	5	4	8

일때, 

블루레이1 = 7+2+6 = 15

블루레이2 = 5+4+8 = 17

답: 17

→ 어디까지 담을지 변경

블루레이1 = 7+2+6+5 = 20

블루레이2 = 4+8 = 12

답 : 20

최대값의 최솟값을 찾는 문제

크기 K짜리 블루레이로 몇개나 구워야하나 구해서 개수가 N보다 크면 크기를 키워야하고 N보다 작으면 크기를 줄여야 한다.

 

● 수학2

○ a^b

a의 b제곱을 빠르게 구해야한다.

b가 짝수일때 : a^2b = a^b x a^b
b가 홀수일때 : a^(2b+1) = a x a^2b

O(logb)시간이 걸린다.

 

§ 이진수의 원리를 이용하는 방법

방법1

27 = 11011₂

      = 2^0 + 2^1 + 2^3 + 2^4

      = 1+2+8+16 

3^27 = 3^1 + 3^2 + 3^8 + 3^16

3^1 -> 3^2 -> 3^4 -> 3^8 -> 3^16

방법2

b : 27 -> 13 -> 6 -> 3

a : 3^1 -> 3^2 -> 3^4 -> 3^8