스택의 개념

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조.

스택의 연산

스택(Stack)은 LIFO(Last In First Out)를 따른다. 즉, 가장 최근에 스택에 추가된 항목이 가장 먼저 제거될 항목이다.

• pop() : 스택에서 가장 위에 있는 항목을 제거한다.
• push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.
• peek() : 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty() : 스택이 비어 있을 때에 true를 반환한다.

스택의 구현

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

Array 기반 스택

• 접근 속도가 빠르지만 변경이 용이하지 않다.
• 배열이 생성될 때, 메모리의 연속된 공간에 데이터를 저장함 → 검색할 때는 데이터를 빠르게 찾을 수 있지만, 변경이 일어났을 때는 새로운 배열을 생성하고, 생성된 배열에 데이터를 복사해야하기 때문에 느려진다.
• 복사해야할 데이터가 많지 않다면, 크게 상관없지만 데이터가 많아질수록 점점 느려질 것이다.

Linked List 기반 스택

• 메모리 주소를 통해 노드가 연결되어 있어, 배열 기반과 달리 상수 시간에 i번째 항목에 접근할 수 없다. 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
• 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.
• 메모리에 연속된 공간에 존재하지 않기 때문에 검색 데이터를 찾기 위해 노드를 순회해야하므로 검색 속도는 좋지 않다.

검색이 자주 일어나고, 등록, 수정 등 변경이 자주 일어나지 않는다면, 배열 스택으로 구현하는 것이 좋다. 반대로 검색보다는 등록, 수정이 빈번히 일어나는 경우에는 연결리스트 스택을 사용하는 것이 좋다.

코드 구현(python)

stack = list()
sp = -1

def stack_pop(stack:list, sp:int):
	
	if sp < 0:
		return False
	
	return stack[:sp], stack[sp], sp-1

def stack_push(stack:list, num:int, sp:int):
	
	stack.append(num)
	sp += 1
	
	return stack, sp

def isEmpty(sp):
	return sp == -1
	

# idx 호출. 스택 초기화 추가.

메모리 스택

메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역이다. 스택 영역은 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.

이렇게 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 한다. 스택 영역은 push 동작으로 데이터를 저장하고, pop 동작으로 데이터를 인출한다. 이러한 스택은 후입선출(LIFO, Last-In First-Out) 방식에 따라 동작하므로, 가장 늦게 저장된 데이터가 가장 먼저 인출된다.

스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당된다.

스택 오버플로우(stack overflow)

앞서 함수의 재귀호출이 반복되면, 해당 프로그램은 스택 오버플로우(stack overflow)에 의해 종료된다.

만약 재귀 호출이 무한히 반복되면, 재귀 호출에 의한 스택 프레임이 계속해서 쌓여만 갈 것이다.

이렇게 스택의 모든 공간을 다 차지하고 난 후 더 이상의 여유 공간이 없을 때 또 다시 스택 프레임을 저장하게 되면, 해당 데이터는 스택 영역을 넘어가서 저장되게 된다.

이렇게 해당 스택 영역을 넘어가도 데이터가 저장될 수 있으면, 해당 프로그램은 오작동을 하게 되거나 보안상의 큰 취약점을 가지게 된다.

따라서 스택 오버플로우가 발생하면, 에러를 발생하고 곧바로 강제 종료시킨다.

Abstract

일반적인 방법으로 구현했을 때, 이 정렬은 안정 정렬(Stable Sort)에 속하며, 분할 정복 알고리즘의 하나입니다.

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법입니다.

• 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

Process

합병 정렬은 추가적인 리스트를 필요로 한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

Python Code

def mergeSort(arr:list):

    def recursion(arr:list):

        if len(arr) == 1 or len(arr) == 0:		# 1.
            return arr

        mid = len(arr) // 2

        recursion_a = recursion(arr[:mid])		# 2.
        recursion_b = recursion(arr[mid:])
        
        idx_a = 0
        idx_b = 0
        temp = []

        while idx_a < len(recursion_a) and idx_b < len(recursion_b):		# 3.
            if recursion_a[idx_a] < recursion_b[idx_b]:
                temp.append(recursion_a[idx_a])
                idx_a += 1
            else:
                temp.append(recursion_b[idx_b])
                idx_b += 1

        if idx_a == len(recursion_a):
            temp += recursion_b[idx_b:]
        else:
            temp += recursion_a[idx_a:]

        return temp

    return recursion(arr)

시간 복잡도

레코드의 개수 n이 2의 거듭제곱이라고 가정($n=2^k)$했을 때, 깊이에 따라서 다음과 같다. $2^3 \rightarrow 2^2 \rightarrow 2^1 \rightarrow 2^0$ 순으로 줄어들게 된다. 이것을 일반화하게 되면 $n=2^k$가 되고 결국 $k=log_2(n)$ 라는 것을 알 수 있다.

