/*elice*/ 문제 해결 절차, 완전 탐색, 시간복잡도

1.  문제 해결의 절차

---

 

1. 문제를 정확히 이해한다.

2. 문제를 해결하는 알고리즘을 개발한다.

3. 알고리즘이 문제를 해결한다는 것을 증명한다.

4. 알고리즘이 제한시간내에 동작한다는 것을 보인다.

5. 알고리즘을 코드로 작성한다.

6. 제출 후 만점을 받고 매우 기뻐한다.

 

 

 

 

 

2. 시간 복잡도

---

 

알고리즘이 대략 몇개의 명령을 수행하는가?
프로그램의 수행 시간을 유추할 수 있음

 

 

sum = 0

for i in range(n) :
	for j in range(i) :
    	sum = sum + i + j

 

 

이 알고리즘의 시간 복잡도는 O(n^2)으로, 해당 연산은 {n x (n-1)} / 2 으로 계산하여 최고 차항만을 취합니다.

 

 

왜?

 

n^2 + 2n + 3 이 식에서 만약 n이 1000이라면, n^2 = 1,000,000 이지만, 2n = 2,000에 불과합니다. n의 값이 커질수록 이 차이는 더 커지게 됩니다. 최고 차항에 비하면 나머지 값들은 무시할 수 있는 값이기 때문에 대략적인 연산 횟수를 표현할 수 있어 제외하게 됩니다.

 

 

다른 한가지 예를 더 살펴볼께요.

 

아래와 같은 함수에서 myList의 배열에 [ 1, 2, 3, 4, 5 ]가 할당되고, target이 운이 좋은 경우 1이여서 단 한 번의 연산으로 값을 찾아 True를 리턴할 수 있지만, -1 처럼 리스트에 없는 값이여서 최악의 경우에는 모든 배열을 돌아 값을 찾아 False를 리턴해야 합니다. 이처럼 운이 좋은 경우와 나쁜 경우가 생겨 연산 횟수의 차이가 생길 수 있습니다. 이때, Big-O 시간 복잡도 표기법은 최악의 경우를 고려한 연산횟수를 기준으로 정합니다. 그러면 이 함수의 시간복잡도는 O(n)입니다.

 

 

Big-O 표기 :

최악의 경우에 수행하는 명령 수

 

 

def findNumber(myList, target) :
	for v in myList :
    	if v == target :
        	return True
        return False

 

 

 

 

3.  완전 탐색

---

 

완전탐색이란 무엇일까요? 그리고 이제까지 문제해결 절차에 대하여 이야기하다가 왜 완전탐색에 대하여 물어보는 것 일까요?

그 이유를 알기 위해 완전 탐색에 대해 알아볼께요.

 

 

완전 탐색(Brute-Force)

 

가능한 모든 경우를 시도해 보는 것

가능한 모든 경우가 무엇인가?

 

 

문제를 해결하는 방법 중 하나인데, 가장 기초적이고 쉬운 방법입니다.

가능한 모든 경우를 전부 고려해도 괜찮을 경우에는 단순히 모든 경우를 고려함으로써 문제를 해결합니다.

 

 

완전 탐색의 중요성

 

문제가 주어지면

무.조.건

완전 탐색법으로 먼저 시도해야 합니다.

 

 

왜냐하면 상식적인 문제 해결의 흐름이 있는데, 어떤 문제를 해결하기 위해 A라는 방법을 적용해보고 해결이 불가능하다면 B라는 방법을 사용.

이와 같이 문제를 해결하기 위한 여러가지 방법을 써보기 위해 가장 먼저 기본이 되는 A라는 방법을 적용해보아야 합니다.

이 A가 완전 탐색입니다.

 

 

 

 

이 문제에서 모든 경우는?

 

완전 탐색을 적용해도 제한시간내에 동작함을 알기 위해서 가능한 모든 경우가 몇 개 인지 알아야 합니다.

만약 가능한 모든 경우의 수가 너무 많다면 완전 탐색으로 풀기 어렵습니다.

 

연속부분이랑 시작 부분과 끝 부분을 정해놓음으로서 정의됩니다. 시작 부분의 위치를 p라고 하고, 끝 부분의 위치를 q라고 하겠습니다.

len(list) = n일 때, p = [0~n-1]이고 q = [p~n-1]라고 정의됩니다.

그렇다면 가짓수는 p는 n개, q는 n-p개 입니다. 그러므로 연속 부분의 가짓수는 1~n의 합이라고 할 수 있습니다.

해당 식은 (n^2+n)/2 = O(n^2)으로 빅오표기법으로 표현됩니다.

 

연속부분에 대하여 합을 구할 때에는 p와 q의 값을 수뇌해야 합니다. 최악의 경우에는 리스트 전체 길이이므로 n의 합을 구해야합니다.

이럴 경우 시간 복잡도는 O(n)입니다.

 

모든 연속 부분을 구하는 경우 O(n^2), 연속 부분의 합을 구하는 과정이 O(n)이므로 완전 탐색으로 해결한 연속 부분 최대합 문제의 시간복잡도는

 

O(n^3)입니다.

 

 

 

 

Complexity

---

 

Complexity Theory에 대한 간단한 내용을 알아봅니다.

 

 

Complexity Theory
각 문제마다 풀이의 시간복잡도 다르다
내 풀이가 얼마나 좋은 풀이인가?

 

 

해석하자면 복잡도 이론입니다. 대부분의 문제는 푸는 방법이 존재하고, 그것에 따라 문자의 시간복잡도가 결정됩니다.

가장 빠른 시간복잡도는 O(nlogn)이고, 이외에도 다양한 시간 복잡도가 존재합니다.

 

 

P class → 다항시간

NP-Complete class

 

 

O(n^2)이나 O(n^3)과 같이 다항시간내에 해결이 가능한 복잡도도 있고, O(2^n)이나 O(n!)처럼 다항시간이 아닌 시간복잡도도 있습니다.

이렇게 다항인것과 아닌것의 시간차이는 어마어마합니다.

따라서 어떤 문제가 주어졌을 때 다항시간 내에 풀 수 있는가를 따로 분류합니다. P class

 

NP class는 답을 검증하는 데 다항시간이 걸린다는 뜻입니다.

그렇다면 NP-Complete class란 NP 문제들 중에서도 푸는 데 가장 오랜 시간이 걸리는 문제들입니다.

대표적인 문제로는 '원소의 합이 0인 부분집합'이 있습니다. 이러한 NP-Complete 문제는 입력값이 아주 작을 때만 풀 수 있습니다.

 

 

알고리즘 과정에서 다루는 문제들

 

(거의 대부분) P 문제들만을 다룬다

 

알고리즘에서는 고려해야 하는 경우를

줄이는 방법을 배운다

 

하지만 대표적인 NP-Complete 문제는 알면 좋다