[1주차-1] 코딩테스트 연습 - 선형배열과 재귀 알고리즘

파이썬에서 이미 데이터 타입을 제공하더라도 기본적인 데이터 타입만으로 해결할 수 없는 문제가 있을 수 있다. 예를 들어, 파이썬 내장함수인 max 함수는 모든 원소를 다 탐색하므로 리스트의 길이만큼의 시간이 걸린다. 즉 자료의 길이가 길어질수록 소요 시간이 오래 걸린다.

 

1. 선형배열

파이썬에서 배열은 리스트라는 데이터형으로 제공된다.

list.append() #원소 덧붙이기
list.pop() #원소 하나 꺼내기

위의 두 작업은 시간 복잡도가 O(1)이므로 실행시간을 최소로 할 수 있다. 물론 list.pop(n)처럼 인덱스를 지정해주면 시간 복잡도가 O(n)이 된다.

 

list.insert() #원소 삽입하기

del list[n] #원소 삭제하기

list.index() #원소 위치 찾기, 해당 원소가 존재하지 않으면 –1 출력

위의 두 작업은 시간 복잡도가 O(n)이다.

 

2. 배열의 정렬과 탐색

(1) 정렬

일반적으로 정렬은 탐색보다 더 많은 시간이 소요된다.

파이썬에서는 sort라는 정렬 함수를 제공한다.

A = sorted(L) #A에 정렬된 L을 할당함(L의 순서는 바뀌지 않음)
L.sort() #L을 정렬함(L의 순서가 바뀜)

###key 지정하기(lambda)
sorted(L, key = lambda x: len(x)) # 원소의 길이 순서로 정렬

 

참고로 파이썬의 sort는 팀소트 이용한다.

*팀소트 O(n)~O(nlogn)

팀소트란 팀 피터스(Tim Peters)가 피터 매킬로이(Peter Mcllroy)의 1993년 논문을 기반으로 2002년도에 파이썬을 위해 C로 구현한 알고리즘으로, 창안자인 팀 피터스의 이름을 따 팀소트로 불린다. 팀소트는 '실제 데이터는 대부분 이미 정렬되어 있을 것이다'라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설게한 알고리즘이다. 팀소트는 삽입 정렬과 병합 정렬을 적절히 조합한 알고리즘으로 이미 정렬되어 있는 자료의 경우 비교를 건너 뛰기 때문에 O(n)까지 가능하다.

즉, 단순히 정렬할 때 sort를 사용할 때는 다른 정렬 알고리즘을 떠올릴 필요 없어 파이썬의 sort를 사용하면 된다는 소리다.

 

(2) 선형 탐색 O(n)

리스트 내의 원소를 하나하나 비교하는 탐색법이며, 시간이 오래걸린다.

파이썬에서 for문이나 while문으로 간단하게 작성 가능하다.

 

(3) 이진 탐색 O(logn)

포인터 두 개(upper, lower)를 이용해서 mid를 설정하고 찾으려는 값보다 mid가 더 크면 lower = mid-1, mid가 더 작으면 upper = mid+1로 설정해서 위 과정 반복하기.

def solution(L, x):
    upper = len(L)-1
    lower = 0
    while lower <= upper: #작거나 같다로 설정하는 것이 핵심
	    mid = (upper+lower)//2
    	if L[mid] > x:
		    upper = mid - 1
    	elif L[mid] < x:
        	lower = mid + 1
    	else:
    		return mid
    return –1

 

3. 재귀 알고리즘

수학의 점화식처럼 함수가 그 함수로 정의되는 구조이다. 예를 들어 피보나치 수열을 재귀함수로 나타내면 f(n) = f(n-1) + f(n-2)과 같이 나타낼 수 있다. 재귀 알고리즘을 구현할 때는 종결조건이 중요한데, 위 식에서는 n=1일 때와 n=2일 때의 함숫값을 설정해야 재귀가 종결되었을 때 올바른 값으로 계산될 수 있다.

 

* 재귀적 이진 탐색

def solution(L, x, l, u): #L은 리스트, x는 찾는 원소, l은 lower, u는 upper
    if l > u:  #재귀의 과정 속에서 L에 x가 없으면 l이 u보다 커진다.
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L,x,l,mid-1)
    else:
        return solution(L,x,mid+1,u)