Ch5. 비트 조작

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 산술 우측 시프트와 논리 우측 시프트

  • 산술 우측 시프트(arithmetic right shift)

    • 산술 우측 시프트는 기본적으로 2를 나눈 결과와 같다.

    • 이는 비트를 오른쪽으로 옮기긴 하지만 부호비트는 바꾸지 않는다.

    • 

  • 논리 우측 시프트(logical right shift)

    • 논리 우측 시프트는 비트를 옆으로 옮긴 뒤 최상위 비트(most significant bit)에 0을 넣는다.

    • 

• 비트 조작하기

  • 비트값 확인

    • i 번째 비트의 값이 0인지 1인지 확인하고자 한다.

    • 이를 위해 1을 i만큼 시프트해서 00010000 과 같은 값을 만든다.

    • 이를 AND 연산을 통해 i 번째 비트를 제외한 나머지 비트를 모두 삭제한 뒤, 이 값을 0 과 비교한다.

    • 만약 이 값이 0이 아니라면 i 번째 비트는 1일 것이며, 0이라면 i 번쨰 비트는 0이어야 한다.

      1 2	def getBit(num, i): return ((num & (1<<i)) != 0)

    • 위의 함수를 통해 i 번째 비트의 값을 확인할 수 있다.

  • 비트값 채워넣기

    • i 번째 비트를 1로 바꾸려고 한다.

    • 이를 위해 1을 i만큼 시프트해서 00010000 과 같은 값을 만든다.

    • 이를 OR 연산을 통해 num의 i번째 값만을 바꿔줄 수 있다.

      1 2	def setBit(num, i): return num | (1 << i)

    • 위의 함수를 통해 i 번쨰 비트를 1로 바꿔줄 수 있다.

  • 비트값 삭제하기

    • i 번쨰 비트값만 삭제하고자 한다.

    • 이를 위해 11101111 과 같은 마스크를 만들어야 한다.

    • 1 을 num 의 길이보다 1 크게 쉬프트한 뒤 1을 빼서 11111111 과 같은 값을 만든다.

    • 그리고 1을 i 만큼 쉬프트해서 00010000 과 같은 값을 만든다.

    • 만든 두 개의 값을 XOR 연산을 통해 11101111 과 같은 마스크를 만든다.

    • 마스크와 num 을 AND 연산하면 i 번쨰 비트만 삭제된다.

      1 2 3 4 5 6

      def clearBit(num, i): length = len(bin(num))-2 temp1 = (1<<(length+1)) -1 ## 11111111 만들기 temp2 = 1<<i ## 00010000 만들기 mask = temp1 ^ temp2 ## 두개를 합쳐서 마스크 만들기 return num & mask

    • 위의 함수를 통해 i 번쨰 비트만 삭제할 수 있다.

Ch5. 연습문제 코드

CtCI_Ch5_Python

Ch4-1. 그래프

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 그래프

  • 앞서 이야기한 트리는 그래프의 한 종류이다. 하지만 모든 그래프가 트리는 아니다.

  • 트리는 사이클이 없는 하나의 연결 그래프라고 말할 수 있다.

  • 그래프는 노드와 노드를 연결하는 간선을 하나로 모아 놓은 것이다.

  • 그래프에는 방향성이 있을 수도 있고 없을 수도 있다. 방향성이 있는 간선은 일방통행, 방향성이 없는 간선은 양방향 통행이라고 생각하면 된다.

  • 모든 노드 쌍에 대해 경로가 존재하는 그래프를 “연결 그래프”라고 한다.

  • 그래프에는 사이클이 있을 수도 없을 수도 있다. 사이클이 없는 그래프를 “비순환 그래프(acyclic graph)”라고 한다.

