이제 면접을 보러 다니면서 받은 질문들을 정리하고 내가 몰랐던 부분, 대답이 미흡했던 부분 등을 더 공부해서 보완할 생각이다. 다음 면접은 더 잘볼 수 있길 바라는 마음으로 작성한다.. :)

React, Redux

  • 테스트를 고려해서 코드를 짠 경험이 있는지

  • MobX랑 리덕스 차이

  • 리액트 훅에 대해 설명해보시오

  • 리액트에서 arrow function을 사용하면 일반 함수를 쓰는 것과 어떤 차이가 있는지

Java

  • 제네릭(Generic)에 대해 설명해보시오

HTML, CSS

  • Semantic HTML에 대해 설명해보시오

  • CSS를 사용해 수평정렬을 할 때 주로 사용하는 방법

JavaScript

  • 불변 객체를 만드는 방법으로 무엇을 사용하는가

  • 자바스크립트에서 비동기를 설명해보시오

  • 프로미스와 어싱크 어웨이트의 차이점을 설명해보시오

그 외

  • JWT 토큰

    • 왜 사용했는지

    • 토큰과 쿠키/세션 차이

    • JWT 토큰을 열어본 적 있는지

  • RESTful API에 대해 설명해보라

  • 중요한 API key는 어떻게 보관할 것인지

  • 왜 JSP와 스프링으로 프로젝트를 만들었는지

  • 스프링, 리액트, 장고를 써봤다고 했는데 그 3개의 차이점을 설명해보라

  • 장고를 왜 배웠는지, 장고의 특징이 뭐라고 생각하는지

  • 익스프레스를 어디서 배웠고 설계를 어떻게 했는지

  • 새로운 기술에 대한 지식 업데이트는 어디서 하는가

  • (면접 본 회사의 서비스가)이러이러한데, 이것을 본인이 구현하려면 어떻게 하겠는가

  • 도커 사용 경험

  • 파이어베이스 디비와 오라클 디비를 쓸 때 어떤 차이를 느꼈는지

Rotation point 찾기 문제

문제

a부터 z 순으로 적혀진 사전을 읽다가 모르는 단어가 나오면 단어장에 기입하는 작업을 하려고 한다. 단, 사전의 어느 중간부터 펴서 이 작업을 시작한다. 그래서 뒤로 가면서 이 작업을 수행하다가 사전의 끝에 도달하면 사전의 처음부터 시작해서 처음에 폈던 페이지 전까지 이 작업을 한다.

이 모르는 단어는 배열에 순서대로 저장하여, 예시를 들면 다음과 같은 형태가 된다.

['ptolemaic','retrograde', 'supplant', 'xenoepist', 'asymtote', 'babka']

알파벳 오름차순으로 진행되다가 사전의 끝까지 찾고 나면 다시 앞에서부터 시작하기 때문에 어느 순간 내림차순이 됐다가, 그 다음 다시 오름차순이다. 위 예시에서는 asymotote 라는 단어가 그 포인트이며, 이렇게 어느 순간 내림차순이 됐다가 다시 오름차순으로 시작하는 이 포인트를 Rotation point라고 하자. 이 Rotation point를 찾는 알고리즘을 구현하라.

 

힌트

Binary Search

 

문제의 포인트

Rotation point가 특정 원소의 왼쪽에 있을지, 오른쪽에 있을지를 어떻게 알 수 있는가. 전형적인 바이너리 서치에서 특정 숫자가 어디에 있는지를 찾을 때에는 중간 인덱스의 원소와 비교한 다음 왼쪽인지 오른쪽인지 범위를 좁힌다. 여기에서는 무엇과 비교를 해야 Rotation Point가 왼쪽인지 오른쪽인지 알 수 있을까?

 

풀이