합치는 연산을 계산해보면 배열의 크기가 $1 \rightarrow 2 \rightarrow 4 .... \rightarrow n$순으로 증가하여 일반화하면 최대 n번의 비교를 하게 된다.

따라서 깊이 $log(n)$과 합치는 연산 $n$을 곱하여 $nlog(n)$이 된다.

Abstract

기본적으로 $O(N^2)으로 정렬하는 알고리즘(Ex : 버블 정렬, 선택 정렬, 삽입 정렬)바꾸는 기준이 순회흘 하면서 바뀌며, 일반적으로 for문의 중첩으로 $O(N^2)의 복잡도를 가지게 된다. 하지만 퀵 정렬 알고리즘은 직관적으로 보았을 때, 비교를 반씩 줄여나가면서 정렬하는 알고리즘으로 즉, 재귀를 이용한 분할정복 알고리즘이다.

• 분할(Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)로 분할한다.
• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)가 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

Process

1. 특정한 기준을 통해 Pivot 값을 지정한다.(먼저 아래 코드와 설명에서는 가장 앞의 값을 기준으로 잡겠습니다.)
2. Pivot을 기준으로 작으면 왼쪽으로, Pivot보다 크면 오른쪽으로 이동한다.
3. 이동하는 방식은 
4. Pivot 위치를 고정하고 왼쪽에 있는 값들을 다시 1번부터 실행, 오른쪽에 있는 값들을 1번부터 실행한다.
5. 양쪽 값이 1개인 경우 멈추게 된다.

Python Code

def quickSort(arr:list):

    
    def recursion(temp:list):
    
        if len(temp) == 1 or len(temp) == 0:		# 6.
            return temp
        
        pivot_idx = 0				# 1.
        pivot = temp[pivot_idx]
        
        low = pivot_idx + 1
        high = len(temp) - 1
        low_change, high_change = False, False
        
        while high > pivot_idx and low < len(temp) and low <= high:		# 2.
        
            if temp[low] < pivot:
                low += 1
            else:
                low_change = True
            
            if temp[high] > pivot:
                high -= 1
            else:
                high_change = True
                
            if low_change and high_change:					# 3.
                temp[low], temp[high] = temp[high], temp[low]
                low_change, high_change = False, False
    
        temp[pivot_idx], temp[high] = temp[high], temp[pivot_idx]	# 4.
        return recursion(temp[:high]) + [temp[high]] + recursion(temp[high+1:])		# 5.

    return recursion(arr)

1. 피벗을 선택합니다. 이 코드에서는 가장 앞에 위치한 값을 피벗으로 선택했습니다.
2. 1번 값을 low, 마지막 값을 high로 설정하고 피벗보다 작은 경우 왼쪽으로, 피벗보다 큰 경우 오른쪽으로 이동합니다. low와 high값이 교차하는 순간 모든 값에 대한 피벗과 비교가 끝납니다.
3. 2번에서 왼쪽에서 피벗보다 큰 경우와 오른쪽에서 피벗보다 큰 경우 서로 값을 교환(swap)합니다.
4. 2번이 종료된 경우 high 위치의 값과 피벗을 교환(swap)합니다.
5. 재귀적으로 왼쪽과 오른쪽을 다시 피벗을 설정하고 정렬을 시작합니다.
6. 더이상 교체할 값이 없는 경우 종료합니다.

시간 복잡도

최선의 경우 아래와 이미지와 같아진다.

순환 호출의 깊이

레코드의 갯수가 n개라고 가정하고 n은 2의 제곱이라고 가정한다면, $2^3\rightarrow 2^2 \rightarrow 2^1 \rightarrow 2^0$식으로 전개가 된다. 이를 일반화하면 $n=2^k$가 되고 $k=log_2n$가 된다.

순환 호출 단계의 비교 연산

각 순환 호출에서는 해당 리스트의 전체와 비교해야한다. 위의 코드를 살펴보면 피벗값은 가장 처음으로 설정되고 이후 low와 high를 통해 모든 값을 비교하므로 n으로 연산할 수 있다.

따라서 퀵 정렬의 시간 복잡도는 $O(nlogn)$이다.

모든 정렬에서 이상적인 계산으로는 퀵정렬이 가장 빠르다. 하지만 퀵정렬은 최악의 경우 $O(n^2)$이 걸리는데 그 이유는 아래와 같다.

리스트가 계속 불균형하게 나누어지는 경우이다. 특히, 이미 정렬된 리스트에 대하여 퀵 정렬을 실행하는 경우이다.

이런 경우 리스트의 깊이가 n번이 되므로 $O(n^2)$가 된다. 이를 해결하기 위한 방법으로는 피벗의 기준을 바꾸면 해결된다.

