[데이터 엔지니어링 데브코스 4기] 1주차 WIL

9월 25일부터 프로그래머스 데이터 엔지니어링 데브코스 4기 강의가 시작되었습니다!

 

각 일자별로 실시간 + 녹화 강의, 녹화강의, 실시간 강의 3가지 형태로 진행되고 있고,
이론적인 부분해 대한 강의는 대부분 녹화강의로 이루어져 있어 복습, 예습을 하기에 좋은 환경인 것 같아요.

 

선발 시에 코딩테스트 과정이 있었지만,
초반 강의는 자료구조, 알고리즘에 대한 내용으로 이루어져 있었습니다.

컴퓨터 공학을 전공했기에 배웠거나 들었던 내용이지만, 사용하지 않은지 꽤 긴 시간이 지나서 강의 후 실습에 꽤 애를 먹었습니당...

각 날짜에 배운 걸 TIL로 작성하고 싶은데, 진도 따라가기에도 벅찬 게 현실이네요 ㅋㅋㅋㅋㅋㅋㅋ...

그렇기에 앞으로는 TIL, WIL을 혼용해서 개인 리뷰 형식으로 작성하도록 하겠습니다!

 

1주 차에 진행한 내용은

9/25(수) - 데이터 엔지니어링 데브코스 4기 OT

9/26(목) - 리스트(타 언어의 배열), 재귀, 연결리스트, 스택

9/27(금) - 코딩테스트 특강, 큐, 트리, 힙

이었습니다..!

 

생각보다 실습의 양이 많아(선택 강의이지만..) 저처럼 오랜만에 코딩을 하시거나, 처음 접하시는 참여자 분들께서는 하루에 8시간보다 더 많은 시간을 투자하셔야 할 것 같아요!!

 

9월 25일에는 OT를 진행했으니 다른 일자에 진행한 내용 중 중요하거나, 알아두면 좋겠다고 생각된 내용을 정리하겠습니다!

9/26(목)

List

• .append() : List에 원소를 추가하는 연산 ( '+' 연산자를 통한 추가도 가능하지만, append가 성능면에서 유리!)

재귀

• 동일한 알고리즘을 탈출 조건까지 반복적으로 호출해서 문제를 해결하는 방법

복잡도

• 코딩테스트에서 정확성도 중요하지만, 시간 복잡도도 만만치 않게 중요!!
  -> O(n)으로 풀 수 있는 문제를 O(n^2) 시간 복잡도를 갖는 알고리즘으로 풀면 시간 초과가 날 수도...

Linked List

• List(타 언어 배열)를 주차장에 주차된 차라고 한다면, Linked List는 각 칸이 연결된 기차라고 할 수 있을 것 같다!!
  -> 어느 것이 유리하다고는 할 수 없지만, 두 자료구조 각각 장단점이 있다!
• 파이썬에는 Linked List를 지원하는 모듈이 없기에 직접 Node와 Linked List를 구현해야 한다!!

List vs Linked List

• List 장점
  1. 인덱스 기반 접근 시간 복잡도가 O(1)로 매우 빠르다!
• List 단점
  1. 원소(요소) 삽입, 삭제하는 연산의 경우 평균적으로 O(n)이 소요된다..
• Linked List 장점
  1. 각 노드가 다음 노드를 가리키는 포인터를 갖기에 삽입, 삭제가 O(1)으로 효율적이다! (** 노드를 찾는 시간은 별도로 필요...)
• Linked List 단점
  1. 인덱스 접근이 불가능하기에, head부터 포인터를 타고 찾게 되어 특정 노드를 찾기 위해 O(n) 시간 복잡도를 갖는다.

Stack

• 후입선출(LIFO)의 형태를 갖는 자료구조!
• 사용할 수 있는 방식
  1. List 사용
  2. collections.deque 사용 (! 주의점 : pop()이 아닌 popleft()를 사용하면 queue가 되어 버린다..)

9/27(금)

Queue

• 선입선출(FIFO)의 형태를 갖는 자료구조!
• 사용할 수 있는 방식
  1. collections.deque 사용 (!주의점 : popleft()가 아닌 pop()을 사용하면 stack이 되어 버린다..)
  2. queue.Queue 사용
