• https://gyoogle.dev/blog/
• https://zeddios.tistory.com/20

거품 정렬 (Bubble Sort)

설명

버블 소트란
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않을 경우 자리를 교환하며 정렬하는 알고리즘이다.

이름의 유래
정렬 과정에서 원소의 이동이 거품이 수면 위로 올라오는 듯한 모습을 보이기 때문

과정

1. 1회전 : n-1과 n번째 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
   1회전을 수행하면 가장 큰 원소가 맨 뒤[-1]로 이동하게 된다.

2. 2회전 : 1회전에서 가장 큰 원소가 맨 뒤로 이동하므로, 원소 정렬 과정에서 맨 끝에 있는 원소를 제외한다.
   2회전을 수행하면 그다음 큰 원소가 맨 뒤에서 두번째 위치[-2]로 이동한다.

구현

def bubble_sort(arr):
    n = len(arr)
    for i in range(n): # 1
        print(i," ",1,n-i,arr)
        for j in range(1, n-i): # 2
            if arr[j-1] > arr[j]: # 3
                arr[j-1], arr[j] = arr[j], arr[j-1]
    print(arr)


bubble_sort([1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7])
"""
0   1 14 [1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
1   1 13 [1, 0, 4, 6, 3, 2, 5, 7, 3, 5, 8, 7, 7, 8]
2   1 12 [0, 1, 4, 3, 2, 5, 6, 3, 5, 7, 7, 7, 8, 8]
3   1 11 [0, 1, 3, 2, 4, 5, 3, 5, 6, 7, 7, 7, 8, 8]
4   1 10 [0, 1, 2, 3, 4, 3, 5, 5, 6, 7, 7, 7, 8, 8]
5   1 9 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
6   1 8 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
7   1 7 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
8   1 6 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
9   1 5 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
10   1 4 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
11   1 3 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
12   1 2 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
13   1 1 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
"""         

1. 제외될 원소의 개수를 의미한다.
   i회전이 끝나면 배열의 n-i 인덱스에 i번째 큰 원소가 위치한다.

2. j는 비교할 원소의 인덱스를 의미한다.
   j-1 : 이전 원소, j : 현재 원소

3. 두 원소의 크기 비교를 한다.
   이전 원소가 현재 원소보다 크면 두 자리를 교환한다.

시간복잡도

• n-1
  n-2
  n-3
  ...
  2
  1
  => n(n-1)/2 => O(n^2)

• 정렬되있지 않은 배열 속 원소들을 비교하기 때문에
  최선, 최악, 평균의 경우 모두 시간복잡도가 O(n^2) 이다.

공간복잡도

교환을 통해 정렬이 수행된다. n개의 원소에 대해 n개의 메모리를 사용한다.
=> O(n)

장점

구현이 간단하고, 소스코드가 직관적이다.
정렬을 하는 과정에서 주어진 배열 이외의 다른 메모리 공간을 요하지 않는다
안정 정렬이다.

단점

시간복잡도가 최악,최선,평균 모두 O(N^2)
정렬되어있지 않을 원소에 대한 교환 연산이 많이 일어난다.

선택 정렬 (Selection sort)

설명

해당 순서에 원소를 넣을 위치는 이미 정해져 있고,
어떤 원소를 넣을지 선택하는 알고리즘이다.

1. 해당 자리를 선택하고
2. 그 선택한 자리에 올 값을 찾는 것

과정

[9,1,6,8,4,3,2,0]
1. 앞에서 부터 데이터를 하나 선택한다. ->9
2. 선택한 데이터 이후에 있는 원소들 중 가장 작은 값을 찾는다. -> min(arr[1:]) == 0
3. 찾은 최소값과 1번에서 선택한 원소의 자리를 바꾼다.
-> 9와 0의 자리를 바꾼다.

구현

def selection_sort(arr):
    n = len(arr)
    print(f"{arr=}")
    for i in range(n-1):
        idx = i
        for j in range(i+1, n):
            if arr[idx] > arr[j]:
                idx = j
        arr[i], arr[idx] = arr[idx], arr[i]
        print(f"{i}: {i+1},{n} {arr}")
    
    print(arr)