def find_rotation_point(words):
    first_word = words[0] 
    start = 0
    end = len(words)-1
    
    while start <= end:
        mid = (start + end) // 2
        # Rotation point인지 
        if words[mid] - words[mid-1] < 0:
            return mid
        # 로테이션 포인트가 오른쪽일 때
        if words[mid] > first_word:
            start = mid+1
        # 로테이션 포인트가 왼쪽일 때
        else:
            end = mid-1      
  • 코드 구현할 때 내가 한 실수

    1. 처음에 mid = (start + end) / 2 라고 썼다. 그냥 나누기 부호를 써서 mid가 float형이 되어버리는 바람에 에러가 났다. 기초적인 부분이지만 조심하자.

    2. while문을 처음에 작성할 때 start < end 라고 써서 아무 것도 리턴되지 않는 경우 발생. 그러니까 start = end인 경우를 간과하고 탈출 조건을 잘못 작성했다. 코드상으로는 매우 작은 차이처럼 보이지만 루프 탈출문은 중요하므로 주의하기.

       

  • 코드 구현하기 전에 틀린 부분

    처음에 힌트를 보지 않고 문제를 풀었을 때는 O(n)이라고 풀었다. 일단 정렬됐긴 한데, 일부만 정렬되어 있으니까 바이너리 서치를 쓰지 못할 거라고 패스했고(정말 전형적인 케이스만 생각한...), 그 다음에 생각난 것은 Rotation Point는 배열 원소 중 최소값일테니까, 선택 정렬에서 사용하는 방식으로 최소값을 찾으면 되겠다고 생각했다. 단 한번만 찾으면 되니까 O(n)이겠다 생각했는데, 정답은 O(logN)이었다.

'Algorithm + Data Structure' 카테고리의 다른 글

Rotation point 찾기 문제(ft. Binary Search)  (0) 2019.12.03
퀵 정렬(Quick sort)  (0) 2019.12.02
선택 정렬(Selection Sort)  (0) 2019.11.30
버블 정렬(Bubble Sort)  (0) 2019.11.30
배열과 링크드 리스트  (0) 2019.11.18
[파이썬] 야근지수 문제  (0) 2019.09.23

퀵 정렬(Quick sort)

컴퓨터 언어에는 대부분 배열을 정렬하는 내장 정렬 함수가 있는데, 대다수가 내부적으로는 퀵 정렬 방법을 택하고 있다. 그 만큼 퀵정렬이 빠르기 때문이다. 퀵 정렬은 최악의 경우에는 삽입정렬이나 선택정렬 만큼 느리지만 대부분의 경우인 평균 시나리오에서는 훨씬 빠르다.

퀵 정렬은 분할(partition) 에 기반하고 있으며 이 분할이 재귀적으로 일어나는 과정을 통해 정렬된다.

 

분할

배열을 분할한다는 것은 피벗(기준 원소)를 기준으로, 피벗의 왼쪽에는 피벗보다 작은 수를 두고, 피벗의 오른쪽에는 피벗보다 큰 수를 두는 것을 말한다.

  1. [0,5,2,1,6,3] 이라는 배열을 가정하자.
  2. 피벗을 정렬되지 않은 배열의 가장 오른쪽 원소라고 정하자. 그러면 맨 오른쪽 위치의 3 이 피벗이 된다.
  3. 분할의 목적은 피벗인 3의 왼쪽에는 피벗보다 작은 수를, 오른쪽에는 피벗보다 큰 수를 두는 것이다. 이 분할이 한 번 끝나면 적어도 피벗인 3은 올바른 위치에 정렬하게 된다. 한 번 분할이 끝나고 3이 올바른 위치에 정렬하면, 양 옆의 원소들 또한 재귀적으로 분할을 진행하며 피벗을 올바른 위치에 정렬한다.
  4. 기저 조건(base case)*인 원소가 하나 남을 때까지 재귀적으로 진행되면 퀵 정렬이 완료된다.

* 기저 조건이란 중단 조건이라고도 한다. 재귀란 함수가 자기 자신을 반복적으로 호출하는 것을 의미하는데, 어느 순간에 중단하지 않는다면 무한 호출이 일어나면서 스택오버플로우가 일어난다. 그러므로 호출을 중단시키는 조건이 필요한데, 이를 기저 조건 또는 중단 조건이라고 한다.

