시작하기에 앞서 나는 블로그를 작성하는 것이 익숙해지기 전까지 TIL을 "Today I Learned"가 아닌 "This week I Learned"로 정의하고 매주 최소 한 번씩 기록해보려고 한다.

지난 주 Python EDA 팀 프로젝트를 마치고 이번주는 자료구조 및 알고리즘 개론 대한 수업을 들었다.

자료구조 및 알고리즘

이번 과정에서는 모든 자료구조와 알고리즘을 커버하기 보다 실제 코딩테스트에 자주 출제되는 부분들 위주로 수업이 진행되었다.

스택 (Stack)

• LIFO (Last In First Out)

• 가장 마지막에 삽입된 자료가 가장 먼저 삭제됨
  

• 주요 코드 :

  # 데이터 삽입
  stack.append(data)
  # 데이터 삭제
  stack.pop()

Leetcode - Valid Parenthesis (Stack 문제1)
Leetcode - Daliy Temperature (Stack 문제2)

해시테이블(Hash Table)

• Key-Value쌍의 데이터를 입력받는 효율적인 탐색 자료구조
• Hash function h를 통해 h(key) 함수값에 해당하는 index에 (key, value) 데이터 쌍 저장
• Python에서는 Hash Table로 구현된 Dictionary 사용 (데이터 순서 없음)
• 주요 코드 :

  # dictionary 선언 및 데이터 추가
  dict = {}
  dict['key] = value

Collision

• 서로 다른 Key의 해시값이 같을 때 발생
• hash function을 잘 설계하는 것이 중요
• Seperate Chaining, Open Addressing 등으로 해결

시간 복잡도

• 저장, 삭제, 검색의 시간 복잡도 : O(1)

Leetcode - Two Sum (Dictionary 문제)

Tree

• 계층형 자료구조 (비선형적)

주요 용어 (Terms)

• 정점 (vertex) : A, B, C와 같은 값을 가진 노드
• 간선 (edge) : 정점 간에 연결된 선
• 자식 노드 (child node)
• 부모 노드 (parent node)
• 형제 노드 (sibling) : 같은 부모를 가진 노드
• 리프 노드 (leaf node) : 더이상 뻗어나갈 수 없는 마지막 노드
• 차수 (degree) : 각 노드의 자식의 수
• 조상 (ancestor) : 간선을 위로 따라가며 만나는 노드들
• 자손 (descendant) : 간선을 아래쪽으로 따라가며 만나는 노드들
• 루트 노드 (root node) : 트리의 시작 점
• 높이 (height) : 루트에서 리프까지의 거리
• 레벨 (level) : 루트에서 떨어진 거리

트리 순회 (Tree Traversal)

Level-Order Traversal

• Queue를 통해 구현하며 이어진 자식 노드들 부터 탐색 (level 별 탐색)
• 시간 복잡도 : O(n)

전위순회 (Preorder)

• 현재노드 먼저 방문 후 자식 노트 방문
• ex) 루트 -> 왼쪽 자식 -> 오른쪽 자식
• 시간 복잡도 : O(n)
• 주요 코드 :

  def preorder(root):
      if root is None:
          return
      print(root)
      preorder(root.left)
      preorder(root.right)

중위순회 (Inorder)

• 현재노드 중간에 방문
• ex) 왼쪽 자식 -> 루트 -> 오른쪽 자식
• 시간 복잡도 : O(n)
• 주요 코드 :

  def preorder(root):
      if root is None:
  		return
      inorder(root.left)
      print(root)
      inorder(root.right)

후위순회 (Postorder)

• 자식노드를 모두 방문 후 현재노드 방문
• ex) 왼쪽 자식 -> 오른쪽 자식 -> 루트
• 시간 복잡도 : O(n)
• 주요 코드 :

  def postorder(root):
      if root is None:
          return
      postorder(root.left)
      postorder(root.right)
      print(root)

Graph

• 정점(vertext)들과 간선(edge)으로 구성된 자료구조
• 연결 관계를 표현하기 때문에 현실 세계의 사물이나 추상적인 개념들을 잘 표현할 수 있음
• indegree : 정점에 들어오는 간선
• outdegree : 정점에서 나가는 간선

그래프의 종류

무향 그래프(Undirected Graph) vs. 방향 그래프(Directed Graph)

• 무향 그래프 : 간선의 방향이 없음
• 방향 그래프 : 간선의 방향이 정해져 있음
• 코딩테스트에서는 주로 무향 그래프를 다룸

단순 그래프 vs. 다중 그래프

