8번째 수업

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

---

△ 파이프 옮기기

사실 다이나믹 문제인데 방법의 수가 100만 가지라 브루트포스로 풀어도 된다.

방법1 : 양쪽 끝점을 기록하는 방법 (r1, c1) (r2, c2)

방법2 : 한쪽끝과 방향을 저장하는 방법 (r, c), 방향

이 문제에서는 방향이 상당히 중요하기 때문에 2번 방법이 더 좋다.

한쪽 점과 방향을 알고 다른  끝점을 아는 것보다 양 끝점을 알고 방향을 계산하는게 더 오래걸린다.

이동방향 쪽에 있는 점을 저장하는 것이 더 낫다.

 

△ 게리맨더링2

사실 이건 문제를 아직 다 이해를 못했다...

크기 NxN인 격자 모양의 도시를 5개의 선거구로 나누는 문제

이때, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구차이의 최솟값을 구하는 문제

선거구를 만들때는 하나를 선택해서 문제에 나와있는 방법 그대로 구현하면 된다.

1. 선거구를 나눔

기준점 : N^2개, d1: N, d2: N

시간복잡도 O(N^4)

2. 인구차이를 구하기 - 전체를 순회해야 한다. O(N^2)

따라서 총 시간복잡도 O(N^6)

 

△ 계란으로 계란치기

왼쪽부터 차례로 계란을 들어서 다른 계란을 깨는 최대 개수

시간복잡도 O((N-1)^N)

N이 8이므로 모든 경우를 다 해볼 수 있다.

조건

1. 깨지지 않은 다른 계란 하나를 친다.

2. 손에 든 계란이 깨졌거나

3, 깨지지않은 다른 계란이 없으면 내려논다.

 

△ 두 동전

둘 중에 한 동전만 떨어트리는 문제

10번 이상 누르면 무조건 -1 출력

보드판의 정보는 변하지 않는다.

두 동전의 위치 저장

4^10가지 경우

- 두 동전이 모두 떨어지거나

- 하나만 떨어지거나

- 10번이 넘었거나

벽일경우에 이동하지 않는 조건 처리

 

△ 에너지 모으기

시간복잡도 O((N-2)!)

N개의 구슬에서 양 끝을 제외하고 1개를 골라 없앤뒤 양 끝값을 곱한값이 에너지

이 문제는 계란 처럼 제외하는 구슬을 아예 빼버릴시 이전 단계로 돌아가기 쉽지 않다

전체를 배열에 담아서 재귀를 돌린다.

 

△ 배열돌리기4

돌리는게 어렵다

값을 구하는 건 순서를 다 정하고 구하면 된다.

배열 회전이 어렵다

시간복잡도 O((N-2)!)

비슷한 문제로 달팽이 1, 2가 있다.

 

● 문자열 알고리즘

Aho-corasick

N개의 문자열에서 패턴 P를 모두 찾는것 (KMP+Trie)

fail의 인덱스가 트라이의 노드가 된다

노드를 노드의 suffix에 연결

BFS를 이용해 탐색. 길이순으로 연결되어있음

 

△ 체스판 위의 공

문제 : 인접한 8방향에 적힌 모든 정수 중 가장 적은 정수가 있는 칸으로 이동한다. 체스판 각 칸 위에 공을 올려 놓고 이동시킨다. 공이 더이상 이동하지 않을때, 각 칸에 공이 몇개 있는가

칸의 개수가 NM, 한칸에서 도착점을 찾는데 걸리는 시간이 O(NM)

총 O((NM)^2)

 

★ 경로압축

모든 점을 다 구할 필요 없다.

예를 들어 29에서 시작해서 어디로 가는지 알고있다면, 36에서 시작해서 29를 만나면 더이상 진행할 필요가 없다.

모든 칸을 한번씩만 방문하게 된다.

이를 경로압축(Path Compression)이라 한다.

 

★ 좌표압축

LIS문제에서
A = [10, 20, 10, 30, 20, 50]가 있을때

LIS에서는 수의 크고작음만 중요하다. 실제 수는 안중요하다.

10->1, 20->2, 30->3, 50->4. 이런식으로 수를 우선순위로 바꿈

수의 크기제한을 없앨 수 있다.

 

△ 배열 B의 값

배열의 값 : 배열의 모든 원소를 합한 값

임의의 두행 또는 두 열을 위치 교환 했을때, 최대가 되는 배열값을 구하는 문제

배열 B를 만드는 시간 O(NM)

배열 B의 값을 구하는 시간 O(NM)

총 O(NM) => N^2

행을 2개 고르는 방법 : O(N^2)

열을 2개 고르는 방법 : O(M^2)

N^2*M+M^2*N => N^3

총 O((N^2+M^2)NM) = O(N^4)

 

배열 B는 실제로 만들 필요 없다.

만들어서 값을 구하면 버린다.

만들지 않고 값만 잘 구하면 된다. 그러나 시간의 이득은 없다.

 

방법의 수를 줄여보자.

배열A가 있을 때 배열B를 구할때, 각각 몇번 더했는지 보면, 