재귀적으로 정렬을 하는 알고리즘에서는 정렬한 원소가 단 하나 남았을 때가 기저 조건이 된다. 원소가 하나일 때에는 정렬할 필요가 없기 때문이다. 또는 계승(factorial) 함수에서는 1! 이 기저 조건이 된다. 1!은 재귀함수를 호출할 필요도 없이 1인 것을 알 수 있기 때문이다.

 

배열이 한 번 분할하는 과정을 표현하자면 이렇다.

  • partition 함수는 전체 배열(arr), 정렬하고자 하는 범위의 시작 인덱스(start)와 끝 인덱스(end)를 패러미터로 받는다.
  • 그 다음 해당 범위에 대해서 분할을 진행한다. (=피벗을 올바른 위치에 위치하게 한다. 다만 피벗은 주어진 범위에서 가장 오른쪽에 위치한 원소로 한다)
  • 올바른 위치에 정렬하게 된 피벗의 위치를 리턴한다.

그 다음 분할은 피벗을 제외(피벗은 이미 정렬되었으므로)한 양 옆의 범위의 배열에 대해서 재귀적으로 진행하면 된다. 즉 배열의 원소가 총 7개이고 0~6까지의 인덱스를 갖고 있으며, 첫 분할 결과 올바르게 정렬한 피벗의 위치가 인덱스 3이라면, 인덱스 0~2의 범위에 대해 분할을 또 진행하고, 마찬가지로 인덱스 4~6의 범위에 대해 또 분할을 진행한다. 각 분할은 또 다시 새롭게 정렬된 피벗의 위치를 리턴할 것이고, 또 양 옆의 범위에 대해서 분할을 하고 …

def swap(arr, p1, p2):
    arr[p1], arr[p2] = arr[p2], arr[p1] 
# 배열의 맨 오른쪽 원소를 피벗으로 설정하는 경우의 분할
# start와 end는 분할을 진행할 범위를 나타냄. 시작 인덱스와 끝 인덱스.
# left와 right는 각각 왼쪽 포인터와 오른쪽 포인터의 위치
def partition(arr, start, end):
    left = start
    right = end-1 
    pivot_position = end
    pivot = arr[pivot_position]
  
    while True:
        # 왼쪽 포인터 이동
        # 왼쪽 포인터가 가리키는 값이 pivot과 같거나 클 경우 stop
        while arr[left] < pivot:
            left += 1

        # 오른쪽 포인터 이동
        # 오른쪽 포인터가 가리키는 값이 pivot과 같거나 작을 경우 stop
        while arr[right] > pivot:
            right -= 1

        # 왼쪽과 오른쪽 모두 포인터가 멈추었을 때
        # 왼쪽 포인터가 오른쪽 포인터보다 왼쪽에 위치한다면 둘을 교환
        if left < right:
            swap(arr, left, right)
        # 왼쪽 포인터가 오른쪽 포인터와 같은 위치에 있거나 더 오른쪽일 때 while문 탈출
        else:
            break
    
    # 왼쪽 포인터가 가리키는 원소와 피벗을 교환
    swap(arr, left, pivot_position)
    # 정렬된 피벗의 위치를 리턴
    new_pivot_position = left
    
    return new_pivot_position
def quick_sort(arr, start, end):
    # 정렬할 부분이 존재하는지 체크
    pi = 0
    if start < end:
        pi = partition(arr, start, end)
    else:
        return
    quick_sort(arr, 0, pi-1)
    quick_sort(arr, pi+1, end)

quick_sort 함수는 기저조건을 포함하고 있다. 원소가 단 하나이거나, 원소가 존재하지 않는다면 분할을 할 필요가 없다. 더 이상 정렬이 필요하지 않기 때문이다. 그래서 start < end이면 분할을 진행하고, start = end여서 원소가 단 하나인 경우나, start > end여서 원소가 존재하지 않는 경우에는 분할을 더 이상 진행하지 않고 탈출한다.

이 기저조건이 없으면 무한 호출이 일어나므로 매우 중요한 부분이다.