바꾸는 방식은 대표적으로 피벗의 기준을 가운데 값으로 하게 되면 항상 2 부분으로 나뉘게 되며 $log(n)$이 된다.

해당 글은 gyoogle 님 github를 참고해서 작성한 글입니다.

삽입 정렬(Insertion Sort)

Abstract

손 안의 카드를 정렬하는 방법과 유사합니다.

Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.

Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.

최선의 경우 $O(n)$이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘입니다.

Process

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하여 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

Python Code

def insertionSort(arr:list):

    for i in range(1, len(arr)):		# 1.
        prev = i - 1
        temp = arr[i]
        while prev >= 0 and arr[prev] > temp:			# 2.
            arr[prev+1] = arr[prev]
            prev -= 1
                
        arr[prev+1] = temp				# 3.

    return arr

1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작합니다. temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장합니다.
2. 이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 '1'번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록 합니다.
3. '2'번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index)를 가리키게 됩니다. 따라서, (prev+1)에 temp 값을 삽입해줍니다.

시간 복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + ... + 2 + 1 -> n(n-1)/2 즉, $O(n^2)$입니다.

하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한 번씩 밖에 비교를 안 하므로 $O(n)$의 시간 복잡도를 가지게 됩니다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다.

최선의 경우는 $O(n)$의 시간복잡도를 갖고, 평균과 최악의 경우 $O(n^2)$의 시간 복잡도를 갖게 됩니다.

위의 코드를 자세히 살펴보면,

1. for문 n-1번 반복
2. prev 입력, temp 입력
3. while문 1, 2, .... 최대 n-1번 반복
4. prev값을 prev+1로 이동, prev - 1
5. 적절한 위치에 temp값 입력
6. 계산해보면 $\Sigma^{n-1}{(O(1)+O(1)+ (\Sigma^{n-1}{O(1)+O(1)}) + O(1))}$
7. 결과적으로, $O(n^2)$

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 $O(n)$ 입니다.

장점 & 단점

1. 장점
   • 알고리즘이 단순합니다.
   • 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다.
   • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. -> 제자리 정렬(in-place sorting)
   • 안정 정렬(Stable Sort)
   • Selection Sort나 Bubble Sort와 같은 $O(n^2)$ 알고리즘에 비교하여 상대적으로 빠릅니다.
2. 단점
   • 평균과 최악의 시간 복잡도가 $O(n^2)$으로 비효율적입니다.
   • Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적입니다.

Conclusion

Selection Sort와 Insertion Sort는 k번째 반복 이후, 첫 번째 k요소가 정렬된 순서로 온다는 점에서 유사합니다. 하지만, Selection Sort는 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 Insertion Sort는 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있습니다.

이 글은 gyoogle님의 github에 있는 자료를 바탕으로 작성되었습니다.

Abstract

Selection Sort는 Bubble Sort와 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

Selection Sort와 Insertion Sort를 헷갈려하시는 분들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하시면 편합니다.

Process

1. 주어진 배열 중에 최소값을 찾습니다.
2. 그 값을 맨 앞에 위치한 값과 교체합니다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체합니다.

Python Code

def selectionSort(arr:list):
	for i in range(len(arr)):			# 1.
		minimum_val, minimum_idx = 0, 0
		for j in range(i+1, len(arr)):		# 2.
        	
			if minimum_val > arr[j]:		# 3.
				minimum_val = arr[j]
				minimum_idx = j
		arr[i], arr[minimum_idx] = arr[minimum_idx], arr[i]		# 4.
    
    
    return arr

1.  우선, 위치(idx)를 선택합니다.
2. 선택한 위치의 값과 i+1번째 원소부터 차례대로 비교를 시작합니다.
3. 오름차순으로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(idx)를 갱신합니다.
4. [2]번 반복문이 끝난 뒤에 선택한 위치의 값과 기존 가장 작은 값을 서로 교환(swap)해줍니다.

시간 복잡도

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1~(n-1) -> n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) -> n-2

최종적으로 $(n-1)+(n-2)+....+2+1 \rightarrow n(n-1)/2$

비교하는 것이 상수 시간에 이뤄진다는 가정 아래, n개의 주어진 배열을 정렬하는데 $O(n^2)$만큼의 시간이 걸립니다. 최선, 평균, 최악의 경우 시간복잡도는 $O(n^2)$로 동일합니다.

위의 코드를 통해 자세히 계산해보면 아래와 같습니다.

1. n번 반복
2. n-1, n-2, ...., 2, 1번 반복
3. if문 및 이하는 1번 실행
4. swap 부분 1번 실행
5. 식으로 표현하면 $\Sigma \Sigma (O(1)+O(1)+O(1)) + O(1)$ 입니다.
6. 따라서 시간복잡도는 $O(n^2)$ 입니다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 $O(n) 입니다.