• 그래프 탐색

  • 깊이 우선 탐색(depth-first search)

    • 깊이 우선 탐색(DFS)은 루트 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법이다.

    • 즉, a 노드를 방문한 뒤 a 와 이웃한 노드 b를 방문했다면, a 와 인접한 다른 노드를 방문하기 이전에 b 의 이웃 노드들을 전부 방문해야 한다.

    • 전위 순회를 포함한 트리 순회는 모두 DFS의 한 종류이다. DFS는 그래프에서 모든 노드를 방문하고자 할 때 더 선호되는 편이다.

    • 

  • 너비 우선 탐색(breadth-first search)

    • 너비 우선 탐색(BFS)은 a 노드에서 시작했을 때, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

    • 즉, BFS는 a 에서 시작해서 거리에 따라 단계별로 탐색한다고 봉 수 있다.

    • BFS는 재귀적으로 동작하지 않는다. BFS는 큐를 이용해서 방문할 노드를 저장하고 이를 탐색한다.

    • 

  • 양방향 탐색(bidirectional search)

    • 양방향 탐색은 출발지와 도착지 사이의 최단 경로를 찾을 때 사용된다.

    • 출발지와 도착지 두 노드에서 동시에 너비 우선 탐색을 수행한 뒤, 두 탐색 지점이 충돌하는 경우에 경로를 찾는 방식이다.

    • 노드 s에서 노드 t까지 너비 우선 탐색으로 4단계를 거쳐야하는 경우를 생각해보자.

    • s와 t 두 지점에서 동시에 탐색을 시작하면 각 노드의 2단계 이후에 탐색 지점이 충돌한다.

    • 이를 수행시간으로 비교해보자.

    • 전통적인 너비 우선 탐색을 통해 k개의 노드를 탐색하는 과정을 d번 반복하면 O(k^d) 개의 노드를 탐색해야 한다.

    • 양방향 탐색을 이용한다면 두 노드의 중간 지점 정도인 d/2 반복에서 충돌할 것이다.

    • 따라서 s와 t 각각에서 방문하게 될 노드의 수는 대략 k^d/2 개가 될 것이고, 전체 노드는 2*k^d/2, O(k^d/2) 의 수행시간이 된다.

    • k^d/2 * k^d/2 = k^d 인 것을 생각해 보면, 양방향 탐색은 일반적인 너비 우선 탐색보다 k^d/2 만큼 더 빠르다.

• 참고

  • https://www.codesdope.com/course/algorithms-bfs/

  • https://www.codesdope.com/course/algorithms-dfs/

Ch4-1. 트리

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 이진 트리

  • 이진 트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리를 말한다.

  • 자식 노드가 세개인 경우는 삼진 트리라고 부른다.

  • 아래와 같은 트리는 최대 자식 노드가 두개이므로 이진 트리이다.

  • 

• 이진 탐색 트리

  • 이진 탐색 트리는 모든 노드가 다음과 같은 순서를 따르는 이진 트리를 뜻한다.

  • “모든 왼쪽 자식 노드 <= n < 모든 오른쪽 자식 노드” 조건이 모든 노드 n에 대해서 반드시 참인 경우 이진 탐색 트리이다.

  • 조건은 바로 아래 자식 노드뿐 아니라 모든 자식 노드에 대해서 참이어야 한다.

  • 

  • 위와 같은 경우, 모든 노드가 조건을 만족하므로 이진 탐색 트리이다.

  • 예를 들어, 13은 8과 10보다는 크지만 14보다는 작으며 4는 8과 6보다는 작지만 3보다는 크다.