"""
arr=[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
0: 1,14 [0, 4, 1, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
1: 2,14 [0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
2: 3,14 [0, 1, 2, 6, 8, 3, 4, 5, 7, 3, 5, 8, 7, 7]
3: 4,14 [0, 1, 2, 3, 8, 6, 4, 5, 7, 3, 5, 8, 7, 7]
4: 5,14 [0, 1, 2, 3, 3, 6, 4, 5, 7, 8, 5, 8, 7, 7]
5: 6,14 [0, 1, 2, 3, 3, 4, 6, 5, 7, 8, 5, 8, 7, 7]
6: 7,14 [0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 5, 8, 7, 7]
7: 8,14 [0, 1, 2, 3, 3, 4, 5, 5, 7, 8, 6, 8, 7, 7]
8: 9,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 8, 7, 8, 7, 7]
9: 10,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 7, 7]
10: 11,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 7]
11: 12,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
12: 13,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
"""

시간 복잡도

n-1 + n-2 + ... + 2 + 1 = n(n-1)/2
=> O(N^2)
최선, 최악, 평균의 경우 모두 동일

공간 복잡도

n개의 원소를 교환을 통해 정렬이 수행된다
=> O(N)

장점

알고리즘이 단순하다
버블 소트보다 교환하는 횟수는 적다
제자리 정렬이다 = 배열속에서 교환하는 방식 = 다른 메모리 공간이 필요하지 않는다.

단점

시간복잡도가 O(N^2)으로 비효율적
불안정 정렬이다.

---

삽입 정렬

설명

배열의 모든 요소를 앞에서부터 차례대로
이미 정렬된 배열 부분과 비교하여
자신의 위치를 찾아 삽입하여 정렬을 완성한다.

다시말해
2번째 원소부터 시작하여
현재 i번째일 경우, arr[0:i-1]의 원소들과 비교하여
삽입할 위치를 지정한뒤
원소를 뒤로 옮기고 지정된 자리에 자료를 삽입한다.

최선의 경우 O(N)이라는 빠른 효율성을 가진다.

과정

1. 정렬은 2번째 인덱스부터 시작(선택)한다
   (맨 처음 정렬할 경우에만. 왜냐하면 첫번째 리스트는 1번째 인덱스의 원소 하나로만 이루어진 정렬된 상태로 보기 때문이다.)
   그리고 선택한 원소를 key 변수에 저장한다.
2. key 변수와 key변수보다 앞에 있는 원소들과 크기 비교 후 올바른 위치에 key 변수를 삽입한다.
3. 1번으로 돌아가 그 다음 인덱스를 key 변수에 저장한다.

구현

def insertion_sort(arr):
    n = len(arr)
    print(arr)

    for i in range(1, n):
        key = arr[i]
        print(f"{i}: {key=}")
        prev = i - 1
        while prev >= 0 and arr[prev] > key:
            arr[prev + 1] = arr[prev]
            prev -= 1
            print(arr)
        arr[prev + 1] = key
        print(f"{arr} !!")
    print(arr)
"""
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
1: key=4
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
2: key=0
[1, 4, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
[1, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
3: key=6
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
4: key=8
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
5: key=3
[0, 1, 4, 6, 8, 8, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 6, 6, 8, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 4, 6, 8, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 4, 6, 8, 2, 5, 7, 3, 5, 8, 7, 7] !!
6: key=2
[0, 1, 3, 4, 6, 8, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 4, 6, 6, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 4, 4, 6, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 3, 4, 6, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 6, 8, 5, 7, 3, 5, 8, 7, 7] !!
7: key=5
[0, 1, 2, 3, 4, 6, 8, 8, 7, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 6, 6, 8, 7, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 3, 5, 8, 7, 7] !!
8: key=7
[0, 1, 2, 3, 4, 5, 6, 8, 8, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 3, 5, 8, 7, 7] !!
9: key=3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 6, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 5, 8, 7, 7] !!
10: key=5
[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 7, 7] !!
11: key=8
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 7, 7] !!
12: key=7
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 7]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 7]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 7] !!
13: key=7
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8] !!
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
"""