장점 & 단점

1. 장점
   • Bubble sort와 마찬가지로 알고리즘이 단순하다.
   • 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야하는 자료 상태에서 비교적 효율적입니다.
   • Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. -> 제자리 정렬(in-place sorting)
2. 단점
   • 시간 복잡도가 $O(n^2)$로 비효율적입니다.
   • 불안정 정렬(Unstable Sort)입니다.

추가적인 왜?

Unstable Sort가 정확히 무엇이지?

1. Stable Sort(안정 정렬)
   • 비교 대상의 Key가 여러개 값을 가질 때 혹은 같은 값을 가지는 데이터가 여러개가 있을 때, 정렬 후에 기존의 순서를 유지하는 정렬.
   • 즉, 정렬되지 않은 상태에서 같은 키 값을 가진 원소의 순서가 정렬 후에도 유지되느냐 이다.
   • Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, Bucket Sort, Radix Sort
2. Unstable Sort(불안정 정렬)
   • 비교 대상의 Key가 여러개 값을 가질 때 혹은 같은 값을 가지는 데이터가 여러개가 있을 떄, 정렬 후에 기존의 순서가 유지 되지 않는 정렬
   • 예를 들어서 다음 5 3 1' 9 2 1이 있다면 1 1' 2 3 5 9 와 1' 1 2 3 5 9가 나올 수 있다.
   • Selection Sort
   • Shell Sort
   • Heap Sort
   • Quick Sort

Abstract

정렬에는 많은 종류의 정렬이 있지만 해당 포스트에서는 아래 6가지 정렬을 정리하려고 합니다.

1. $O(n^2)$
   • Bubble Sort, 거품 정렬
   • Selection Sort, 선택 정렬
   • Insertion Sort, 삽입 정렬
2. $O(nlogn)$
   • Quick Sort, 퀵 정렬
   • Merge Sort, 병합 정렬
   • Heap Sort, 힙 정렬

해당 글은 gyoogle 님 github의 tech-interview-for-developer를 기반으로 작성합니다.

코드는 파이썬으로 작성하려 노력합니다.

거품 정렬 (Bubble Sort)

Abstract

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다. 아래는 위키백과에서 나오는 무작위 배열 수의 정렬 예시입니다.

Process

1.  1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를..... 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환합니다.
2.  1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외도, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정령에서 제외되는 데이터가 하나씩 늘어납니다.

Python Code(Ascending)

def bubbleSort(arr:list):
	
    for i in range(len(arr)):				# 1.
    	for j in range(len(arr)-i-1):			# 2.
        	if arr[j] > arr[j+1]:			# 3.
            	arr[j], arr[j+1] = arr[j+1], arr[j]
    
    return arr

1.  제외될 원소의 갯수를 의미합니다. 1회전이 끝났을 때, 배열의 마지막에 가장 큰 원소가 위치하므로 1씩 증가합니다.
2.  비교할 원소의 idx를 지정하는 for문입니다. 1회전이 끝났을 때, 마지막 값 1개가 고정, 2회전이 끝났을 때, 마지막 값 2개가 고정.... 이므로 전체 길이에서 i를 뺀 만큼 반복을 실행합니다.
3. 현재 idx가 가르키고 있는 2개의 값을 비교합니다. 위의 코드는 오름차순 정렬이므로 현재 원소가 다음 원소보다 큰 경우 서로 자리를 교환합니다.

시간 복잡도

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + ....... + 2 + 1 -> n(n-1)/2 이므로 O(n^2)입니다. 또한, Bubble Sort는 정렬이 돼있던 안돼 있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)로 동일합니다.

코드를 활용해 더 자세하게 계산해보자.

def bubbleSort(arr:list):
	
    for i in range(len(arr)):				# 1.
    	for j in range(len(arr)-i-1):			# 2.
        	if arr[j] > arr[j+1]:			# 3.
        		arr[j], arr[j+1] = arr[j+1], arr[j]	# 4.
    
    return arr # 5.

먼저 arr의 갯수를 n으로 생각한다.

1. for i in range(len(arr)) -> n번 반복
2. for j in range(len(arr)-i-1) -> n번, n-1, n-2 ......, 2, 1번 반복 -> 최대 n번 반복
3. 1번 실행하므로 O(1)
4. 1번 실행하므로 O(1)
5. 이를 계산해보면 $\Sigma^n \Sigma^n {(O(1) + O(1))}$
6. 결과적으로 $O(n^2)$

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)입니다.

장점 & 단점

1. 장점
   • 구현이 매우 간단하고, 소스코드가 직관적이다
   • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. -> 제자리 정렬(in-place sorting)
   • 안정 정렬(stable Sort)이다.
2. 단점
   • 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로, 굉장히 비효율적이다.
   • 정렬돼있지 않은 원소가 정렬됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

