기술 면접 준비(2)

작성일 | In

코딩 인터뷰 정복하기 2강

BIg O Notation

알고리즘의 퍼포먼스 이야기 할 때 상당히 좋다. 2019-03-06 7 53 10

O(1)

인자로 하나의 배열을 받았다면, 하나의 인덱스에만 접근하기 떄문에 order 1이 된다. stack 에 push 하거나 pop 할 때, 혹은 hash table에 접근할 때.

상수는 항상 무시된다

O(log n)

binary search tree에서 삽입 과정은 order logN이므로 총 8개이므로 log8 = 3이다.

O(n)

order N의 예제. 인자로 하나의 배열을 받았다고 생각하고, 우리는 그 배열의 모든 item을 print 한다고 보자. 따라서 for를 한번 돌아야 한다. 아이템의 갯수 만큼 access를 하므로 order(n)이라고 할 수 있다.

링크드 리스트의 순회나, 트리를 순회하는 것도 order(n)이다.

O(nlogn)

-> Quick Sort, Merge Sort, Heap Sort가 O(nlog n)에 해당한다.

여기서는 merge Sort의 예제를 확인해보자.

image

나누는 과정 -> O(logn) 마지막에 다 나눈 뒤 각각의 아이템 비교 -> O(n) 따라서 nlog n

O(n^2)

이중 배열, insertion Sort, Bubble Sort, Selection Sort 들이 해당된다.

코딩 인터뷰 정복하기 (3강)

Bubble Sort

정렬을 위한 교환 작업이 마치 거품처럼 보인다고 하여 bubble sort

performance : O(n²), space complexity: O(1)

bubbleSort.py

import unittest

def bubblesort(alist):
    for i in range(len(alist)-1):
        for j in range(len(alist)-1):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
    return alist


class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([6, 5, 4, 3, 2, 1]))

Q) inmport unittest unitest는 뭐하는 걸까?

파이썬 표준 라이브러리 중 유명한 테스트 모듈. testCase를 만들려면, unitest.TestCase를 상속받는 하위 클래스를 만들어야 한다.

import unittest

def fun(x):
    return x + 1

class MyTest(unittest.TestCase):
    def test(self):
        self.assertEqual(fun(3), 4)

-> 단위 테스트.

인접한 두 개의 자료를 비교해서 차순에 맞게 교환하는 작업을 정렬이 완료될 떄 까지 해주는 작업이 버블소트다.

자료수의 1개 뺀 만큼 looping을 한다.

6531을 정렬한다면 -> 5631 -> 5361-> 5316 : 첫 루프 끝 5316을 정렬 -> 3516 -> 3156 : 두 번째 루프 끝 3156을 정렬 -> 1356 : 끝

자료수 -1만큼 싸이클을 했다.

지난 시간 복습 체크

체크리스트

Q) class가 무엇이냐? -> class란 object의 템플릿이다.

Q) object란? -> 클래스의 인스턴스이다.

Q) Encapsulation이란 ? -> 캡슐화. 클래스의 보안 제공.

Q) Inheritance ? -> 상속, 부모의 메소드와 멤버 사용 가능

Q) Polymorphism ? -> 다형성, overloading과 overriding으로 표현 overloading : 하나의 클래스 안에서 같은 이름의 함수인데 서로 다르게 행동이 가능한 것. overriding : 서로 다른 클래스에서 같은 이름의 함수 사용 가능한 것.

Q) Abstraction ? -> 가상클래스를 부모로 갖고 있는 자식 클래스는 가상 함수를 그 안에서 무조건 구현해야 한다.

참고자료

허민석님 깃헙 블로그 https://github.com/minsuk-heo/problemsolving

단위테스트 관련 참고자료 https://wikidocs.net/16107

0%