1. 배열의 첫번째 원소 앞부분에는 원소가 없기 때문에 두번째 원소부터 탐색을 시작한다.
   key 변수에 임시로 해당 인덱스의 값을 저장하고, prev 변수에는 해당 위치 바로 이전 위치를 저장한다.
2. 이전 위치를 가리키는 변수 prev가 음수가 되지 않고, 1번에서 선택한 원소보다 클 경우에만 서로의 값을 교환해주고, prev 변수를 더 이전의 위치를 가리키도록 -1 한다.
3. 2번의 반복문이 끝나면
   prev 변수에는 key값보다 작은 값들중 가장 큰 값의 위치가 담겨 있다.
   따라서 prev 위치 바로 뒤에 key 변수에 담긴 값을 넣어준다.

시간복잡도

(n-1) + (n-2) + .... + 2 + 1 = n(n-1)/2
=> O(N^2)
하지만 입력된 배열이 정렬된 경우
비교 연산을 1번씩만 하게된다
=> 최선의 경우 O(N), 최악,평균이 경우 O(N^2)

공간복잡도

n크기의 배열에서 교환이 n번 수행된다 => O(N)

장점

원소가 이미 정렬된 경우, 매우 효율적
제자리 정렬이다 = 배열안에서 교환하므로 다른 메모리 공간을 필요로하지 않는다.
안정 정렬이다.
선택정렬, 버블 정렬보다 상대적으로 빠르다

단점

최악,평균의 경우 시간복잡도가 O(N^2)이다
배열의 길이가 길어질 수록 비효율적이다.

선택정렬과 비교

유사점
k번째 반복 이후, 첫번째 k요소가 정렬된 순서로 온다

차이점
선택정렬 : k+1번째 요소를 찾기 위해 나머지 모든 요소를 탐색
삽입정렬 : k+1번째 요소를 배치하는데 필요한 요소만 탐색 (훨씬 효율적)

---

퀵 정렬

설명

분할 정복 (divide and conquer) 방법을 통해 배열을 정렬한다.

분할정렬이란
문제를 작은 2개의 문제로 분리하여 각각 해결한 뒤,
결과를 모아서 원래의 문제를 해결하는 전략

불안정 정렬에 속한다.
다른 원소와의 비교만으로 정렬을 수행할 수 있다 => 비교정렬
merge sort와 달리 배열을 비균등하게 분할한다.

과정

1. 배열 가운데에서 하나의 원소를 고른다. 고른 원소를 피벗(pivot)이라고 한다.
2. 피벗앞에는 피벗보다 작은 원소들이 오고
   피벗 뒤에는 피벗보다 큰 우너소들이 오도록
   피벗을 기준으로 배열을 둘로 나눈다.
   이렇게 배열을 둘로 나누는 것을 분할(divide)라고 한다.
3. 분할된 두개의 작은 배열에 대해 재귀적으로 1,2번 과정을 반복한다.

구현

def quick_sort(arr, left, right):
    if left >= right:
        return
    print(f"{left=} {right=} \n{arr}")
    pivot = partition(arr, left, right)
    quick_sort(arr, left, pivot - 1)
    quick_sort(arr, pivot + 1, right)


def partition(arr, left, right):  # 비 균등하게 나눈다.
    pivot = arr[left]  # 가장 왼쪽의 값을 피벗으로 설정한다
    i = left
    j = right
    print(f"--partition {left=} {right=} --")
    print(arr)
    print(f"{i=} {j=} pivot = arr[left] = {pivot}")
    while i < j:
        while pivot < arr[j]: 
            j -= 1
        while i < j and pivot >= arr[i]:
            i += 1
        print(f"i={i}({arr[i]}) j={j}({arr[j]}) 교환")
        arr[i], arr[j] = arr[j], arr[i]
        print(arr)

    arr[left] = arr[i]
    arr[i] = pivot
    print(arr, i, f"번({arr[i]}) 기준\n")
    return i