추가적으로 생각해보는 왜?

Bubble sort와 Selection sort가 유사하다고 하는데 어떤 점에서 유사할까?

글을 시작하며..

먼저 자세한 문제와 알고리즘을 알려드릴 수 없다는 것을 말씀드립니다!!😂

준비하기

 네이버 부스트캠프를 하면서 정말정말 좋은 분들을 만나게 됐다. 진짜 생각하면 할수록 귀인 같다는 느낌..ㅎㅎㅎ

그 분들과 함께 매일 아침마다 9시부터 10시까지 1시간 동안 문제를 풀고 30분 동안 리뷰하는 스터디를 진행하는 중이다. 다른 공부도 있지만 코딩테스트 문제를 너무 안풀면 감이 사라져서 이 정도만 투자했다!

이번 코딩테스트는 다른 기업의 테스트와 달리 1차 2시간, 2차 2시간으로 나눠져서 실시됐다.

안내 메일을 확인해보면 1차는 평소 테스트와 같은 것 같지만 2차는 [단계별 코딩테스트]로 코드 퀄리티와 리더빌리티를 살펴보기 위한 시험으로 주석까지 원하는 것 같았다.

시험 후기

 시험 내용은 엄청 어려운 느낌은 아니었지만 2시간이라는 시간이 많이 짧게 느껴졌다...😥😥😥

왜 중간에 이상한 거에 꽂혀서 시간을 넘겼을까...... 히든테케까지 확인하지 못한 점이 너무너무 아쉽ㅠㅠ

단계별 코딩테스트에서는 무서웠던 것 만큼은 아니어서 다행이었지만 마지막 문제에서 실수하나로... 다 못 풀었다...

너무너무 아쉽다. 흐앙

해당 문제를 풀면서 필요한 주석과 doc string을 정리하면서 풀다보니 생각보다 오래걸렸다.

사실 이번 시험과 스코페를 많이 고민했는데 그래도 경험해보자는 느낌으로 시험을 봤다. 물론 합격이 된다면(...?) 좋겠지만 그렇지 않아도 부족한 부분을 다시 한 번 생각할 수 있는 기회였다고 생각한다!

시험 결과

기대하지 않고 있었는데 합격이 나와서 머리가 멍해졌다..!!ㅋㅋㅋㅋㅋ

그래도 그동안 쉬지않고 공부한 결과라고 생각하고 남은 cs시험도 경험해보자는 마인드로 해보자!

- p.s. 아 나는 대학교 다니면서 무슨 전공 공부를 한거지... 왜 기억이 안날까유ㅠㅠ 꾸준히 cs공부하자..!

Abstract

새로운 음성 인식 응용프로그램이 포함되는 순환 신경망 언어 모델(RNN LM)이 제공된다. 최첨단 backoff language 모델과 비교했을때, perplexity가 50%하는 결과가 나타났다. 음성인식 실험은 Wall Street Joural task에서 단어 오차율이 같은 양의 데이터로 학습된 모델과 비교했을 때 대략 18% 감소를 보여준다. 그리고 대락 RNN LM보다 더 많은 데이터로 학습된 backoff 모델의 오차율에서 대략 5% 감소했다. 우리는 높은 계산(훈련) 복잡성을 제외하고, 연결론적 언어 모델이 표준 n-gram 기술보다 뛰어나다는 것을 말하는 충분한 경험적 증거를 제시한다.

index Terms : language modeling, recurrent neural networks, speech recognition

Introduction

시퀀셜 데이터 예측은 머신러닝과 인공지능에서 많은 key problem을 가지고 있다고 여겨진다. statistical language modeling의 목표는 문맥을 가진 텍스트 데이터에서 다음 단어를 예측하는 것이다. 따라서, 우리는 언어 모델을 구성할 때, 시퀀셜 데이터 예측 문제를 다룰 것이다. 그럼에도 불고하고, 이러한 통계 모델을 넘으려는 많은 시도는 매우 특정한 언어 도메인의 접근 방식을 포함한다.

예를 들어, 자연어 문장이 구문 분석 트리에 의해 설명될 수 있다는 가정, 또는 단어, 구문, 의미의 형태를 고려해야할 수 있다는 가정.

심지어 가장 널리 일반적으로 사용되는 모델(n-gram 통계에 기반한)도 언어는 원자 기호, 즉 문장을 형성하는 단어로 구성된다고 가정한다. 그리고 문장의 끝 기호가 중요하고 특별한 역할을 한다.