다만 나는 기저조건을 쓰고도 실수로 인해 계속 recursion error 가 났는데 마지막 줄에서 quick_sort(arr, pi+1, len(arr)-1)로 쓴 것이 원인이었다. 처음엔 얼핏 맞다고 생각했는데 전혀 아니다. 퀵소트를 처음 호출했을 때나 맞지, 그 다음 호출부터는 이렇게 쓰면 쪼개진 범위가 제대로 들어가지 않는다. 예를 들어 쪼개진 범위가 0~6 범위에서 피벗 위치가 4이면, 그 다음은 0~3, 5~6이 들어간다. 그 다음 0~3 범위에서 분할을 진행한 결과 피벗 위치가 2이면 0~1, 3~3 이렇게 다시 분할을 진행해야 하는데 len(arr)-1은 고정으로 6이라는 값을 가지니까 0~1, 3~6이 들어가 버린다. 3~3이면 더 이상 분할이 진행되지 않고 끝나야 하는데 3~6으로 잘못들어가니 계속 분할이 일어나서 결국 recursion error가 일어난다.

 

퀵 정렬의 효율성

  삽입 정렬(Insertion sort) 퀵 정렬(Quick sort)
최선 O(n) O(n*logn)
평균 O(n^{2}) O(n*logn)
최악 O(n^{2}) O(n^{2})

퀵 정렬에서 최악의 경우는, 분할 결과마다 피벗이 맨 끝에 위치하는 경우다. 원소가 총 N개일 때 분할을 하면 일어나는 최소 비교 횟수는 N번이다. 교환은 분할 한 번에 최소 1번, 최대 N/2번까지 일어난다. 비교와 교환을 합해도 빅오표기법으로 하면 O(n)이다. 피벗이 매번 맨 끝에 위치하면 총 비교하는 횟수만 합해도 N + (N-1) + (N-2) + … + 2 단계가 걸린다. 이를 합하면 약 N^{2}/2 인데 빅오표기에서는 상수항을 무시하므로 O(n^{2}) 이다.

반면 피벗이 맨 끝에 위치하지 않고 중간 쯤 위치한다면 비교 횟수가 훨씬 줄어들게 된다. 만약 피벗이 늘 배열의 중간 쯤에 위치한다면, 분할할 때 마다 절반씩 쪼개서 또 분할하는 형태가 반복될 것이다. 즉 전체 길이가 N일 때 logN만큼 쪼개지는데, 쪼갤 때마다 총 길이인 N에 대해 분할을 진행하므로 O(N*logN ) 이 긍정적인 시나리오일 때 퀵 정렬의 속도이다.

'Algorithm + Data Structure' 카테고리의 다른 글

Rotation point 찾기 문제(ft. Binary Search)  (0) 2019.12.03
퀵 정렬(Quick sort)  (0) 2019.12.02
선택 정렬(Selection Sort)  (0) 2019.11.30
버블 정렬(Bubble Sort)  (0) 2019.11.30
배열과 링크드 리스트  (0) 2019.11.18
[파이썬] 야근지수 문제  (0) 2019.09.23

파이썬에서 함수에 인자를 전달하는 방식 - Call by object reference

함수에 인자를 전달할 때 사용하는 방식은 크게 2가지다.

  1. Call by value
  2. Call by reference

그런데 파이썬은, call by object reference란다. (…?)

 

Call by Value

def print_val(val):
    val += 10
    print(val)
    
i = 2
print_val(i) # 12
print(i) # 2

파이썬이기 때문에 Call by value라고 하면 안 되겠지만, 어쨌든 결과는 유사하므로 call by value라고 가정하자. Call by value는 i가 print_val의 인자로 넘겨졌을 때 i가 담고 있는 값인 2가 복사되어 val에 할당된 것이다. 그러므로 함수 밖에서 i는 여전히 2이다.

 

Call by reference

def print_ref(ref):
    ref[0] = 0
    print(ref)
    
i = [1,2]
print_ref(i) # [0,2]
print(i) # [0,2]