• 단순 그래프 : indegree와 outdegree가 1인 그래프
• 다중 그래프 : 인접한 두 정점 사이에 outdegree와 indegree가 2 이상인 그래프
• 코딩테스트에서는 주로 단순 그래프를 다룸

가중치 그래프

• 경로마다 가중치(비용)가 다르게 설정된 그래프
• 다익스트라(Dijkstra) 알고리즘에 쓰임

그래프의 구현

인접 행렬

• 각 정점에 연결된 정점들의 index에 1표시
• 정점들의 관계를 제외하고는 모두 0으로 나타내기에 메모리 사용 측면에서 비효율적

  matrix = [
      [0, 1, 0, 0, 0, 0],
      [1, 0, 1, 0, 1, 0],
      [0, 1, 0, 1, 0, 0],
      [0, 0, 1, 0, 1, 1],
      [0, 1, 0, 1, 0, 1],
      [0, 0, 0, 1, 1, 0],
  ]

인접 리스트

• Dictionary 형태로 정의
  - key : 정점
  • value : list형태로 연결 관계 표시
• 코딩테스트에서는 주로 인접리스트 사용

  graph = {
      "A": ["B"],
      "B": ["A", "C", "E"],
      "C": ["B", "D"],
      "D": ["C", "E", "F"],
      "E": ["B", "D", "F"],
      "F": ["D", "E"],
  }

암시적 그래프

• 연결 관계를 직접적으로 나타내지 않음

  graph = [
      [1, 1, 1, 1, 1],
      [0, 0, 0, 1, 1],
      [1, 1, 0, 1, 1],
      [1, 0, 0, 0, 0],
      [1, 1, 1, 1, 1],
  ]

그래프의 순회 (완전 탐색)

• 시간 복잡도 : O(V+E)

BFS (Breadth First Search)

• Level order Traversal과 유사하게 인접 정점부터 탐색

DFS (Depth First Search)

• 출발점에서 시작해 막다른 지점에 도착할 때 까지 깊게 탐색
• 막히면 그 전 정점으로 돌아가 다른 길로 깊이 탐색

Leetcode - Keys and Rooms (BFS/DFS 문제1)
Leetcode - Shortest Path (BFS/DFS 문제2)
Leetcode - Number of Island (BFS/DFS 문제3)

동적 계획법 (Dynamic Programming, DP)

• 정답이 될 가능성이 있는 모든 해결책을 체계적이고 효율적으로 탐색
• DP의 조건 :
  - 중복 하위문제 (Overlapping Subproblems) : 중복 계산해야 하는 하위 문제 존재
  - 최적 부분 구조 (Optimal Substructure) : 하위 문제에서 구한 답이 큰 문제의 최적의 답을 구할 수 있는 구조
• 시간 복잡도 : O(n)

Top-down vs. Bottom-up

• Top-down : f(n) -> f(1) 접근
  - 재귀(recursion)으로 구현
  • tabulation : memoization을 통해 구한 값들을 저장해 놓는 것
• Bottom-up : f(1) -> f(n)
  - 반복문(iteration)으로 구현

Leetcode - Climbing Stairs (DP 문제1)
Leetcode - Min Cost Climbing Stairs (DP 문제2)
Leetcode - Unique Paths (DP 문제3)

느낀점 및 회고

알고리즘 수업이 3일이라는 짧은 기간동안 진행되었던 만큼, 많은 내용을 단기간에 학습하기는 쉽지 않았다. 그래도 코테를 준비해 본 경험이 있었기 때문에 개념을 익히는 부분은 많이 힘들지는 않았다. (그저 10시~19시 풀 실시간 수업이라는게 체력적으로 많이 힘들었을 뿐...)

우선 혼자 공부할 때는 특히 BFS, DFS, DP의 개념은 이해가 갔으나 매번 적용이 쉽지 않았다. 문제에 어떻게 접근해야할지 조차 모르겠다는 생각이 강해서 포기 수준으로 손대지 않고 있었다. 그러나 강사님께서 문제들마다 다양한 접근 방법을 알려주시고 같이 풀이도 해주셔서 완벽히는 아니지만 어느정도 감이 잡힌 것 같다. 그 증거로 수업시간에 내주신 leetcode 문제들은 전부 풀 수 있었다.

코테는 꾸준히 연습하지 않으면 감을 빨리 잃게 되기 때문에 앞으로도 매일 한 문제씩 꾸준히 연습할 것이다.

코테가 코딩 실력의 전부는 아니지만 코테를 통과하지 못한다면 면접의 기회조차 없기 때문에 절대 소홀히 하면 안된다.