simple n-gram 모델에 비해 언어 모델링이 눈에 띄는 과정이 있었는지 의문이다. 만약 우리가 시퀀셜 데이터를 더 잘 예측하는 모델의 능력에 의해 이러한 진행상황을 측정한다면, 대답은 캐시 모델과 클래스 기반 모델의 도입에 상당한 개션이 이뤄졌다는 것이다. 다른 많은 기술들이 목적을 이루는 동안, 노력의 대부분은 비슷한 캐쉬 모델(긴 문맥 정보를 설명하는 모델) 혹은 클래스 기반 모델(비슷한 단어간에 파라미터를 공유하여 짧은 context에 대한 매개 변수 추정을 개선함.)

실제로 응용 프로그램을 통해 고급 언어 모델링 기술의 성공을 측정하려면 훨씬 더 회의적이어야 할 것이다. 실제 음성 인식 또는 기계 번역 시스템을 위한 언어 모델은 엄청난 양의 데이터를 기반으로 구축되며, 일반적인 믿음은 더 많은 데이터가 우리에게 필요한 전부라고 말한다. 연구에서 도출된 모델은 복잡한 경향이 있으며 종종 매우 제한된 양의 훈련 데이터를 기반으로 하는 시스템에서만 잘 작동한다. 실제로 제안된 대부분의 고급 언어 모델링 기술은 단순한 기준선에 비해 아주 작은 개선 사항만 제공하며 실제로 거의 사용되지 않는다.

Model description

순차 데이터를 모델링하기 위해 반복 신경망에 대해 조사하기로 결정했다. 통계 언어 모델링에서 인공 신경망을 사용하는 것은 고정된 길이 컨텍스트를 가진 feedforward 신경망을 사용한 Bengio에 의해 이미 제안됐다. 이 접근 방식은 예외적으로 성공적이었으며 Goodman의 추가 조사를 통해 이 단일 모델이 클래스 기반 모델을 포함한 다른 기술을 기반으로 한 여러 모델의 혼합보다 성능이 우수하다는 것을 알 수 있다. 이후, Schwenk는 신경망 기반 모델이 양호한 기준선 시스템에 대한 몇 가지 작업에 대해 음성 인식의 상당한 향상을 제공한다는 것을 보여주었다.

Bengio 접근 방식의 주요 결점은 feedforward 네트워크가 훈련 전에 특별하게 지정되어야하는 고정된 길이의 컨텍스트를 사용해야 한다는 것이다. 보통 이것은 신경망이 다음 단어를 예측할 때 5개에서 10개의 단어만 본다는 것을 의미한다. 인간이 더 긴 문맥을 성공적으로 이용할 수 있다는 것은 잘 알려져 있다. 또한 캐시 모델은 신경망 모델에 보완 정보를 제공하므로 임의의 길이를 가진 컨텍스트에 대해 시간 정보를 암시적으로 인코딩하는 모델을 생각하는 것은 당연하다.

반복 신경망은 제한된 크기의 컨텍스트를 사용하지 않는다. 반복적인 연결을 사용함으로써, 정보는 임의로 오랜 시간 동안 이러한 네트워크 내부에서 순환할 수 있다. 하지만, 확률적 경사 하강에 의한 long-term dependencies를 학습하는 것은 상당히 여려울 수 있다는 주장도 종종 제기된다.

우리의 연구에서, 우리는 보통 단순 반복 신경망 또는 Elman 네트워크라고 불리는 아키텍처를 사용했다. 이것은 아마도 반복 신경망의 가장 단순한 버전일 것이며 구현과 훈련이 매우 쉽다. 네트워크에는 입력 계층 x, 숨겨진 계층 s(context layer 또는 state) 및 출력 계층 y가 있다. 시간 t로 입력은 x(t), 출력은 y(t), 히든 레이어는 s(t)로 나타낸다. 입력 벡터 x(t)는 현재 단어를 나타내는 벡터 w와 시간 t-1에서 컨텍스트 레이어의 s의 뉴런 출력값을 연결하여 형성된다. input, hidden, output layer는 다음과 같이 계산된다.

함수 $f(z)$는 시그모이드 활성화 함수로 아래와 같다.

함수 $g(z)$는 소프트맥스 함수로 아래와 같다.

초기화의 경우 s(0)은 많은 양의 데이터를 처리할 때 초기화는 중요하지 않은 0.1과 같이 작은 값의 벡터로 설정될 수 있다. 다음 시간 단계에서 s(t+1)는 s(t)의 사본이다. 입력 벡터 x(t)는 N 코드화 1(one-hot 인코딩)을 사용하여 인코딩된 단어 t를 나타내며 벡터 x의 이전 컨텍스트 레이어 크기는 사전 V의 크기와 같다.(실제로 30,000 ~ 200,000). 컨텍스트(hidden) 레이어의 크기는 일반적으로 30 ~ 500 hidden 단위이다. 우리의 실험에 따르면, hidden 레이어의 크기는 훈련 데이터의 양을 반영해야 한다. 많은 양의 경우