위의 call by value 예시와 다르게, print_ref 함수를 호출한 뒤에는 i값이 실제로 바뀐다. 함수에 인자를 넘길 때 값을 복사하는 것이 아니라, 해당 변수가 참조하고 있는 주소를 넘겼기 때문에 함수 내부에서 변경되면 외부에서도 마찬가지로 변경된다.

 

Call by object reference

파이썬에서는 모든 것이 객체인데 immutable한 객체와 mutable한 객체가 있다.

  • Immutable: int, float, tuple, str ..
  • Mutable: dic, list, set ...

변경 불가능한 값, 즉 이뮤터블 오브젝트가 인자로 전달되면 마치 call by value처럼 작동하고, 변경 가능한 값인 뮤터블 오브젝트가 전달되면 call by reference로 작동한다.

처럼이라는 말을 사용한 것은, call by value의 경우 겉으로 보기에는 비슷해보이는데 실제로는 조금 다르게 작동하기 때문이다. 파이썬에서는 C처럼 변수가 있는 메모리에 값을 저장하는 형태가 아니라, 값을 가리키는 형태이다. 변수와 값(파이썬에서는 모든 값이 객체이니 이하 객체라고 하자)은 다른 것이다.

x = 3 라고 했을 때 x는 변수이고 3 은 객체이다. 파이썬에서는 x라는 변수가 객체 3 를 저장하고 있는 것이 아니라, 객체를 가리킨다. 파이썬에서 모든 객체는 단 하나의 인스턴스를 갖고 있는 싱글톤 패턴이어서, 3 의 유일한 인스턴스를 x가 가리키고 있는 것이다. 이 때 y=x 라고 한다면, y라는 또다른 변수도 3 의 인스턴스(즉 x가 가리키고 있는 것과 똑같은)를 가리키게 된다.

파이썬에는 reference count라는 개념이 있어서, x와 y과 똑같은 객체를 가리킨다면, 해당 객체의 reference count는 2가 된다.

그러면 파이썬에서는 모든 것이 객체고, 3 같은 int 값도 객체이기 때문에 call by reference처럼 작동하는 것이 맞는 것 같다. 즉 아래 예시를 예로 들면 2라는 객체의 주소가 넘어가고, 그 객체가 변경됨으로써 i가 가리키는 객체의 value도 변경되어야 할 것 같다. 하지만 실제로는 call by value처럼 작동하여 함수 외부에서는 i가 가리키는 값은 그대로이다.

def print_val(val):
    val += 10
    print(val)
    
i = 2
print_val(i) # 12
print(i) # 2

이 이유는 print_val이 호출될 때 val이라는 변수가 생성되면서 i와 똑같은 객체, 즉 2의 인스턴스를 가리키게 되는 건 맞지만 여기에 +=10 이라는 연산이 들어갔을 때 객체 2의 인스턴스가 변동되어 12가 되는 것이 아니고, 새로운 객체 12의 인스턴스가 생성되며 val이라는 변수는 그것을 가리키게 되기 때문이다. 여전히 i는 객체 2의 인스턴스를 가리키고 있다. 그러므로 마치 call by value처럼, 이뮤터블 오브젝트는 인자로 전달되어도 함수 바깥에서는 변하지 않는다.

선택 정렬(Selection sort)

  • 단순 정렬(Simple sort) 중 하나로, 속도는 느린 편(평균적으로 O(n^{2}), quadratic time)이지만 최악의 경우를 가정했을 때 버블소트보다 2배 가량 빠르다.

 

가정

  • 배열(Array) 정렬을 가정한다.
  • 정렬되지 않은 배열을 오름차순으로 정렬한다.
  • 배열의 길이는 n이다.

 

