내배캠 TIL 2022.11.15 (알고리즘 3주차)

스택 stack: 나중에 들어간 것이 먼저 나온다

큐queue: 먼저들어간 것이 먼저 나온다

 

해쉬: 해쉬 태그할 때 쓰는 기술인가?

 

정렬

버블 정렬

앞뒤 자리를 비교해가면서 자리를 변경해가는게 버블 정렬이다.

한번 돌 때 가장 큰 숫자를 제일 뒤로 보낸다

제일 뒤 숫자를 빼고 같은 행동을 반복하면 결국은 순서대로 정렬이 된다.

 

두 변수의 값을 교체하는 법 swap

a,b = b,a 라고 쓰면 된다.

 

그러면 이제 한 번 구현하러 가볼게요! Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오.

줄어들면서 반복되는 것.... 재귀함수?

 

인덱스 구하기

for i in range(5 - 1):
    for j in range(5 - i - 1):
        print(j)

 순서대로 정렬하는 함수

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    n = len(array)
    for i in range(n-1):
        for j in range(n -i -1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]

    return array


bubble_sort(input)
print(input

시간복잡도는 O(N^2)

 

선택정렬

전체 배열을 보고 가장 작은 숫자를 찾아서 그 숫자를 맨 앞에 놓는 식이다.

그 다음에는 맨 앞자리 숫자 빼고 같은 행동을 반복한다.

 

배열 안에서 서로 서로 비교하면서 가장 작은 숫자를 찾아야하기 때문에 2중 반복문 구조를 띈다.

 

비교할 때 쓸 인덱스 구하기

for i in range(5-1):
    for j in range(5-i):
        print(i + j)

# range(4) = 0,1,2,3 

0부터 넣은 숫자 -1 까지 범위를 잡는다.

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i + j] < array[min_index]:
                array[i + j], array[min_index] = array[min_index], array[i + j]

    return array


selection_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ", selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ", selection_sort([3, -1, 17, 9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ", selection_sort([100, 56, -3, 32, 44]))

반복문이 2번 들어가서 시간복잡도 빅오표기법 최악의 경우 O(N^2)

 

삽입정렬

선택 정렬은 전체에서 최솟값을 선택하는 것

삽입 정렬은 전체에서 하나씩 올바른 위치에 삽입하는 것

 

[4,6,2,9,1] 이 있을 때

1) 4는 처음에 그냥 정렬

2) 6은 4랑 비교해서 더 크니까 제자리

3) 2는 6보다 작으니까  둘을 변경 4보다 작으니까 둘을 변경

4) 9는 6보다 크니까 제자리

5) 1은 9보다 작으니까 둘을 변경, 6보다 작으니까 둘을 변경, 4보다 작으니까 둘을 변경, 2보다 작으니까 둘을 변경  

 

인덱스 구하기

for i in range(1, 5):
    for j in range(i):
        print(i - j)

 

input = [4, 6, 2, 9, 1]

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array


insertion_sort(input)
print(input)

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

 

버블 정렬과, 선택 정렬은 O(N^2)의 시간 복잡도를 가진다. 그리고 최악의 경우나 최선의 경우나 항~상 N^2 만큼의 시간 복잡도를 가진다. 삽입 정렬도 O(N^2)를 가지나 차이가 있다. 

삽입 정렬은 앞에 정렬 된 것들은 이미 순서되로 정렬되어 있다.

그렇기 때문에 새로 들어온 숫자와 마지막으로 정렬되어있던 숫자와 비교해서 새로 들어온 숫자가 더 클 때

당연히 그 앞에 정렬되어 있는 숫자보다도 더 크기 때문에 더 비교해보지 않아도 되고

break를 써주고 다음 숫자 비교로 넘어가도 된다.  

그래서 최선의 경우 시간 복잡도는 Ω(N)이다. 

배열이 거의 다 정렬이 된 상태에서 들어온 경우 조금의 이득이 있다.

 

병합정렬

 

병합 merge

두 정렬의 각각 요소들을 비교하면서  제 3의 정렬에 작은 것 부터 차근차근 넣으면서 병합한다.

비교할 대상이 이제 없는 나머지 대상을 그냥 넣어주면 된다.

 

 

어려우면 그냥 한번 코드 따라쳐보고 끝! 자꾸하다보면 되겠지

이해하다가 힘들면 다른 강의 듣자.

len()