• Circular Queue
  • 등장 배경 : Queue에서 삽입, 삭제가 반복되게 되면 front, rear 포인터가 계속 증가하게 되고, 큐의 앞부분에 빈 공간이 있더라 하더라도 값을 삽입할 수 없는 문제가 발생하기에 이미 데이터가 삭제된 공간을 재활용하기 위해 등장
  • 각 포인터 위치 : (포인터 + 1) % size로 계산
  • (rear + 1) % size == front일 때 큐 포화 -> rear 다음 값이 front이므로 값을 삽입할 공간이 없다!!
  • front == -1일 때 빈 큐
• Priority Queue
  • 2가지 형태로 구현 가능
    1. 큐에 값을 삽입할 때 정렬해서 넣기
       • 삽입 시 O(n)의 시간복잡도, 추출 시 O(1)의 시간복잡도
    2. 큐에서 값을 추출 시 우선순위가 높은 값부터 추출하기
       • 삽입 시 O(1)의 시간복잡도, 추출 시 O(n)의 시간복잡도
         -> 그렇기에 어떤 작업이 더 많이 일어나느냐에 따라 구현방식이 달라진다!!

Tree

• Tree라는 이름 그대로 나무와 같은 구조를 가진다!
• 재귀적 성질을 가짐!
• 용어
  • root node : 부모가 없는 최상단의 노드
  • edges : 간선으로 부모와 자식을 이어주는 나뭇가지 같은 역할!
  • leaf node : 자식이 없는 말단 노드
  • internal node : leaf node가 아닌 노드
  • sibiling : 같은 부모를 갖는 노드
  • size : 총노드의 개수
  • depth : root ~ 해당 노드까지의 간선 수
  • level : depth와 동일한 개념으로 root node는 0 level
  • degree : 하위 트리의 수 / 간선 수
  • degree of tree : 트리의 최대 차수(degree)
  • height : 최말단 노드의 depth
• Binary Tree
  • 트리에 포함되는 모든 노드의 차수가 2 이하인 트리 -> 모든 노드는 자식이 없거나 최대 2개까지 가진다!
• dfs(깊이 우선 탐색)
  • 용어 그대로 깊이를 우선적으로 탐색!
    • in-order traverasl(중위 순회)
    • 순서 : 왼쪽 서브트리 -> 자기 자신 -> 오른쪽 서브트리
    • pre-order traversal(전위 순회)
    • 순서 : 자기 자신 -> 왼쪽 서브트리 -> 오른쪽 서브트리
    • post-order traversal(후위 순회)
    • 순서 : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 자기 자신
• bfs(너비 우선 탐색)
  • 재귀적인 성질을 갖지 않는다!!!! -> 선형의 성질을 갖는 Queue로 구현!!!
    • 어떻게?? -> 트리의 root로 시작하는 Queue를 만들고 Queue가 빈 Queue가 될 때까지 자기 자신을 추출해서 하고 왼쪽, 오른쪽 자식을 순서대로 queue에 삽입하여 탐색 가능!
  • 깊이가 아닌 같은 레벨의 노드를 먼저 탐색한다!