네트워크는 훈련 말뭉치의 모든 데이터가 순차적으로 표시되는 여러 epoch에서 훈련된다. 가중치는 작은 값으로 초기화 된다.(평균이 0이고 분산이 0.1인 랜덤 가우시안 노이즈로) 네트워크를 훈련시키기 위해 확률적 경사 하강을 가진 backpropagation 알고리즘을 사용한다. 시작 학습률은 α = 0.1입니다. 각 epoch 이후, 네트워크는 유효성 검사 데이터에 대해 테스트된다. 검증 데이터의 로그-라이클리후드가 증가하면 새로운 epoch에서도 학습을 계속한다. 유의미한 개선이 보이지 않으면, 학습률 $\alpha$는 새로운 epoch가 시작할 때마다 절반으로 감소한다. 다시 이렇다할 개선이 없으면 훈련이 끝난다. 수렴은 보통 10~20 epoch 후에 이뤄진다.

우리의 실험에서, 네트워크는 매우 큰 hidden 레이어를 사용하더라도 크게 오베트레이닝되지 않는다. (- 큰 가중치에 불이익을 주기 위한 네트워크의 정규화는 큰 개선을 제공하지 않았다.) 출력 계층 y(t)는 이전단어 w(t)와 컨텍스트(t-1)가 주어진 다음 단어의 확률 분포를 나타낸다. 소프트맥스는 이 확률 분포가 유효한지 확인하다.

각 교육 단계에서 교차 엔트로피 기준에 따라 오류 벡터가 계산되고 backpropagation 알고리즘으로 가중치가 업데이트 된다. $error(t)=desired(t)-y(t)$

desired는 1-of-N 코딩 표현을 사용한 벡터로 특정 컨텍스트에서 예측되는 단어를 나타내고 y(t)는 실제 네트워크로부터의 출력이다.

통계적 언어 모델링의 훈련 단계와 시험 단계는 일반적으로 시험 데이터가 처리될 때 모델이 업데이트되지 않는다는 점에서 다르다. 따라서, 새로운 사람 이름이 테스트 세트에서 반복적으로 발생한다면, 알려진 단어로 구성되더라도 반복적으로 매우 작은 확률을 얻게 될 것이다. 이러한 long term 메모리는 컨텍스트 유닉의 활성화(이러한 매우 빠르게 변화함에 따라)가 아니라 시냅스 자체에 있어야 하며, 네트워크가 테스트 단계 중에도 훈련을 계속해야 한다고 가정할 수 있다. 우리는 그러한 모델을 동적 모델이라고 부른다. 동적 모델의 경우 고정 학습 속도 α = 0.1을 사용한다. 학습 단계에서는 모든 데이터가 epoch에서 여러 번 네트워크에 제공되지만, 동적 모델은 테스트 데이터를 처리할 때 한 번만 업데이트된다. 이것은 물론 최적의 솔루션은 아니지만, 우리가 볼 수 있듯이 정적 모델에 대한 큰 난이도 감소를 얻기에 충분하다. 이러한 수정은 신경 네트워크가 연속 공간에서 학습하는 차이와 함께 backoff 모델의 캐시 기법과 매우 유사하므로, '개'와 '고양이'가 관련이 있는 경우, 테스트 데이터에서 '개'가 자주 발생하는 것도 '고양이'의 확률을 높일 수 있다는 점에 유의한다.

따라서 동적으로 업데이트된 모델은 새로운 도메인에 자동으로 적응할 수 있다. 그러나 음성 인식 실험에서 역사는 인식자에 의해 주어진 가설로 표현되며 인식 오류를 포함한다. 이는 일반적으로 ASR에서 캐시 n-gram 모델의 성능 저하를 초래한다.

여기서 설명하는 학습 알고리즘은 τ = 1을 사용한 시간 경과에 따른 잘린 backpropagation라고도 한다. 현재 시간 단계에 대해서만 계산된 오류 벡터를 기반으로 네트워크의 가중치가 업데이트되기 때문에 최적화되지 않는다. 이러한 단순화를 극복하기 위해 BPTT(Back Propagation through Time) 알고리즘이 일반적으로 사용된다.

Bengio와 schwenk에서 사용하는 feedforward 신경망과 반복 신경망 사이의 주요 차이점 중 하나는 훈련 전에 조정하거나 특별하게 선택해야 하는 매개 변수의 양이다. RNN LM의 경우 hidden(컨텍스트) 계층의 크기만 선택하면 된다. feedforward 네트워크의 경우 단어를 저차원 공간에 투영하는 계층의 크기, 숨겨진 계층의 크기 및 컨텍스트 길이를 조정해야한다.

Optimization

성능을 향상시키기 위해, 우리는 (훈련 텍스트에서) 임계값(threshold)보다 적게 발생하는 모든 단어를 특별한 rare 토큰으로 병합한다. 단어-확률(Word-probabilities) 계산은 아래와 같다.