quick_sort(arr, 0, len(arr)-1)

"""
left=0 right=13 
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
--partition left=0 right=13 --
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
i=0 j=13 pivot = arr[left] = 1
i=1(4) j=2(0) 교환
[1, 0, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
i=1(0) j=1(0) 교환
[1, 0, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] 1 번(1) 기준

left=2 right=13
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
--partition left=2 right=13 --
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
i=2 j=13 pivot = arr[left] = 4
i=3(6) j=9(3) 교환
[0, 1, 4, 3, 8, 3, 2, 5, 7, 6, 5, 8, 7, 7]
i=4(8) j=6(2) 교환
[0, 1, 4, 3, 2, 3, 8, 5, 7, 6, 5, 8, 7, 7]
i=5(3) j=5(3) 교환
[0, 1, 4, 3, 2, 3, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7] 5 번(4) 기준

left=2 right=4
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7]
--partition left=2 right=4 --
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7]
i=2 j=4 pivot = arr[left] = 3
i=4(2) j=4(2) 교환
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7] 4 번(3) 기준

left=2 right=3
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
--partition left=2 right=3 --
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
i=2 j=3 pivot = arr[left] = 2
i=2(2) j=2(2) 교환
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7] 2 번(2) 기준

left=6 right=13
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
--partition left=6 right=13 --
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
i=6 j=13 pivot = arr[left] = 8
i=13(7) j=13(7) 교환
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 8, 7, 8] 13 번(8) 기준

left=6 right=12
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 8, 7, 8]
--partition left=6 right=12 --
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 8, 7, 8]
i=6 j=12 pivot = arr[left] = 7
i=11(8) j=12(7) 교환
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
i=11(7) j=11(7) 교환
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8] 11 번(7) 기준

left=6 right=10
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
--partition left=6 right=10 --
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
i=6 j=10 pivot = arr[left] = 7
i=10(5) j=10(5) 교환
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8] 10 번(7) 기준

left=6 right=9
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
--partition left=6 right=9 --
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
i=6 j=9 pivot = arr[left] = 5
i=7(5) j=7(5) 교환
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8] 7 번(5) 기준

left=8 right=9
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
--partition left=8 right=9 --
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
i=8 j=9 pivot = arr[left] = 7
i=9(6) j=9(6) 교환
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8] 9 번(7) 기준
"""

퀵소트 개선

partition 함수에서 피벗 값이 최소나 최대 값으로 지정되어 파티션이 나누어지지 않을 경우
=> O(N^2)의 시간복잡도를 가진다.

배열의 가장 앞의 값(left)과 중간 값(mid == left+right//2)을 교환해주면 확률적으로 시간복잡도를 개선할 수 있다.
=> O(nlog_2n) 하지만 최악의 시간복잡도가 이렇게 되는 것은 아니다.

시간복잡도

• 최선의 경우 = O(nlog_2n)

전체 호출 횟수 (순환 호출의 깊이) = log_2n
각 호출 단계의 비교 연산 = n
=> n * log_2n

• 최악의 경우 = O(N^2)

정렬하려는 배열이 오름차순 또는 내림차순 정렬이 되어있는 경우
전체 호출 횟수 (순환 호출의 깊이) = n
각 호출 단계의 비교 연산 = n
=> n * n

• 평균의 경우 = O(nlog_2n)

공간복잡도

n 크기의 주어진 배열에서 교환을 통해 정렬이 수행된다
=> O(N)

장점

• 불필요한 데이터의 이동을 줄인다, 먼 거리의 데이터를 교환할 수 있다, 한번 결정된 피벗들은 비교에서 제외된다
  => 시간복잡도가 O(nlog2n)으로 다른 정렬 알고리즘 보다 빠르다
• 배열 안에서 교환하기 때문에 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬이다.
• 정렬된 배열에 대해서는 불균형 분할로 인해 수행시간이 더 걸린다.

자바의 Arrays.sort() 는 내부적으로 dual pivot quick sort로 구현되어있다.

기술면접에서 빈번히 나오는 주제이다.