• Binary Search Tree
  • 정렬된 선형 배열을 대상으로 배열을 절반씩 잘라서 찾기에 O(log_2(n))의 시간 복잡도를 갖는다!
    • 이진 탐색을 하기 위해서는 배열이 미리 정렬되어 있어야 하기에, 삽입과 삭제에 O(n)의 시간 복잡도를 갖는다
  • 모든 노드에 대해 왼쪽 서브트리 값 < 부모 노드 값 < 오른쪽 서브트리 값을 만족하도록 해야 한다!!
    • 그렇기에 넣으려는 노드의 key 값이 부모(현재) 노드의 값보다 작다면
      1. 왼쪽 자식 노드의 유무를 확인
      2. 있다면, 재귀적으로 그 자식의 왼쪽, 오른쪽 자식(현재 노드의 손자)에 해당하는 값을 확인하도록!
      3. 없다면, 왼쪽 자식 노드에 해당 값을 갖는 노드를 만들어 삽입!
    • 크다면?
      1. 오른쪽 자식 노드의 유무를 확인
      2. 있다면, 재귀적으로 그 자식의 왼쪽, 오른쪽 자식(현재 노드의 손자)에 해당하는 값을 확인하도록!
      3. 없다면, 오른쪽 자식 노드에 해당 값을 갖는 노드를 만들어 삽입!
  • 삽입의 경우 생각보다 간단하지만, 삭제의 경우보다 복잡하다.
    1. 삭제하려는 노드가 리프 노드(자식이 없는 노드)일 경우
       • 트리의 구조에 영향을 미치지 않기에 부모와의 연결을 끊어주면 된다!
    2. 삭제하려는 노드가 자식을 하나만 가진 경우
       • 삭제하려는 노드를 자식 노드로 교체
       • 삭제하려는 노드의 부모가 없다면, 루트 노드이므로 루트 노드 = 자식 노드로 변경!
    3. 삭제하려는 노드가 자식을 둘 가지는 경우
       • 우선 후계자란, 삭제할 노드를 대체할 노드이다!
       • 오른쪽 서브트리에서 가장 작은 후계자 값을 찾거나, 왼쪽 서브트리에서 가장 큰 선행자를 찾는 2가지 방법이 있지만, 더 나은 트리 구조를 갖기 위해서는 오른쪽 서브트리의 값으로 변경하는 게 좋다!
         3-1. 부모의 오른쪽 자식의 왼쪽 자식이 없을 때까지. 즉, 오른쪽 서브트리에서 가장 작은 값을 찾을 때까지 찾아 내려가며 후계자 값(처음에는 오른쪽 서브트리이기에 오른쪽 자식이지만, 그 이후로는 왼쪽 자식)과 부모 값을 바꾸고, 후계자 값은 바뀐 부모(기존 후계자)의 왼쪽 자식으로 변경하는 작업을 반복한다.
         3-2. 이후 후계자가 부모의 왼쪽 자식인지 오른쪽 자식인지 판단하여 부모의 왼쪽 혹은 오른쪽 자식을 후계자의 오른쪽 자식으로 교체해 준다. -> 그 이유는 후계자는 오른쪽 서브트리에서 가장 작은 값이므로 왼쪽 자식은 존재하지 않기 때문!!!!!!!!

Heap

• 이진트리의 한 종류로 완전 이진트리의 성질을 가진다!
• 루트 노드가 항상 최대 값이거나 최소 값인 최대 힙, 최소 힙이 존재한다.
• 서브트리 또한 최대힙의 성질을 갖는다!
• 삽입, 삭제, 정렬 모두 O(log(n)) 시간 복잡도를 갖는다!
• heapq라는 모듈을 파이썬에서 지원하며, 해당 모듈은 최소 힙만 지원하지만, 값에 -1을 곱하는 등 음수로 저장하여 최대힙으로 사용이 가능하다.
• 삽입(heapq.heappush(리스트 명, 값))
• 삭제(heapq, heappop(heap))

회고

학교를 다니면서 배웠던 내용인데, SQL만 사용하다 보니 해당 내용에 대해 '뭐였던 거 같은데...' 하는 생각은 들어도 정확히 어떠한 자료구조이고, 시간 복잡도는 어떻게 되는지 99프로가 기억나지 않았다..ㅠ
코딩테스트에 겁을 먹고 있고, 풀어봤자 어렵지 않은 구현, 수학 문제만 풀 정도에서 너무 안일하게 살아온 것 같다.
그리고 기존에 사용했던 JAVA나 C++이 아니라 새롭게 공부하는 Python이기에 기본기를 탄탄하게 해서 코딩테스트를 부술 정도로 레벨업을 하고 싶다!
물론 아직 구글링과 Chatgpt의 도움을 많이 받고 있지만, 꾸준히 해서 내년 상반기 취업까지 성실히 달려보려고 한다!!!!

난잡한 글이지만, 봐주셔서 감사합니다!