• 트리의 종류

  • 완전 이진 트리(complete binary tree)

    • 완전 이진 트리란 트리의 마지막 단계(Level)을 제외한 모든 높이에서 노드가 꽉 차 있어야 한다.

    • 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

    • 

    • 위의 그림은 완전 이진 트리가 맞지만 만약 L 노드가 F 노드의 right child 였다면 완전 이진 트리가 아니다.

  • 전 이진 트리(full binary tree)

    • 전 이진 트리는 모든 노드가 자식이 없거나 정확히 두 개 있는 경우이다.

    • 다시 말해, 자식이 하나만 있는 노드가 존재해서는 안된다.

    • 

  • 포화 이진 트리(perfect binary tree)

    • 포화 이진 트리는 완전 이진 트리이면서 전 이진 트리인 경우이다.

    • 모든 말단 노드가 같은 높이에 있고, 말단 노드의 개수가 최대이다.

    • 

    • 포화 이진 트리의 노드 개수는 2^k+1-1 개 이다. (k는 트리의 height)

• 이진 트리 순회

  • 중위 순회(in-order traversal)

    • 중위 순회는 왼쪽 가지, 현재 노드, 오른쪽 가지 순서로 노드를 방문하고 출력하는 방법이다.

    • 이진 탐색 트리를 중위 순회한다면 오름차순으로 방문하게 된다.

  • 전위 순회(pre-order traversal)

    • 전위 순회는 자식 노드보다 현재 노드를 먼저 방문하는 방법이다.

    • 전위 순회에서는 루트 노드를 가장 먼저 방문하게 된다.

  • 후위 순회(post-order traversal)

    • 후위 순회는 모든 자식 노드를 먼저 방문하고 마지막에 현재 노드를 방문하는 방법이다.

    • 후위 순회에서는 루트 노드를 가장 마지막에 방문하게 된다.

• 이진 힙

  • 힙은 최댓값 및 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진 트리이다.

  • 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 “최소 힙” 이라 하며, 그 반대는 “최대 힙”이라 한다.

  • 키값의 관계는 부모와 자식 노드 사이의 관계만 성립하며, 형제 사이에 대소관계는 성립하지 않는다.

  • 삽입 연산

    • 최소힙에 원소를 삽입할 때, 가장 밑바닥 오른쪽 위치로 삽입한다.(완전 트리의 속성에 위배되지 않기 위해서)

    • 그 다음 삽입된 원소가 알맞은 자리를 찾을 때까지 부모 노드와 교환해 나간다. 이와 같은 방식으로 최소 원소를 위쪽으로 올린다.

    • 이 연산은 힙에 있는 원소의 개수를 n개라 할 때, O(long n) 시간이 걸린다.

  • 최소 원소 뽑아내기

    • 최소힙에서 최소 원소는 언제나 가장 위에 위치한다.

    • 최소 원소를 제거한 후, 힙에 있는 가장 마지막 원소와 교환한다.

    • 그 다음 최소힙의 성질을 만족하도록 해당 노드를 자식 노드와 교환한다.

    • 자식 노드와 교환할 때 왼쪽과 오른쪽 자식 중 누구와 교환해야 할까?

      • 최소힙의 속성을 유지하기 위해 더 작은 원소와 교환해 나간다.

    • 

• 트라이(접두사 트리)

  • 트라이는 n-차 트리의 변형으로 각 노드에 문자를 저장하는 자료구조이다.

  • 트리를 아래쪽으로 순회하면 단어 하나가 나오게 된다.

  • 널 노드(null node) 혹은 ‘ * 노드 ‘ 는 종종 단어의 끝을 나타내주기 위해 사용된다.

  • 트라이에서 각 노드는 1개에서 <알파벳_사이즈 + 1> 개까지 자식을 갖고 있을 수 있다.

  • 트라이를 통해 유효한 단어의 접두사를 빠르게 확인할 수 있으며 이는 길이가 K인 문자열이 주어졌을 때 O(K) 시간이 소요된다.

• 참고

  • https://algorithms.tutorialhorizon.com/binary-min-max-heap/

  • https://www.geeksforgeeks.org/

