7번째 수업

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

---

● 그리디 알고리즘 (저번 시간에 이어서~)

△ 보석 도둑

★ 냅색문제 Knapsack

N개의 물건이 있고 각각 무게와 가치가 있을때,

가방의 무게에 제한이 있을 때 담을 수 있는 가치의 최대값을 구하는 문제

 

브루트포스로 풀면 시간복잡도 O(2^N)

다이나믹 프로그래밍으로도 풀 수 있다.

D[i][j]: i번째 물건까지 들어있고, 가방의 무게가 j일 때 최대 가치

i번째 물건을 가방에 넣을 수도 있고 안 넣을 수도 있다.

i번째 보석의 무게 = W[i], 가치 = V[i]

① i번을 가방에 넣지 않을 때, D[i-1][j]가 최대 가치

② i번을 가방에 넣을 때, D[i-1][j-W[i]] + V[i]가 최대 가치

 

그리디로 푸는 방법1

예시1) 보석 3kg이 있는데, 가방이 4kg짜리와 7kg짜리가 있다면 어디에 넣는 것이 좋은가?

- 항상 4kg짜리에 넣는 것이 좋다. 뒤에 어떤 보석이 올지 모르기 때문에 4kg 이하의 보석은 4kg짜리 가방에 담는 것이 좋다.

예시2) 무게가 작은 보석부터 담는 것이 좋을까? 큰 거부터 잡는 것이 좋을까?

- 문제에서는 가격이 큰거를 집는 것이 항상 좋다. 가격순으로 내림차순

1. 어떤 수 x보다 큰 숫자 중에 가장 작은 수를 찾는다. (Lowerbound)

2. 수를 지운다.

시간복잡도 O(NlogK)

 

방법2

후보를 이용하는 방법

----------

가방과 보석을 하나로 합친뒤 무게 순으로 정렬한다.

예시) (1, 23), (2, 99), 2, (5, 65), 10 ....

그런다음 후보를 하나 만들어주고

예시) 후보 : { (1, 23), (2, 99) }  - 이런식으로 들어간다.

그다음 가방이 나오면(2) 2kg 이하의 보석은 다 들어갈 수 있다. 큰 보석이 들어가는 게 더 좋다.

따라서 (2, 99)짜리 보석이 가방에 들어간다. 해당 보석은 후보에서 지워준다.

예시) 후보 : { (1, 23), (5, 65) }  - 가방에 들어간건 빼주고 다른후보 들어옴.

그다음 나온 가방의 무게가 10. 여기에 가치가 큰 65짜리를 넣어준다.

--------- 여기까지가 그리디 알고리즘에서 가장 많이 쓰이는 방법이다.

후보에 넣어줄 수 있고 또 지워줄 수 있어야한다.

따라서 후보를 최대 힙으로 구현해주면 된다. 항상 최대값이 나오므로

시간복잡도 O((N+K)logN)

 

△ 순회강연

d일만에 와서 p만큼의 강연을 해주면 강연료를 지불할 때 얻을 수 있는 최대 강연료

냅색에서 d가 무게 p가 가치라 보면 된다.

다른점은 보석은 무게가 가방의 이하면 되는데, 강연은 데드라인이 d일보다 뒤여야한다.

 

△ 가장 긴 증가하는 부분수열 2

그리디 알고리즘이면 O(NlogN)안에 풀 수 있다.

문제의 답을 다 만들어본다.

{1, 3, 1, 2, 4, 3, 4, 2}이 있으면, {1, 3}을 볼때

1, 3 이 나온다.

다음 중 답이 안되는 것은 '3'. 1은 뒤의 답이 2 이상이지만, 3은 뒤가 4이상이다. 가장 작은 답을 남기고 나머지는 지운다. 3 지워버리고, 1 똑같으니까 지나가고, 2 나오면

후보 {
1
1, 3 (x)
1, 2
2 (x)

}

길이가 같으면 뒤의 수가 작은 쪽만 남긴다.

4 나오면
1
1, 2
1, 4 (x)
1, 2, 4
3 나오면
1
1, 2
1, 3 (x)
1, 2, 3
1, 2, 4 (x)
이렇게 계속 반복

