4번째 수업

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

---

● 브루트포스 - 백트래킹

백트래킹은 브루트포스의 유형 중 하나다. 브루트포스가 모든 방법을 다 시도하는 것이라면 백트래킹은답의 가능성이 없으면 더이상 호출하지 않고 잘라버리는 것(커팅)이다.

 

△ 문제 - 부등호

문제 : 부등호 기호 <와 >가 나열된 수열 A가 있다. 기호의 앞 뒤에 한자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 이때, 선택된 수는 모두 달라야한다. k개의 부등호 관계를 모두 만족시키는 (k+1)개 자리의 정수 중 최대값과 최소값을 구하는 문제

 

방법1

1. 수를 채운다.

2. 부등호 관계를 만족하는 지 검사

방법의 수 : (k+1)!개

시간 복잡도 O((k+1)!*k)

 

방법2

위의 방법은 부등호 기호를 만족하는지 마지막에 검사를 한다. 함수의 호출 중간에 정대로 정답이 될 수 없는 경우를 발견하면 그 뒤의 호출은 더 이상 진행하지 않아도 된다.

 

△ 문제 - 맞춰봐

문제 : -10부터 10까지 N(1≤N≤10)개의 정수로 이루어진 수열 A가 있다. S[i][j] = A[i]+A[i+1]+...+A[j]가 0보다 크면 +, 작으면 -, 같으면 0. S가 주어졌을때 가능한 A를 아무거나 찾는 문제.

 

방법1

21개의 수를 10개의 자리에 넣어야한다.

총 경우의 수 : 21^10 = 16,679,880,978,201

시간초과

 

방법2

-10부터 10까지 다 돌아보지 말고 부호에 따라 '+'면 1~10, '-'면 -10~-1, '0'인 경우에는 0능 넣는 방식으로 계산

시간초과

 

방법3

모든 기호를 먼저 검사하고 돌아보기

S[k][index] (0≤k≤index)를 재귀함수 go(index)에서 검사

함수의 호출 중간에 정대로 정답이 될 수 없는 경우를 차단

 

● 브루트포스 - 순열

모든 순서를 다 살펴봐야 할때 사용한다. 그러나 느리다

1. 첫 순열 만들고

2. 다음 수열을 만드는 함수 구하기

C++이면 STL의 함수 next_permutation, prev_permutation를 사용하면 간단하다.

 

다음 순열

사전적으로 다음에 오는 순열을 찾는 방법

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.

2. j≥i이면서 A[j]>A[i-1]을 만족하는 가장 큰 j를 찾는다.

3. A[i-1]과 A[j]를 swap한다.

4. A[i]부터 순열을 뒤집는다.

시간복잡도 O(N)

 

△ 문제 - 외판원 순회 2

영어로 Travelling Salesman Problem(TSP)이라고 한다.

문제 : 1번부터 N번까지 번호가 매겨져 있는 도시가 있다. 한 도시에서 시작해 N개의 모든 도시를 거쳐 다시 원래 도시로 돌아오려고 한다. 한 번 갔던 도시는 다시 갈 수 없다. 이때, 가장 적은 비용을 구하는 문제.

 

방법

2≤N≤10이므로 시간복잡도는 O(N*N!)이다. 모든 경우를 다해봐도 된다.

첫 순열부터 마지막 순열까지 모든 비용을 계산해 최소값을 출력한다.

 

● 브루트포스 - 비트마스크

비트마스크 : 변수 하나로 많은 데이터를 저장 가능

정수로 집합에 관한 정보를 넣는다. 보통 0부터 N-1까지 정수로 이루어진 집합을 나타낼때 사용한다.

예) {1, 3, 4, 5, 9} = 570 = 2^1+2^3+2^4+2^5+2^9

전체집합 : (1 << N) -1

공집합 : 0

기본 연산 : 추가, 검사, 제거 

추가 : S | (1 << i)

검사 : S & (1 << i)

제거 : S & ~(1 << i)

토글 : S ^ (1 << i)

비트연산을 사용할 때는 연산자 우선순위를 생각해야 한다.

 

△ 문제 - 부분수열의 합

문제 : 서로 다른 N개의 정수의 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제

모든 부분수열의 개수 = 2^N (1≤N≤20)

 

방법

전체집합=(1<<N)-1

크기가 0인 부분수열은 제외

집합에 무엇이 포함되어있는지 확인

 

△ 문제 - 수들의 합 2

문제 : N개의 수로 된 수열 A[1], A[2], ..., A[N]이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+...+A[j]가 M이 되는 경우의 수를 구하는 문제