순서

  • index 0 원소를 temp라는 변수에 저장한다.
  • 그 다음 index 1부터 index n-1 까지 순회하면서 temp보다 작은 값이 있는지 비교 한다. 만약 비교 결과 temp보다 작은 값이 있으면 그 값을 temp에 재할당한다. 이렇게 한 번 패스 스루(정해진 범위의 배열을 한 번 훑는 것)를 끝내고 나면, temp에는 전체 배열 원소값 중 최소값이 저장되어 있을 것이다.
  • 이 최소값이 갖고 있던 index가 0 이 아니고 i라면, index 0과 index i의 원소를 교환하여 최소값이 배열의 맨 앞자리에 위치하도록 한다.
  • 그 다음부터는 index 1부터 위 과정을 반복한다. 그러면 index 1부터 index n-1 사이(정렬되지 않은 범위)에서의 최소값이 index 1에 위치한다.
  • 이 과정을 index 2, 3, 4… n-2가 될때까지 반복한다. *

 

구현 - 파이썬


def selection_sort(list):
    start_index = 0
    
    while not start_index == len(list)-1:
        temp = list[start_index]
        temp_index = start_index
        for i in range(start_index, len(list)):
            if temp > list[i]:
                temp = list[i]
                temp_index = i
        list[start_index], list[temp_index] = list[temp_index], list[start_index]
        start_index += 1
    
    return list

 

주의점

* 버블소트와 마찬가지로 셀렉션소트도 비교교환으로 이루어져 있다. 둘 다 오름차순으로 배열을 정렬하는데, 버블소트는 최대값을 배열 끝에서부터 하나씩 정렬하고, 셀렉션소트는 최소값을 배열 앞에서부터 하나씩 정렬한다. 다만 버블소트와 비교하자면 비교는 동일한 횟수만큼 일어나지만 교환 횟수가 셀렉션소트가 훨씬 적다. (최악의 경우를 가정할 때)

* Bubble Sort Selection Sort
비교 연산 n(n-1) / 2 n(n-1) / 2
교환 연산 n(n-1) / 2 n-1

빅오표기법으로는 같은 quadratic time으로 같은 분류에 해당하지만, 실제로는 셀렉션소트가 더 빠를 가능성이 높은 것이다. 평균적으로 약 2배 가량 빠르다고 한다. 즉 빅오표기법은 다른 분류 사이에서는 어느 것이 더 효율적인지 확실히 답해줄 수 있지만, 같은 분류 사이에서는 어떤 것이 더 효율적인지 말해주지 않는다.

'Algorithm + Data Structure' 카테고리의 다른 글

Rotation point 찾기 문제(ft. Binary Search)  (0) 2019.12.03
퀵 정렬(Quick sort)  (0) 2019.12.02
선택 정렬(Selection Sort)  (0) 2019.11.30
버블 정렬(Bubble Sort)  (0) 2019.11.30
배열과 링크드 리스트  (0) 2019.11.18
[파이썬] 야근지수 문제  (0) 2019.09.23

버블 정렬(Bubble sort)

  • 단순 정렬(Simple sort) 중 하나로, 속도는 느린 편(평균적으로 O(n^{2}), quadratic time)이지만 간단하게 구현할 수 있는 장점이 있다

     

가정

  • 버블소트는 배열(Array) 정렬을 가정한다.
  • 정렬되지 않은 배열을 오름차순으로 정렬한다.
  • 배열의 길이는 n이다.

 

순서

  • 배열의 가장 처음부터(index 0부터) 원소 2개씩 비교 한다.

  • 즉 arr[0], arr[1]을 비교해서 arr[0] > arr[1] 이면 순서를 바꾼다. 아니면 그냥 Pass한다.

  • arr[1]과 arr[2]에도 똑같이 한다.

  • arr[n-2]과 arr[n-1]까지 똑같이 한다. 즉 총 n-1번, 바로 뒤의 원소와 대소비교를 해서 교환을 하거나 하지 않는다.

  • 배열의 앞에서부터 끝까지 이렇게 한 번 훑으며 교환을 하는 과정을 패스스루(pass through) 라고 한다.

  • 패스스루 과정에서 교환이 1번이라도 일어났다면, 다시 index 0부터 패스스루를 진행한다. *

  • 패스스루 중 단 한번도 교환이 일어나지 않는다는 것은 모든 원소가 정렬되어 있다는 의미이므로, 이 때 loop를 종료한다.

  • 또는 패스스루가 일어날 수 있는 최대 횟수인 n-1번이 되면 loop를 종료한다.

     