여기서 $C_{rare}$는 단어에서 임계값보다 적게 발생하는 단어 수입니다. 따라서 모든 rare 단어는 동등하게 취급된다. 즉, 확률은 균일하게 분배된다. Schwenk는 추가적인 성능 향상에 사용할 수 있는 몇 가지 접근 방식을 설명한다. 추가 가능성은 [10][11][12]에서도 논의되며, 대부분의 가능성을 RNN에도 적용할 수 있다. 비교를 위해, 우리의 기본 구현이 브라운 말뭉치(800K 단어, 100개의 숨겨진 단위 및 어휘 임계값(vocabulary threshold 5)를 기반으로 RNN 모델을 훈련하는 데 약 6시간이 소요되며, Bengio는 유사한 데이터와 신경망 크기를 사용할 때 기본 구현에 113일, 중요도 샘플링 [10]으로 26시간을 걸렸다고 보고서에 썼다. 계산 속도를 올리기 위해 BLAS 라이브러리를 사용한다.

Conclusion and future work

반복 신경망은 모든 실험에서 최첨단 backoff 모델보다 훨씬 더 많은 데이터에 대해 backoff 모델을 훈련한 경우에도 훨씬 더 우수한 성능을 보였다. WSJ 실험에서는 동일한 양의 데이터에 대해 훈련된 모델의 경우 워드 오류율 감소가 약 18%, 백오프 모델이 5번 훈련되었을 때 12%이다. RNN 모델보다 데이터 수가 더 많습니다. NIST RT05의 경우, 우리는 모델이 단 5번에 대해 훈련되었다고 결론을 내릴 수 있다. 5.4백만 단어의 도메인 내 데이터는 수백 배 많은 데이터에 대해 훈련된 빅 backoff 모델을 능가할 수 있습니다. 언어 모델링은 단지 n-gram(n-gram)의 계산에 관한 것이며, 결과를 개선하는 유일한 합리적인 방법은 새로운 훈련 데이터를 획득 하는 것이라는 속설을 깨는 결과이다.

표 2에 보고된 난해성 개선은 온라인 학습의 매우 중요한 효과(본 논문에서는 동적 모델이라고도 하며 비지도 LM 훈련 기법과 매우 유사한 음성인식 맥락에서)와 유사한 데이터 세트에 대해 보고된 최대 중 하나이다. WER은 약간만 영향을 받고 정확한 테스트 데이터 순서가 필요하지만, 온라인 학습은 캐시와 트리거 같은 정보를 얻는 자연스러운 방법을 제공하므로 더 자세히 조사해야한다.(데이터 압축의 경우, 예를 들어, 예측 신경망 훈련을 위한 온라인 기술은 이미 Mahoney에 의해 연구되었다.) 언어를 실제로 배울 수 있는 모델을 구축하려면 온라인 학습이 매우 중요합니다. 새로운 정보를 얻는 것은 확실히 중요합니다. 반복 신경망 학습을 위한 시간 알고리즘을 통한 역전파에 대한 추가 조사가 추가적인 개선을 제공할 수 있다. 장난감 작업에 대한 예비 결과는 유망하다. 그러나 캐시 모델은 BPTT로 훈련된 동적 모델에까지 여전히 보완 정보를 제공하기 때문에 단순한 반복 신경망은 정말 긴 컨텍스트 정보를 캡쳐할 수 있는 것 같지는 않다. 설명은 [6]에서 논의한다.

task에서 task 또는 언어별 가정을 하지 않았기 때문에 기계번역이나 OCR과 같은 backoff 언어 모델을 사용하는 모든 종류의 애플리케이션에서 RNN 기반 모델을 거의 쉽게 사용할 수 있다. 특히, [12]에서 이미 설명한 것처럼, 큰 어휘를 가진 변곡 언어 또는 언어를 포함하는 작업은 NN 기반 모델을 사용함으로써 이득을 얻을 수 있다.

연구에서 보고된 매우 좋은 결과 외에도, 제안된 반복 신경망 모델은 언어 모델링을 기계 학습, 데이터 압축 및 인지 과학 연구와 더 밀접하게 연결하기 때문에 흥미롭다. 앞으로 이러한 connection이 더 잘 이해되기를 바란다.

논문 리뷰

전반적으로 n-gram에서 진화했다는 것에 초점을 맞춘 논문 같다. 내가 느낀 바로는 사람은 단어를 무한히 듣고 답할 수 있는데 n-gram 모델은 제한적인 입력을 받는 것으로 이거를 까려고? 만든 논문이라는 느낌이다. 핵심으로는 BPTT를 사용했다는 것과 semantic semantic utterance meaning으로 vocabulary에 없는 단어가 들어왔을때도 비슷한 단어를 찾아 결과를 낸다는 것 같다.