2022.07.23

p151~200

 

보글문제

-완전 탐색 이용.

1. 문제의 분할

word 의 시작 위치 (y,x)와 인접한 여덟 칸을 모두 시도하며 답을 찾자. 

2. 기저 사례의 선택

더 이상의 탐색 없이 간단히 답을 낼 수 있는 경우를 기저 사례로 선택하자. 

a. 위치(y,x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패 

b. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공 

이때 두 조건의 순서는 바뀌어선 안됌. 

c. 현재 위치가 보글 게임판을 벗어난 경우

d. 첫 글자가 일치하지 않는 경우 

*간결한 코드 작성의 팁: 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하기 -> 함수 호출 시점에서 오류 검사할 필요 없어짐. 

3. 구현

4. 시간 복잡도 분석

완전 탐색이므로 가능한 답 후보의 수를 전부 세어 보면 됨. 

이 문제의 시간 복잡도: O(8^N)-> 지수적으로 증가하므로 단어의 길이가 짧은 경우에만 해결이 가능함. 

5. 완전 탐색 레시피

1) 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로 걸리는 시간은 가능한 답의 수에 정확히 비례함. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지 가늠하기. 만약 계산할 수 없다면 설계 패러다임을 적용.

2) 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔. 각 선택은 답의 후보를 만드는 과정의 한 조각. 

3) 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성. 

4) 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로 이것을 기저 사례로 선택해 처리 

6. 이론적 배경: 재귀 호출과 부분 문제 

- 재귀 호출을 논의할 때 문제란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미함. 

- 보글 게임에서 '해당 단어를 현재 위치에서 찾을 수 있는지'를 알기 위해서는 9가지의 정보를 알아야함. 1. 현재 위치에 단어의 첫 글자가 있는가? 2. 윗 칸에서 시작해서 단어의 나머지 글자들을 찾을 수 있는가? 3. 왼쪽 위칸에서 시작해서 단어의 나머지 글자들을 찾을 수 있는가?... 이때 2번 이후의 항목은 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제를 푼 결과임. (원래 문제: 현재 위치 그리고 단어가 주어질 때 해당 단어를 이 칸에서부터 시작해서 찾을 수 있는가?) 이런 문제를 원래 문제의 부분 문제라고 함. 

 

소풍 문제 

1. 완전 탐색 

가능한 조합의 수를 계산하는 문제의 가장 간단한 해결법 = 완전 탐색을 이용해 조합 모두 만들어 보기 

재귀 호출을 이용해 문제를 해결하려면 우선 각 답을 만드는 과정을 여러 개의 조각으로 나눠야 한다. 여기서는 전체 문제를 n/2 개의 조각으로 나눠서 한 조각마다 두 학생을 짝지어 주는 것. 이때 문제의 형태 = '아직 짝을 찾지 못한 학생의 명단을 주었을 때 친구끼리 둘씩 짝짓는 경우의 수 계산하라'

2. 중복으로 세는 문제

해결법: 항상 특정 형태를 갖는 답만 세기. ex 사전순으로 가장 먼저 오는 답 하나만을 세기 

3. 답의 수의 상한 

답의 수에 정비례하는 시간이 걸림.ㅁ

 

게임판 덮기 문제

경우의 수를 세는 것 -> 완전 탐색 이용 

1. 중복으로 세는 문제

해결법: 재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하는 것. 

2. 답의 수 상한

2^32개 

시간 내에 구현할 수 없을 것 같지만, 각 단계에서 우리가 선택할 수 있는 블록 배치가 크게 제한되어 있으므로 가능. 

3. 구현 

a. 한 칸을 덮는 네 가지 방법을 각각의 코드로 구현하지 않고 coverType[] 배열에 저장. 이 배열은 네 가지 방법에서 새로 채워질 칸들의 상대 좌표의 목록을 저장.

b. set() 은 delta 에 따라 블록을 놓는 역할과 치우는 역할을 같이 할 수 잇음. 블록을 놓는 것과 치우는 것을 별도로 짤 필요 x 

c. set()은 해당 위치에 블록을 놓을 수 있는지 여부도 같이 판단. 단 이때 곧장 함수를 종료하는 것이 아니라 마지막까지 함수를 실행한다는 데 유의.

 

<최적화 문제>

문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 좋은 답을 찾아 내는 문제들을 통칭해 최적화 문제라고 부름. 완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법.

 