* 여기서 반복해서 패스스루를 진행할 때마다 직전 패스스루의 버블은 제외하고 진행한다. 정렬되지 않은 값 중 가장 큰 값을 버블이라고 하는데, 한 번의 패스스루가 될 때마다 반드시 가장 큰 값은 맨 뒤에 위치하는 것이 보장된다. 즉 가장 처음 패스스루를 할 때 n-1번의 원소 비교를 거쳐 가장 큰 값이 배열의 맨 뒤에 위치하게 된다. 그 다음 패스스루를 진행할 때에는 이 버블을 제외하고 n-2번의 원소 비교를 하면 되고, 그 다음 패스스루에는 n-3번의 원소 비교가 필요하게 된다. 그 다음, 그 다음으로 가다보면 마지막에는 1번의 원소 비교가 필요하다. 그러니까 (n-1) + (n-2) + (n-3) + … + 2 + 1, 총 비교 횟수는 ​\frac{n-1}{2} * (n) 이 된다. 그리고 최악의 경우 비교할 때마다 교환이 일어나므로, 비교 횟수 * 2를 하면 비교와 교환을 합한 최대 연산은 ​n(n-1) 이다. 빅오표기법은 상수항을 무시하므로 ​O(n^{2}) 이 된다.

 

구현 - 파이썬

def bubble_sort(list):
  # 패스스루할 구간을 정해주는 변수(decrement할 변수)
  unsorted_until_index = len(list)-1
  # 정렬 여부를 표시. 패스스루할 동안 교환이 일어났으면 False, 일어나지 않았으면 정렬된 것이므로 True
  sorted = False 
  
  # 탈출조건
  # 패스스루할 동안 교환이 한 번도 일어나지 않는 경우
  # 또는 총 len(list)-1 번의 패스스루가 진행된 경우
  while not sorted:
    sorted = True 
    # 패스스루 시작
    for i in range(unsorted_until_index):
      # 대소비교 후 교환
      if list[i] > list[i+1]:
        # 교환이 일어났기 때문에 아직 loop 종료하면 안 됨 
        sorted = False 
        list[i], list[i+1] = list[i+1], list[i]
        unsorted_until_index -= 1 

  return list

 

주의점

버블소트는 셀렉션 소트(선택정렬)랑 평균적으로는 빅오표기법에 의한 속도가 같지만, 실제로 어떤 정렬이 더 좋을지는 세부적인 전제들을 따져봐야 한다.

예를 들어 버블소트와 선택정렬에는 기본적으로 원소 간 비교와 교환이 포함되는데, 이 중 교환에 시간이 오래 걸린다면 어떤 정렬 알고리즘이 더 효율적일 가능성이 높을까? 이런 경우에는 선택정렬을 택하는 것이 더 안전할 것이다.

왜냐하면 선택정렬은 길이가 n인 배열 정렬에서 n-1번을 탐색하고, 최대 n-1번의 교환을 한다. 즉 배열을 전체 탐색(패스 스루)할 때마다 최대 1번의 교환이 일어나므로 총 n-1번의 교환을 넘지 않는다.

반면 버블소트는 길이가 n인 배열에서 최대 \frac{n-1}{2} * (n) 만큼의 교환이 일어날 수 있다. 매번 패스 스루할 때마다, 비교하는 모든 원소 간 교환이 일어난다는 최악의 경우(내림차순으로 정렬된 경우)를 가정할 때 그렇다.

'Algorithm + Data Structure' 카테고리의 다른 글

퀵 정렬(Quick sort)  (0) 2019.12.02
선택 정렬(Selection Sort)  (0) 2019.11.30
버블 정렬(Bubble Sort)  (0) 2019.11.30
배열과 링크드 리스트  (0) 2019.11.18
[파이썬] 야근지수 문제  (0) 2019.09.23
[JS] 가장 먼 노드(그래프 탐색)  (0) 2019.07.02

특정한 sub folder 제외하고 모두 복사하기

은근 종종 써야 하는데 쓸 때마다 찾아보기 귀찮은 명령(eg. 어디에 소스코드 제출해야 할 때 노드 모듈 빼기)