A[1][1]은 1번, A[1][2]는 2번... 즉, ∑A[i][j]*C[i][j]

2번 열과 3번열을 바꾸는 것은 의미가 없다. 더해지는 횟수가 같다

1번행과 i번 행을 바꾸는것 또는 N번 행과 i번행을 바꾸는 것만 의미가 있다. 열도 마찬가지

정답에 영향을 줄 수 있는건 N가지와 M가지

방법이 줄어들면 가지수= O(NM + MN) = O(N^2)

총 O(N^3)

 

더 줄일 수 있다.

1번 행과 i번 행을 다 바꾸는 게 아니라 합의 차이가 가장 큰행만 바꿔보자

그럼 가지수가 N가지에서 1가지로 변한다.

그러면 총 4가지가 된다. O(N^2)

 

△ 돌 그룹

돌이 각각 A, B, C개 있을 때 돌 개수를 같게 만들 수 있는가?

(A, B, C)의 경우의 수는? 500^3? 각 그룹에서 돌의 최대 개수는 1000개

그럼 경우의 수가 1000의 세제곱이 되는데 이거는 너무 크다.

하지만 실제로 1000의 세제곱이 되지 않는다.

돌의 합이 항상 고정되어 있기 때문에 그렇게 큰값이 나오지 않는다.

 

A, B를 알면 C를 자동으로 알수 있다.

그럼 경우의 수는 1000^2가지가 되고, 풀수있다.

BFS, DFS 둘 다 풀 수 있다.

 

맨처음 돌의개수 = {x, y, sum-x-y}

작은수, 큰수 구해서 돌 개수 바꿔주고, 재귀함수 돌리기

check[sum/3][sum/3]을 방문한 적 있으면 가능하단 뜻

 

△ 적록색약

DFS, BFS

색약인 사람일때와 아닐때 구역 개수 구하기

 

방법1

입력정보 가지고 BFS/DFS로 구역 개수 구하기

입력정보 변경

다시 BFS/DFS로 구역 개수 구하기

방법2

구역 개수를 구할 때 조건을 바꿔서 R과 G를 같다고 놓고 두번 구하기

조건검사를 함수로 빼서 검사

 

※ 문제풀때 많이 틀리는 이유

1. 

문제 보고 -> 코드 짜서 -> 제출했을때, -> 주로 틀린다.

이때, 틀린 데이터를 구하는 방법

1 ≤ N ≤ 100000

예시에 N이 1, 3, 4, 10일때,

주로 N이 5일때, 7일 때 데이터를 많이 넣어보는데

실제로 틀리는 경우는 N이 1 또는 100000, 즉 끝값일때 많이 일어난다.

 

2. 

테스트 케이스 방식의 문제를 풀때,

테스트 케이스 개수가 주어지고, 밑에 그만큼 경우가 주어지는 문제

테스트 케이스의 순서를 바꿔보면 가끔 답이 제대로 안나올 때가 있다. (주로 오름차순으로 주어진다.)

변수값이 제대로 초기화가 안되서 그렇다

테스트케이스 문제에서 초기화가 제일 중요하다.

 

3. 

브루트포스 함수를 조건문에 넣으면 여러번 호출하게 된다.

그럴때는 따로 변수에 결과값을 받아서 넣어주는 게 좋다.

많이들 시간초과를 받는 이유 중 하나.

if(ans < go(index+1)) {
	ans  = go(index+1) 
}

비슷한예로 문자열의 길이

for(i=0; i<strlen(s); i++) 

에서 strlen함수가 시간복잡도 N이라면 이코드에서는 N번 돌아가므로 N^2이 된다.

 

4. 

자바에서 문제가 생기는 경우 (C++도)

피보나치 수열에서 배열을 만들때 

D = new int[N] 
D[1]=1; 
D[2]=1; 
for(i=3; i<=N; i++) {
	D[i] = D[i-1] + D[i-2];
}

이경우에 만약 N이 2라면 런타임 에러가 일어난다.

C++은 간혹 배열 범위를 넘어가도 실행이 되는 경우가 있는데 자바는 그런거 없다.

 

5. 

오버플로우

1, 2, 3 더하기 3 문제에서

d[i] = d[i-1]+d[i-2]+d[i-3]

을 1억9로 나눈 값을 구해야하는데

d를 int로 바꾸면 d[i-1]+d[i-2]+d[i-3]를 다 했을때 int 범위를 넘어갈 수 있다.

2번 더하는 것까지는 괜찮지만 3번 더하면 넘어간다.

d[i] = ((d[i-1]+d[i-2])%mod)+d[i-3])%mod

를 하면 된다.

그래서 큰값을 넣어봐야 한다. 이상한 값이 나오면 오버플로우가 발생한다는 것을 알 수 있다.

 

6. 

테스트케이스 문제에서 불가능하면 -1을 출력하는 코드를 짤때

프로그램을 종료시키는 코드를 짜면 안된다.

이때 테스트 케이스 문제일 때 순서를 바꿔서 넣어보면 중간에 종료가 되는 걸 알 수 있다.