여행하는 외판원 문제

1. 무식하게 풀 수 있을까?

-시간 안에 답을 구할 수 있을까? 

2. 재귀 호출을 통한 답안 생성 

-shortestPath(path) = path 가 지금까지 만든 경로일 때, 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다. 

 

시계 맞추기 문제 

1. 문제 변형하기

입출력 설명이 유도하는 방향과 달리 스위치를 누르는 순서는 전혀 중요하지 않다. 시계는 12시간이 지나면 제 자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 바꿀 수 있다. 

2. 완전 탐색 구현하기

문제를 모두 열 조각으로 나눈 후 각 조각에서 한 스위치를 누를 횟수를 정하는 식으로 구현. 

 

많이 등장하는 완전 탐색 유형 

-모든 순열 만들기

-모든 조합 만들기 

-2^n가지의 경우의 수 만들기 

 

<분할 정복>

각개 격파.

주어진 문제들을 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것. 

분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 가짐. 

a. 문제를 더 작은 문제로 분할하는 과정(divide)

b. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

c. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

분할 정복을 적용해 문제를 해결하기 위해서는 문제에 몇 가지 특성이 성립해야 함. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 하며, 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 함. 

분할 정복의 장점: 많은 경우 같은 작업을 더 빠르게 처리. 

 

수열의 빠른 합과 행렬의 빠른 제곱 

1. 시간 복잡도 분석

O(lg(n))

2. 행렬의 거듭제곱

 분할 정복을 이용하면 빠르게 계산 가능. 

3. 나누어 떨어지지 않을 때의 분할과 시간 복잡도 

같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예이다. 절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문. 이런 속성을 부분 문제가 중복된다 고 부름. 또 동적 계획법이 고안된 이유이기도 함.

 

병합 정렬과 퀵 정렬 

두 알고리즘 모두 분할 정복 패러다임을 기반으로 해서 만들어진 것. 

-병합 정렬: 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻음. O(n)

-퀵 정렬: 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할. 이를 위해 퀵 정렬은 파티션이라는 단계를 도입. 이는 배열에 있는 수 중 임의의 기준 수 를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정. O(n)

1. 시간 복잡도 분석 

병합 정렬: O(nlgn)

퀵 정렬: 평균적: O(nlgn) 최악: O(n^2)

 

카라츠바의 빠른 곱셈 알고리즘 

1. 시간 복잡도 분석 

 

카리츠바 알고리즘은 두 개의 입력을 절반씩으로 쪼갠 뒤, 세 번 재귀 호출을 하기 때문에 재귀 호출을 한 번이나 두 번만 하던 지금까지의 예제와는 다르게 시간 복잡도를 분석해야 함.

최종 시간 복잡도 : O(n^(lg3))

입력의 크기가 작을 경우, O(n^2)가 더 빠름.

 

쿼드 트리 뒤집기 문제 

1. 쿼드 트리 압축 풀기 

쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀 호출로 구현하는 것이 가장 자연스러움. 

2. 압축 문자열 분할하기

주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수 getChunkLength() 만들기. 

decompress() 함수에 s를 통째로 전달하지 말고 s 의 한 글자를 가리키는 포인터를 전달하기. 

3. 압축 다 풀지 않고 뒤집기

압축을 해제한 결과를 메모리에 다 저장하는 대신 결과 이미지를 뒤집은 결과를 곧장 생성하는 코드 작성하기. 

4. 시간 복잡도 분석 

O(n)

 

울타리 잘라내기 문제 

1. 무식하게 풀 수 있을까?

-2중 for 문 사용 시 O(n^2) 시간 걸림 -> 기각

2. 분할 정복 알고리즘의 설계

-n개의 판자를 절반으로 나눠 두 개의 부분 문제를 만들기. 그럼 우리가 찾는 최대 직사각형은 다음 세 가지 중 하나. 

-가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다

-가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다

-가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다. 

-첫 번와 두 번째 경우는 반으로 나눈 부분 문제를 재귀 호출하여 해결 가능.

3. 양쪽 부분 문제에 걸친 경우의 답

-더 높은 오른쪽 판자를 포함하게끔 확장하는 것. 

4. 정당성 증명

-핵심: 양쪽 부분 문제에 걸쳐 있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳음을 보이는 부분. 귀류법 이용해서 증명 가능. 

5. 시간 복잡도 분석

6. 선형 시간 알고리즘