문제는 정답을 항상 다 만들어놓아야 하기 때문에 후보를 너무 많이 유지해야 한다.

 

● 계속해서 문제풀기 시간~(브루트포스와 BFS)

△ 벽 부수고 이동하기

큐에 (행, 열, 벽을 부순 횟수) 이렇게 3가지를 넣어줘야 한다.

답은 D[N][M][0] 또는 D[N][M][1] 둘중 작은 거

벽이 의미없는 곳에 있는 경우 벽을 부수지 않는게 더 나을 수도 있다.

 

△ 벽부동 4

위의 문제와 다른 점은 벽인 곳을 없애보고 이동할 수 있는 최대 칸의 개수를 해당 칸의 위치에 출력한다는 점

최소라는 말이 없기 때문에 DFS도 되고 BFS도 된다.

중복되는 것이 많다. 시간복잡도 O((NM)^2)

먼저 빈칸을 다 그룹지어 놓은 뒤 각 그룹별 크기를 구해놓고, 어떤 벽을 빈칸으로 바꾸었을 때 거기서 이동할 수 있는 최대 칸수를 구하면 된다. 중복되는 칸을 지워버리면 된다. 그러면 시간복잡도 O(NM)

 

△ 아기상어

상어가 먹이를 찾는 것만 BFS인 문제

가장 가까이에 있는 물고기를 찾는데 bfs를 활용

시간복잡도 : BFS : O(N^2)

최악의 경우 모든 칸이 물고기고 상어가 물고기를 다 먹는 경우 : N^2 -> N^4의 시간복잡도가 나온다. N의 제한이 20이라 최악의 경우 16만으로 브루트포스로 풀 수 있다.

 

△ 연구소2

BFS 1번에 N^2의 시간

2의 개수에서 M개를 고르는 시간.

최악의 경우는 2의 개수가 10개. 

최악의 시간 = 2^10

시간복잡도 = O(2^10*N^2) = 1024*2500

바이러스를 놓을 수 있는 칸에 바이러스를 놓지 않으면 그 칸은 빈칸

 

△ 연구소3

연구소3은 바이러스를 놓을 수 있는 위치에 이미 바이러스가 있는데 활성화냐 비활성이냐의 차이. 바이러스가 비활성인 칸은 그냥 빈칸이라고 봐도 된다.

연구소 2문제와는 푸는 방법에서 차이가 난다.

활성일때는 0, 빈칸으로 만들어주고

비활성일때는 해당부분 코드를 지워준다.

 

△ 감시

CCTV의 방향을 결정하는 경우의 수 : 4^8

사각지대를 계산하는데 걸리는 시간 :  벽이 없다면 N+M. 행+열. 그게 C개 있으므로 총 시간복잡도는 4^C*C(N+M)

각각에 대해 기준을 만들어 주면 나머지 방향은 덧셈으로 구할 수 있다. 기준 : 시계방향

1. CCTV의 정보를 모두 빼버림

2. 재귀함수를 이용해 모든 방법을 다 만듬

3. 모든 방법에 대해 실행해보고 사각지대 계산하기

회전을 먼저 처리하지 않고 기준을 정하고 방향을 정해준 다음 돌리는 방식으로 구현

 

△ 주사위 윷놀이

오면체 주사위 : 1~5까지의 수

빨간 화살표가 기본방향

파란 화살표는 파란색 칸에 있을 때는 꼭 파란색 화살표 방향으로 이동해야 한다.

모든 방법을 다 시도

방법의 수 : 말을 이동시키는 횟수 , 4^10

But 지도가 일직선이 아니라 복잡하다. 지도를 저장하는 방법에 대해 생각해봐야한다.

그래프로 저장

각 정점에 마음대로 번호를 매긴 뒤에 이동에 대한 것 처리

항상 하나의 칸은 다른 하나의 칸으로만 이동 가능하므로 그 칸만 저장하면 된다.

까다로운 점이 바로 10번 점수 칸과 같이 지나갈때는 12쪽으로 가는데 머물러 있을 때는 13쪽으로 가는 칸이다.

파란색 화살표는 해당 칸에서 이동을 시작할 때만 의미가 있다.

따라서 해당 칸에서 이동을 시작하는 경우와 아닌 경우로 나눈다.