제로초님의 강의를 보고 실습해보았습니다.

합병 정렬

이번엔 합병 정렬에 대해 알아보겠다. 합병 정렬은 O(NlogN)의 복잡도를 가진 정렬로 준수한 성능을 가졌다고 한다. 다만, 30개 이하일 때는 삽입정렬이랑 별 차이가 없다고 한다. 합병 정렬은 분할 정복 알고리즘에 속하는데, 폰 노이만에 의해 개발되었다고 한다. 분할 정복이란 어떤 문제를 그대로 해결할 수 없을 때, 작은 문제로 분할해서 푸는 방법이다.

이 합병 정렬은 배열을 두 개로 나누고, 나눈 것을 다시 두개로 계속 나눠 정렬 한다. 이를 위해 재귀함수를 이용해서 계속 쪼개주고 쪼갤 수 없을 때까지 나눈 후, 좌 우 비교해서 큰 것을 새로운 배열에 입력해준다. 이 때 새로운 배열이 필요하기에 새로운 메모리가 요구되기도 한다.

파이썬 예시

def merge_sort(arr):
    if len(arr) < 2: return arr
    pivot = len(arr) // 2
    left = arr[0:pivot]
    right = arr[pivot:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    result = []
    while len(left) and len(right):
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    while len(left): result.append(left.pop(0))
    while len(right): result.append(right.pop(0))
    return result


print(merge_sort([5, 2, 4, 7, 6, 1, 3, 8]))

느낀점

재귀함수 부분인 merge(merge_sort(left), merge_sort(right))에서 첫번째 인자 부분의 재귀를 먼저 처리하고 이후에 두번째 재귀를 처리함을 알 수 있게 되었다. 근데 재귀는 정말 헷갈리는거 같다..

제로초님의 강의를 보고 실습해보았습니다.

기초적인 정렬 중 하나인 삽입 정렬에 대해 알아보겠다. 삽입 정렬은 두 번째 숫자부터 이전의 숫자를 비교해서 정렬하는 방법이다.

예시

1. [5, 6, 1, 2, 4, 3] 처음의 배열 예시이다.
2. [5, 6, 1, 2, 4, 3] 앞의 5와 비교하는데 5보다 크기 때문에 그냥 그 자리에 둔다.
3. [5, 6, 1, 2, 4, 3] 1은 앞의 5, 6보다 작기 때문에 5, 6 앞에 넣어준다.
4. [1, 5, 6, 2, 4, 3] 2는 1보다는 크고, 5와 6보다는 작기 때문에 그 사이에 넣어준다.
5. [1, 2, 5, 6, 4, 3] 마찬가지 과정으로 1,2와 5,6 사이에 넣어준다. 6.[1, 2, 4, 5, 6, 3] 마지막으로 1,2와 4,5,6 사이에 3을 넣고, 다음 숫자가 없으므로 종료한다.

이렇게 하면 [1, 2, 3, 4, 5, 6] 정렬이 완료된다.

def insertion_sort(arr):
    temp = 0
    for i in range(1, len(arr)):
        temp = arr[i]
        for j in range((i-1), -1, -1):
            if arr[j] > temp:
                arr[j+1] = arr[j]
            else:
                continue
            arr[j] = temp
    return arr


print(insertion_sort([5, 6, 1, 2, 4, 3]))

제로초님의 강의를 보고 실습해보았습니다.

버블 정렬

버블정렬은 단순하다. 처음부터 인접한 두 수를 비교해서 바꿔주면 된다. 예시로 [5, 1, 7, 4] 같은 배열이 있으면,

1. 1과 5를 비교해서 크니 바꿔준다. [1, 5, 7, 4]
2. 5는 7보다 작으니 둔다. [1, 5, 7, 4]
3. 7이 4보다 크니 바꿔준다. [1, 5, 4, 7]
4. 1은 5보다 작으니 둔다. [1, 5, 4, 7]
5. 5와 4를 비교해서 5가 크니 바꿔준다. [1, 4, 5, 7]

이런 식이다. 계속 처음부터 돌아가 두 수를 비교해야 하니 비효율 적이고 O(n^2)에 속할 정도로 안좋다. 하지만, 이런 정렬도 있음을 알기 위해 해보자.

파이썬 예시

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(1, len(arr)-i):
            if arr[j-1] >= arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr


print(bubble_sort([5, 1, 7, 4, 6, 3, 2, 8]))

두번째 반복문에 -i 를 넣어준 이유는 맨 마지막은 최종적으로 확정된 숫자기 때문에, 굳이 안돌리기 위해서 추가한 것이다.

느낀점

비효율적인 정렬이라지만, 이해하기는 가장 좋은 정렬인거 같고 설명대로 교육용으로 입문하긴 좋은거 같다.

참고사이트: git 문서 제로초님

개발자로 도전하면서 알아야 할게 정말 많아지고 있는데, 그중에서 중요하다고 생각하는 것중 하나가 바로 이 git이다. git을 사용하기 이전에 필자는 하나의 파일, A를 작성해둔다음, 만약 다르게 고쳐나가보고 싶으면은 A를 복사해서 A-1, A-2이런식으로 저장해서 사용했었다. 그러다 결국 어디를 수정했는지 기억도 못하고 중복되어버리는 경우가 발생하였는데, git을 사용하면서 복사할 필요 없이 한 파일을 통해 사용할 수 있게 되었다. 또한 친구와 같이 협업하는게 있는데, github같은 원격 저장소를 활용해서 서로 한 디렉토리로 관리할 수 있기에 편리함을 느꼈다. 개발자를 도전하는 사람이면 이 git은 꼭 알아둘 필요가 있을 거 같다.

Git이란

git은 버전 관리 시스템(VSC, Version Control System) 중 하나이다. 말 그대로 파일의 버전을 관리해주는 것이다. 위에서 기술했듯이, A라는 파일을 만들어서 이 파일의 변경점을 스냅샷 같은 형태로 관리하고 변경점을 관리하는 것이다. 그리고 이 관리되는 파일들은 원격지(Github)에 저장하거나 또는 로컬 컴퓨터에 저장하여서 각자 관리할 수 있도록 해준다.

Git 저장소 생성(init)

자신이 관리할 디렉토리에 들어가서 다음과 같은 명령어를 입력해주면, 이 디렉토리의 git이 시작된다.

git init

아래처럼 나타나고 git 관리가 개시됨을 볼 수 있다. 필자의 경우 zsh와 oh-my-zsh의 agnoster 테마를 사용하면 아래처럼 master가 표시됨을 볼 수 있다.

파일 관리해보기

파일을 한 번 관리해보도록 해보자. 간단하게 두 개의 파일을 만들어서 해보겠다.

touch git.html
touch git.css

파일을 생성하면 master의 배경색이 노랗게 바뀌는데(테마마다 차이 있음), untracked된 파일이 생성되면 바뀐다.

이후 git stauts 명령어를 이용해서 파일들의 상태를 확인해 볼 수 있다. 위 파일들을 git을 통해 관리를 할거면 commit을 해줘야 하는데 그 전에 git add 명령어를 이용해서 staged 상태로 바꾸어 줘야한다.

다음의 명령어를 통해 파일들을 staged 상태로 올려보자. add를 하면 master 옆에 + 표시가 나타난다.

git add 파일명

마지막으로 commit 명령어를 통해 파일들을 관리해준다.

원격저장소(Github) 사용

commit 수정

branch 관리

에듀캐스트 장고&리액트 강의를 듣고 정리하는 글이다.

댓글 쓰기 화면 및 API 구현

yarn add moment