[알고리즘 #4] Problem Solving Paradigms (1)

 

문제가 주어졌을 때 올바른 방법으로 접근하는 것이 중요하다.  주요 방법론을 정확하게 이해하고 관련된 문제들을 많이 풀어보는 것이 좋다.

 

- Input : Size n array A

- A 에서 가장 큰 element 와 작은 element 찾기 : Complete Search - O(n)

- A 에서 k 번째로 작은 element 찾기 : Divide and Conquer - O(n log n)

- A의 두 element x 와 y에 대해 |x-y|의 최대값 구하기 : Greedu - O(n)

- A의 LIS 구하기 : DP - O(n6=^2) or Binary Search + DP - O(n log n)

 

Complete Search

전체 혹은 일부 가능한 탐색 공간을 하나 하나 살펴봄으로써 원하는 답을 찾는 방법

 

ex) 8 Queens Chess Problem(Uva 750)

: 8x8 체스판에 퀸 8개를 서로 공격할 수 없도록 하는 모든 배치를 구하기

-좌표 (a, b) - a번째 row, b번째 columnn 에는 반드시 queen 이 위치해야함

 

방법1 : 64개의 칸에 가능한 8개의 퀸을 모두 배치하기 -> 40억개 경우의수

방법2 : 하나의 퀸이 하나의 column 에만 들어갈 수 있다는 사실 -> 1700만개 경우의 수 

방법3 : 같은 row에도 두 퀸이 존재할 수 없다는 사실을 이용 - 퀸이 (j, i) 에 있는 경우 row[i] = j 위 예시의 경우 row = {2, 4, 6, 8, 3, 1, 5}.

Row array 는 permutation 이므로 8! ~ 40000으로 줄어든다

 

방법4 : 방법 3에서 불가능한 조건을 좀 더 pruning 

-위치 (i, j)와 (x, y) 에 두 퀸이 있다고 하자.

- 이 때, |i-x| = |j-y| 인 경우 두 퀸은 같이 존재할 수 없다.( 대각선으로 만나기 때문애)

- 즉 위 제약조건을 만족하는 해들 중에서 row[b] = a 인 해를 출력하면 됨

 

ex) Rat Attack_ Uva 10360

 

모든 가능한 위치에 폭탄 설치해보기_ 약 26억번이므로 TLE 가능성 농후

 

=> Complete Search 를 거꾸로 생각가능 

killed[1025][1025] array 를 만든다음 , 쥐의 위치와 마리수 정보 (x,y,p) 얻는 대로 |i-x| <= d, |j-y| <= d 를 만족하는 모든 killed[i][j] 에 p를 더한다. 이 후 killed array 의 최대값과 index를 출력하면 됨. 사전작업에 O(nd^2)

 

 

Divide and Conquer

: 탐색 공간의 전체를 살펴봄으로써 원하는 답을 찾는 방법

 

1. 주어진 문제를 작은 단위(subproblem) 으로 쪼갠다. 이 때 subproblem 은 본 문제와 같지만 input size 가 작은 문제를 뜻한다.

2. 1번에서나눈 subproblem 들을 recursion 이용하여 해결한다.

3. 2번에서 푼 subproblem 들의 답을 적절하게 조합하여 본 문제의 답을 제시한다.

 

ex) Merge Sort, Quick Sort, Binary Search 

 

ex) Uva10341_Solve it

=> Binary Search 를 통해 0.0과 1.0 사이의 모든 숫자들에 대해 해가 있는지 여부 검색한다. 

 

Bit-Parallel Algorithms

: 반복문 등을 비트 연산자를 이용한 연산으로 변형하여 수행하는 기법

ex) hamming Distance : 길이가 같은 두 bit string a, b가 있을 때, a와 b 사이의 hamming distance 는 a와 b의 symbol이 일치하지 않는 위치의 개수이다. 

hamming (01101, 11001) = 2