array_a = [1, 2, 3, 5]
print(len(array_a))

 

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    array_c = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index += 1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            array_c.append(array1[array1_index])
            array1_index += 1
    return array_c


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge([-7, -1, 9, 40], [5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge([-1, 2, 3, 5, 40], [10, 78, 100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge([-1, -1, 0], [1, 6, 9, 10]))

 

선행조건은 두 배열 다 순서대로 정렬되어 있을 경우만 쓸 수 있다.

1. 빈 배열 만든다 

2. 1씩 더해줄 인덱스 값 0을 각각 배열에 만들어준다.

3. 배열의 길이 len()보다 index가 적을 때를 조건으로 둬서 인덱스보다 숫자가 커지지 않도록 한다.

4. 인덱스를 이용해서 두 배열의 값을 비교하고 적은 숫자를 array_c에 넣어준다.

배열 a의 값이 작은 경우와 배열 값이 작은 경우 두 가지 경우를 다 써준다.

5.  하나의 배열의 값은 다 넣었는데 다른 배열의 값은 남았을 경우=배열의 인덱스가  배열의 길이 len()과 같아진 경우

다른 배열의 인덱스도 배열의 길이 len()과 같아 질때까지 array_c에 값을 넣는다. 

배열 a가 먼저 끝날 경우와 배열 b가 먼저 끝날 경우 두 가지 경우를 다 조건으로 써 준다.  

 

병합 정렬 merge sort

분할 정복 divide and conquer 개념을 적용한다. 

작은 2개의 문제로 분리해서 해결하고, 결과를 모아서 원래의 결과를 해결하는 전략

그냥 머지하면 먼저 정렬을 해야하는데

다 쪼개서 숫자 하나하나 위의 머지 방법으로 비교하면서 합쳐주면 결과적으로는 정렬되면서 병합이 된다.

 

이 안에서 반복되면서 합쳐야할 배열들의 수는 줄어든다 이런 두 가지 특징 있으면 재귀함수를 이용해 볼 수 있다.

간단 코드로 써보자면

MergeSort(0,N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))

나눌 때 슬라이싱을 이용하는데, 홀수를 자를 때 중간에 수를 놓치면 어떡하나 걱정했는데

자릿수 기준으로 앞뒤로 나눠주는 방식을 쓰기 때문에

 

탈출 조건은 문자열이 1보다 작거나 같을 때 

array = [5, 3, 2, 1, 6, 8, 7, 4]


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])   # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:])  # 오른쪽 부분을 정렬한 다음에
    return merge(left_array, right_array)   # 합치면서 정렬하면 됩니다!


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge_sort([-7, -1, 9, 40, 5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge_sort([-1, 2, 3, 5, 40, 10, 78, 100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge_sort([-1, -1, 0, 1, 6, 9, 10]))

시간복잡도는 O(N^2)이라고 생각했는데

답은 O(N*log2N)이라고 한다

git 명령어

cd 들어가기

..cd 나가기

pwd 현재 위치 확인

clear: 명령창 깨끗하게

 

git init : . git 숨김폴더 생성하면서 작업디렉토리 생성

touch + 만들 파일 : 비어있는 파일 생성

git status: 작업 디렉토리 상태 확인 (변경사항이 있는지 없는지, 그 변경 사항이 스테이지에 올라갔는지 아닌지 보여준다.)

git add + 파일 이름 : 스테이지에 올려주기

git commit -m "커밋 메세지": 커밋하기

git log: 지금까지 만들어준 버전들의 목록을 확인한다(날짜, 만든 사람, 커밋 해시가 나온다)

 

터미널 내부 편집기 쓰기

자세하게 커밋 메세지를 쓰고 싶으면 git commit 만 넣고 엔터 

그러면 내가 갇혔던 창이 뜬다. vi 창( 터미널 내부에서 파일을 수정하고 삭제할 수 있는 편집기)

# 위에 한칸 비워져 있는 곳에 커밋 메세지 쓴다. 

a 누르면 인서트 뜬다

esc 누르면 나가진다

i 누르면 인서트 뜬다

o 누르면 한칸 띄우고 새로운 내용을 입력해라

 

1. 인서트 모드로 들어간다.

2. 젤 윗줄은 노란색으로 커밋 메세지

3. 줄바꾸고 한칸 띄우고 쓰면 회색으로 description 써진다.

4. 쓰고 esc 해서 insert 모드에서 나간다.

5. :(콜론)+ w 눌러서 작성내용 저장

6. : (콜론) +q 눌러서 편집기에서 나간다.

(:콜론 +wq 같이 써주면 저장 나가기 같이 한다)

 

git add .(점) : 변경사항 다 스테이지에 올리기

git commit -am "커밋메세지": 스테이지에 올리는 것과 커밋하는 것을 같이 하기

(한번이라도 변경사항을 추적해보았던 파일의 변경사항에 한해서 가능= 이전에 커밋해봤던 디렉토리 한해서 가능?)