$ rsync -av [project_name]/ to [copy_project_name] --exclude=node_modules/ # project_name 하위 내용을 copy_project_name 디렉토리로 노드모듈 빼고 전부 복사하기

rsync가 원래는 동기화용 이라고 하는데 스택오버플로우에서 검색한 결과 복사용으로도 사용되는 듯 하다. 여기서 / 를 주의해야 하는데 [project_name] 뒤에 / 를 붙이지 않으면 [copy_project_name] 내에 [project_name] 디렉토리 자체가 통째로 포함돼 버린다.

 

컴퓨터 메모리에 뭔가를 저장해야 할 때

  1. 컴퓨터에게 저장 공간을 요청한다.
  2. 컴퓨터는 뭔가를 저장할 수 있는 주소를 알려준다.

이 때 여러 개의 원소를 저장해야 한다면 여러 개의 주소가 필요할 텐데, 선형적으로 저장한다고 가정하면 배열이나 리스트 중 하나로 저장하게 된다. (선형적이지 않은 저장 방법으로는 트리나 그래프 등이 있다)

 

배열(Array)

만약 10개의 원소를 배열로 저장해야 한다면, 메모리에 연달아 있는 10개 공간을 할당한다.

배열의 장점

인덱스가 주어지므로 빠르게 접근할 수 있다.

배열의 단점

처음에 3개의 공간만 요청했다가 공간이 1개 더 필요하게 되면, 이 때 공간 4개를 재요청해야 한다. 즉 사전에 할당한 공간 내에서만 저장이 가능하고 이 공간 범위를 벗어날 경우 재요청이 필요하다.

이를 해결하기 위해서 애초에 공간을 넉넉하게 요청할 수도 있는데, 만약 추가할 일이 생기지 않으면 메모리 낭비가 생기는 셈이고 추가하더라도 그 넉넉한 범위를 벗어날 가능성은 언제나 있다.

또한 삽입과 삭제가 느리다. 원소 한 개를 삽입하더라도, 그 삽입 위치 뒤의 원소들은 모두 하나씩 이동해야 한다. 삭제 또한 마찬가지이다.

 

연결 리스트(Linked List)

여러가지 메모리 주소들이 하나의 목록으로 연결되어 있다. 첫 번째 주소로 가면 두 번째 주소에 대한 정보가 있고, 두 번째 주소로 가면 세 번째 주소에 대한 정보가 있는 식이다. 그러므로 배열처럼 연달아 메모리를 할당하지 않고, 빈 곳 아무데나 저장한 다음 그 주소를 바로 앞의 원소에 저장해놓기만 하면 된다.

리스트의 장점

삽입과 삭제가 빠르다. 리스트는 이전 원소가 무엇을 가리키는지 바꾸기만 하면 된다.

리스트의 단점

읽기가 느리다. 배열과 달리 순차 접근(sequential access)을 하여 첫 번째 원소부터 읽어야 하기 때문에 n번째 원소를 읽으려면 연산이 n번 필요하다.

 

빅오 표기법으로 나타내기

  • 배열

    • 읽기: O(1)
    • 삽입: O(n)
    • 삭제: O(n)
  • 링크드 리스트

    • 읽기: O(n)
    • 삽입: O(1)
    • 삭제: O(1)

단 삽입과 삭제는 가장 마지막 원소 또는 가장 첫 번째 원소를 가정한 것이다. 즉 바로 접근이 가능할 때에만 링크드 리스트에서 삽입과 삭제가 O(1)이 걸린다는 소리이다.

 

'Algorithm + Data Structure' 카테고리의 다른 글

선택 정렬(Selection Sort)  (0) 2019.11.30
버블 정렬(Bubble Sort)  (0) 2019.11.30
배열과 링크드 리스트  (0) 2019.11.18
[파이썬] 야근지수 문제  (0) 2019.09.23
[JS] 가장 먼 노드(그래프 탐색)  (0) 2019.07.02
[Java] LinkedList  (0) 2019.05.31

+ Recent posts