Ch3. 스택과 큐

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 스택 구현하기

  • 스택은 데이터를 쌓아올리는 자료구조이다. 스택은 LIFO(Last-In-First-Out)에 따라 자료를 배열한다.

  • 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이 된다.

  • 스택에는 다음과 같은 연산이 존재한다.

    • pop(): 스택에서 가장 위에 있는 항목을 제거한다.

    • push(item): item을 스택의 가장 위에 추가한다.

    • peek(): 스택의 가장 위에 있는 항목을 반환한다.

    • isEmpty(): 스택이 비어있을 때에 True를 반환한다.

  • 파이썬을 통해 스택을 아래와 같이 구현할 수 있다.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

    class Stack(): def __init__(self): self.stack = [] def __len__(self): return len(self.stack) def isempty(self): if self.stack: return False else: return True def push(self, num): self.stack.append(num) def pop(self): if self.stack: return self.stack.pop() else: raise Exception("stack is empty") def peek(self): if self.stack: return self.stack[-1] else: raise Exception("stack is empty")

• 큐 구현하기

  • 큐는 FIFO(First-In-First-Out)에 따라 자료를 배열한다.

  • 즉, 큐에 저장되는 항목들은 추가되는 순서대로 제거된다.

  • 큐에는 다음과 같은 연산이 존재한다.

    • add(item): item을 리스트의 끝부분에 추가한다.

    • remove(item): 리스트의 첫 번쨰 항목을 제거한다.

    • peek(): 큐에서 가장 위에 있는 항목을 반환한다.

    • isEmpty(): 큐가 비어있을 때 True를 반환한다.

  • 파이썬을 통해 아래와 같이 큐를 구현할 수 있다.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

    class Queue(): def __init__(self): self.queue = [] def push(self, num): self.queue.append(num) def pop(self): if self.queue: item = self.queue[0] self.queue = self.queue[1:] return item else: raise Exception("Queue is empty") def peek(self): if self.queue: return self.queue[0] else: raise Exception("Queue is empty") def isEmpty(self): if not self.queue: return True else: return False

Ch3. 연습문제 코드

CtCI_Ch3_Python

Ch1. 배열과 문자열

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 해시테이블

  • 해시테이블(파이썬의 dict)은 키와 값으로 대응되는 자료구조이다.

  • 해시코드 충돌로 인해 최악의 수행 시간은 O(N)이지만, 일반적으로 탐색 시간은 O(1)이다.

  • python dict time complexity에서 시간 복잡도를 확인할 수 있다.

• 리스트

  • 가변 크기의 자료구조를 원할 때는 리스트(배열)을 사용하게 된다.

  • 리스트는 O(1)의 접근 시간을 유지한다.

  • 리스트의 크기를 두배로 늘리는 시간은 O(n)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간은 O(1)이 된다.

    • Go 를 생각해보자. 슬라이스에 아이템을 하나씩 append 하다가 처음에 정의한 슬라이스의 크기보다 더 들어가야 된다면 그때, 슬라이스의 크기가 두배 늘어나는 상황이다.

  • 상환 입력 시간이 O(1)인 이유

    • 크기가 N인 배열을 생각해보자. N개의 원소를 삽입하기 위해 얼마나 많은 원소를 복사해야 하는지 역으로 계산할 수 있다.

      1 2 3 4 5 6 7 8

      마지막 배열 크기 증가 : n/2 개의 원소 복사 이전 배열 크기 증가 : n/4 개의 원소 복사 이전 배열 크기 증가 : n/8 개의 원소 복사 . . . 두 번쨰 배열 크기 증가 : 2 개의 원소 복사 첫 번째 배열 크기 증가 : 1 개의 원소 복사

    • 즉, N개의 원소를 삽입하기 위해 복사해야 하는 원소의 총 개수는 1+2+…N/8+N/4+N/2 이며 이는 N보다 작다.

    • 따라서, O(N)이 소요되는 삽입 연산도 존재하기는 하지만 평균적으로 삽입 연산은 O(1)이 소요된다.

Ch1. 연습문제 코드

CtCI_Ch1_Python