총 3가지 시간복잡도로 해결할 수 있다.

 

방법1

A[i]+A[i+1]+...+A[j] == M이 되는 (i, j)쌍을 찾는 문제와 같다.

i를 정하고, j를 정하고, 합을 계산하면 O(N^3)로 계산할 수 있다.

 

방법2

i=a, j=b인 경우의 합과 i=a+1, j=b인 경우의 차이는 A[b+1]밖에 없다.

합을 계산할 때, 합을 각각의 i에 대해서 누적하면 O(N^2)로 계산할 수 있다.

 

방법3

각각 i=a, j=b인 경우와 i=a+1, j=b인 경우에 대해 생각해 봤을때,

A[a]+A[a+1]+...+A[b] < M

A[a]+A[a+1]+...+A[b]+A[b+1] > M

이 경우, j를 계속 증가시키는 것은 의미가 없기 때문에 i를 증가시켜야 한다.

즉, sum이 sum<M에서 sum>M이 되는 순간에 i를 증가시킨다.

시간복잡도 = O(N)

 

● 중간에서 만나기

Meet in the Middle

문제를 절반으로 나눠서 양쪽 절반에서 모든 경우를 다 해보는 방법

 

△ 문제 - 부분수열의 합 2

문제 : 서로 다른 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제

 

방법

주어진 수열을 반으로 나눈다. 각각 Up, Down.

각각의 수열에 대하여 모든 경우를 나열한다.

L과 R을 이동시키며 합이 S가 되는 경우를 센다.

 

△ 문제 - 합이 0인 네 정수

문제 : 크기가 N인 배열 A, B, C, D가 있다. 이때, A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 문제

 

방법

총 가능한 경우의 수 : N^4가지

절반으로 나눠서 A[a]+B[b] = N^2가지,  C[c]+D[d] = N^2가지 로 계산해 볼 수 있다.

 

● 그래프

다이나믹은 점화식이 문제마다 다르고, 브루트포스는 만드는 방법이 달랐다.
하지만 그래프는 알고리즘이 딱 있다. 변하지 않는다. (DFS, BFS)
문제의 상황을 어떻게 그래프로 만들거냐가 더 중요하다.

 

§ 특징

정점(Node)과 간선(Edge)으로 이루어짐. G = (V, E)

경로 : 정점A에서 B로 가는 경로 (A->B->C)

사이클 : 정점 A에서 다시 A로 돌아오는 경로 (A->B->C->A)

단순경로와 단순사이클 : 경로/사이클에서 같은 정점 방문하지 않는다.

가중치★★★ : 지나갈때마다 소비해야하는 비용
차수 : 정점과 연결된 간선의 개수, in-degree와 out-degree가 다르다

 

§ 표현
그래프의 저장은 간선을 효율적으로 저장하는 것을 의미한다. 

효율 =  한 정점이 있을때, 한 정점과 연결된 간선을 찾는 시간이 빠른 것

#방법1. 1차원 배열

1차원 배열은 효율성이 떨어짐. 전체 간선을 다 살펴봐야 함. O(E)

#방법2. 인접행렬

이차원 배열 A[i][j]

i와 j가 연결되어 있으면 A[i][j]=1. 공간 = O(V^2), 효율★=O(V)

but 인접행렬은 거의 안쓴다.

#방법3. 인접리스트.

A[i] = i와 연결된 모든 정점을 저장 (리스트, 배열)

왜 리스트냐, 몇개를 저장해야할 지 알 수 없기 때문에, 크기를 모른다.

크기가 변하는 배열을 쓰면 된다.

C++ : vector / Java : ArrayList / Python은 원래 변함

인접리스트 효율 = O(E), 공간 = E

가중치가 필요하면 두개씩 넣으면 된다.

-------------------------------------------------

+간선리스트라는 자료구조도 있다. 

아주 특수한 상황에서만 쓰인다.

크기가 변하는 배열을 쓸 수 없을때 링크드 리스트를 구현해야 하는데 구현하기 싫을때, 한 정점과 연결되어있는 간선을 빠르게 알 수 있다. 

단점 : 정렬을 한번 해야한다. 만드는데 걸리는 시간 O(ElogE)

 

§ 탐색

목적 : 한 정점에서 시작해 연결되어 있는 모든 정점을 1번씩 방문

종류 : DFS(깊이우선), BFS(너비우선, 최단경로(가중치가 모두 1일때)) - 차이점은 방문순서

중요도 : BFS >>>> DFS