프로그래머스 인공지능 데브코스 1주차 정리 및 후기

이번 글에서는 프로그래머스 인공지능 데브코스 합격 후기에 이어서 1주차 강의에 대한 정리입니다.
지원 과정에서 코딩 테스트가 있었긴 했지만, 기본적인 자료구조나 알고리즘은 매우 중요합니다.
그러한 이유 때문인지 이번 1주차에서는 기본적인 github 사용법과 함께 자료구조와 알고리즘을 배웁니다.
그리고 배운 내용과 연관 되어 있는 코딩 테스트 문제도 함께 풀어보는 시간을 갖습니다.

1. [K-Digital-Training] 인공지능 데브코스

코드 리뷰 하는 방법

깃헙 (GitHub) 사용 방법을 배우자.
- 브랜치 만들고, 해당 브랜치로 이동 -> git checkout -b <branch name>
- 작업한 내용 커밋 및 메시지 남기기 -> git commit -a -m <commit message>
- 커밋한 내용 브랜치에 푸쉬하기 -> git push
- 깃헙 페이지에서 PR (Pull Request) 생성하기
- 깃헙 페이지에서 PR 리뷰 및 merge
깃헙을 사용하는 이유는 여러 사람들과 함께 작업하기 위함이므로 나름의 규칙을 지키자.
- 코드 공유 및 리뷰는 서로 더 나은 코드를 만들기 위한 커뮤니케이션 과정
- feature 브랜치 생성 방법 및 규칙, PR의 제목 형태
참고할 수 있는 링크

알고리즘 이야기 - 요약

얼핏 보기에는 특정 라이브러리나 프레임워크를 잘 다뤄서 서비스를 만드는 코딩이 중요해보인다.
하지만 실제 개발자에게 가장 필요한 것 중 하나는 문제 해결 능력의 기반이 되는 알고리즘이다.
알고리즘은 자신의 논리적 사고나 문제 해결 능력의 기반이 되어줄 수 있다.
알고리즘 문제를 풀었다면, 어떻게 풀었는지 정리하고, 다른 사람들의 코드를 많이 보며 배우자.
간결하고 가독성 좋은 코드를 작성하자. 일관성 있는 코드를 작성하자.
참고할 수 있는 링크
- visualgo
- algorithm-visualizer

2. 어서와! 자료구조와 알고리즘은 처음이지? (1)

안녕, 자료구조 & 알고리즘!

문자열 (str), 리스트 (list), 사전 (dict), 순서쌍 (tuple), 집합 (set)
해결하고자 하는 문제에 따라 최적의 해법은 서로 다를 수 있다. 따라서 자료구조 공부가 필요하다.
알고리즘이란?
- 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
- 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

선형 배열 (Linear Array)

배열: 원소들을 순서대로 늘어놓은 것
리스트 (배열) 연산 -> 리스트의 길이에 비례하여 선형적으로 시간이 걸림
- 가장 마지막에 원소 덧붙이기 -> append()
- 가장 마지막 원소 꺼내고, 리스트 반환하기 -> pop()
- 특정 위치에 원소 삽입하기 -> insert(index위치, 삽입할 값)
- 특정 리스트의 위치에 있는 원소 삭제하기 -> del(리스트[index])
- 찾고자 하는 원소 index 탐색하기 -> index(찾고자 하는 원소)

정렬 (Sort), 탐색 (Search)

파이썬 리스트의 정렬
- sorted(): 내장 함수, 정렬된 새로운 리스트를 얻음
- sort(): 리스트의 메서드, 해당 리스트를 정렬함
- 정렬 순서를 반대로 하고 싶은 경우에는 reverse = True 조건 추가
- 문자열로 이루어진 리스트에서 정렬 순서는 사전 순서를 따름

  
L = [ {'name': 'John', 'score': 83}, {'name': 'Paul', 'score': 92} ]

L.sort(key = lambda x: x['name'])  # name 순서로 정렬
L.sort(key = lambda x: x['score']) # score 순서로 정렬

선형 탐색 (Linear Search): 앞에서 부터 뒤에까지 순차적으로 탐색하는 방법
- 값을 찾을 때까지 리스트의 길이만큼 반복
- 리스트의 길이에 비례하는 시간 소요 -> O(n)
- 최악의 경우에는 모든 원소를 다 비교해봐야 함

  
def linear_search(L, x):
    i = 0
    while i < len(L) and L[i] != x:
        i += 1

    if i < len(L): return i
    else: return -1

이진 탐색 (Binary Search): 탐색하려는 리스트가 이미 정렬된 경우에만 적용 가능
- 크기 순으로 정렬되어 있다는 성질 이용
- 한 번 비교가 일어날 때마다 리스트를 절반씩 줄임 (divide & concuer) -> O(log n)

  
def binary_search(L, x):
    idx = -1
    lower, upper = 0, len(L) - 1

    while lower <= upper:
        middle = (lower + upper) // 2
        if L[middle] == x: return middle
        elif L[middle] < x: lower = middle + 1
        else: upper = middle - 1

재귀 알고리즘 기초

재귀함수 (Recursive function): 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
이진 트리 (Binary trees): 이진 탐색과 유사하게 접근할 수 있음

예제 1. 1부터 n까지 모든 자연수의 합 구하기

  
def sum(n): # O(n)
    if n <= 1: return n          # 종결 조건 (trivial case), 점화식
    else: return n + sum(n - 1)

def sum(n): # O(n)
    s = 0
    while n >= 0:
        s += n
        n -= 1
    return s

예제 2. 펙토리얼 (!)의 재귀 함수

  
def factorial(n):
    if n <= 1: return 1
    else: return n * factorial(n - 1)

예제 3. 피보나치 순열의 재귀 함수

  
def fibonacci(x):
    if x == 0: return 0
    elif x == 1: return 1
    else: return solution(x - 1) + solution(x - 2)

재귀 알고리즘 응용

예제 1. 조합의 수 계산 - n개의 서로 다른 원소에서 m개를 선택하는 경우의 수

  
from math import factorial as f

def combi(n, m):
    return f(n) / (f(m) * f(n - m))

def combi(n, m):
    if n == m: return 1
    elif m == 0: return 1
    return combi(n - 1, m) + combi(n - 1, m - 1)

알고리즘의 복잡도

시간 복잡도 (Time Complexity): 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계
공간 복잡도 (Space Complexity): 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계
평균 시간 복잡도 (Average Time Complexity): 임의의 입력 패턴을 가정했을 때, 소요되는 시간의 평균
최악 시간 복잡도 (Worst-case Time Complexity): 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
Big-O Notation: 점근 표기법의 하나 - 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
- 입력의 크기가 n 이라고 할 때,
- O(logn)은 입력의 크기의 로그에 비례하는 시간이 소요된다는 것
- O(n)은 입력의 크기에 비례하여 시간이 소요된다는 것
- 계수는 그다지 중요하지 않음
선형 시간 알고리즘: n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘 적용 -> O(n)
로그 시간 알고리즘: n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘 적용 -> O(logn)
이차 시간 알고리즘: 삽입 정렬 (insertion sort) -> O(n^2)
보다 낮은 복잡도를 갖는 정렬 알고리즘: 병합 정렬 (merge sort) -> O(nlogn)
복잡한 문제: 배낭 문제 (Knapsack problem)

연결 리스트 (Linked Lists)

추상적 자료구조 (Abstract Data Structures)
- Data: 정수, 문자열, 레코드
- A set of operations: 삽입, 삭제, 순회, 정렬, 탐색
기본적인 연결 리스트 (Node)는 데이터와 Link (next)를 포함하고 있음
연산 정의: 특정 원소 참조, 리스트 순회, 길이 얻어내기, 원소 삽입 및 삭제, 두 리스트 합치기
배열과 비교한 연결 리스트

특징	배열	연결 리스트
저장 공간	연속한 위치	임의의 위치
특성 원소 지칭	매우 간편	선형 탐색과 유사
Big-O 표기	O(1)	O(n)

  
class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos <= 0 or pos > self.nodeCount: return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

원소의 삽입

  
def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodCount + 1:
        return False

    if pos == 1:
        newNode.head = self.head
        self.head = newNode
    else:
        if pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        newNode.head = prev.next
        prev.next = newNode
    
    if pos == self.nodCount + 1:
        self.tail = newNode

    self.nodeCount += 1
    return True

연결 리스트 원소 삽입의 복잡도
- 맨 앞에 삽입하는 경우: O(1)
- 중간에 삽입하는 경우: O(n)
- 맨 끝에 삽입하는 경우: O(1)
연결 리스트가 힘을 발휘할 때: 삽입과 삭제가 유연하다는 것

양방향 연결 리스트 (Doubly Linked Lists)

한 쪽으로만 링크를 연결하지 말고, 양쪽으로 링크를 연결하자
앞으로도 (다음 Node), 뒤로도 (이전 Node) 진행 가능

3. 어서와! 자료구조와 알고리즘은 처음이지? (2)

스택 (Stacks)

자료 (Data element)를 보관할 수 있는 선형 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 (push 연산)
꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 (pop 연산)
후입선출 (LIFO - Last In First Out) 특징을 갖는 선형 자료 구조
스택의 추상적 자료 구조 구현
- 배열을 이용하여 구현: Python 리스트와 메서드 이용
- 연결 리스트 (Linked list)를 이용하여 구현: 양방향 연결 리스트 이용
- size(): 현재 스택에 들어 있는 데이터 원소의 수
- isEmpty(): 현재 스택이 비어 있는지 판단
- push(x): 데이터 원소 x를 스택에 추가
- pop(): 스택의 맨 위에 저장된 데이터 원소를 제거 및 반환
- peek(): 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)

수식의 후위 표기법

중위 표기법 (infix notation): 연산자가 피연산자들의 사이에 위치 -> (A + B) * (C + D)
후위 표기법 (postfix notation): 연산자가 피연산자들의 뒤에 위치 -> A B + C D + *
중위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 그냥 출력
- ’(‘ 이면 스택에 push, ‘)’ 이면 ‘(‘가 나올 때까지 스택에서 pop, 출력
- 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력

큐 (Queues)

자료를 보관할 수 있는 선형 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 (enqueue, 인큐 연산)
꺼낼 때에는 반대 쪽에서 뽑아야 하는 제약 (dequeue, 디큐 연산)
선입선출 (First In First Out, FIFO) 특징을 갖는 선형 자료구조
큐의 추상적 자료구조 구현
- size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함 - O(1)
- isEmpty(): 현재 큐가 비어 있는지를 판단 - O(1)
- enqueue(x): 데이터 원소 x를 큐에 추가 - O(1)
- dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거 및 반환 - O(n)
- peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음) - O(1)

환형 큐 (Circular Queue)

큐의 활용
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳애서 일어나는 경우
- 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
환형 큐
- 정해진 개수의 저장 공간을 빙 돌려가면서 이용
- 큐가 가득차면, 더이상 원소를 넣을 수 없음
환형 큐의 추상적 자료구조 구현
- 기존의 큐의 추상적 자료구조 구현 내용과 동일
- isFull(): 큐에 데이터 원소가 꽉 차 있는지를 판단

우선순위 큐 (Priority Queue)

큐가 FIFO 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
우선순위 큐의 구현
- enqueue 할 때, 우선순위 순서를 유지하도록 구현
- 연결 리스트 (Linked List)를 이용하여 구현

이진 트리 (Binary Trees) - 깊이 우선 순회

이진 트리의 추상적 자료구조
- size(): 현재 트리에 포함되어 있는 노드의 수를 구함
- depth(): 현재 트리의 깊이 또는 높이를 구함
- 순회 (traversal)
이진 트리의 순회
- 깊이 우선 순회 (depth first traversal)
  - 중위 순회 (in-order traversal)
  - 전위 순회 (pre-order traversal)
  - 후위 순회 (post-order traversal)
- 넓이 우선 순회 (breadth first traversal)

이진 트리 (Binary Trees) - 넓이 우선 순회

원칙
- 수준이 낮은 노드를 우선으로 방문
- 같은 수준의 노드들 사이에는,
  - 부모 노드 방문 순서에 따라 방문
  - 왼쪽 자식 노드를 오른쪽 자식 보다 먼저 방문
- 재귀는 적합하지 않을 수 있음
- 한 노드를 방문 했을 때, 나중에 방문할 노드를 순서대로 기록해야 함 (큐를 이용!)
넓이 우선 순회 알고리즘 구현
- 초기화 -> traversal = 빈 리스트, q = 빈 큐
- 빈 트리가 아니면, root node를 q에 추가 (enqueue)
- q가 비어 있지 않는 동안
  - q에서 원소를 추출 (dequeue)
  - node를 방문
  - node의 왼쪽, 오른쪽 자식들을 q에 추가
- q가 빈 큐가 되면, 모든 노드 방문 완료

이진 탐색 트리 (Binary Search Trees)

모든 노드에 대해서 다음의 성질을 만족하는 이진 트리
- 왼쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 작음
- 오른쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 큼
정렬된 배열을 이용한 이진 탐색과 비교
- 장점은 데이터 원소의 추가, 삭제가 용이
- 단점은 공간 소요가 큼 -> O(logn)의 탐색 복잡도
이진 탐색 트리의 추상적 자료구조
- 각 노드는 (key, value) 쌍을 가지고 있음
- 키를 이용해서 검색 가능, 보다 복잡한 데이터 레코드로 확장 가능
- insert(key, data): 트리에 주어진 데이터 원소를 추가
- remove(key): 특정 원소를 트리에서 삭제
- lookup(key): 특정 원소를 검색
- inorder(): 키의 순서대로 데이터 원소를 나열
- min(), max(): 최소 키, 최대 키를 갖는 원소를 각각 탐색
이진 탐색 트리에서 원소를 삭제
- 키를 이용하여 노드를 찾음 (찾은 노드의 부모 노드도 알고 있어야 함)
- 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리
  - 삭제되는 노드가 말단 (Leaf) 노드인 경우 - 그 노드를 없애면 됨 (부모 노드 링크 조정)
  - 삭제되는 노드가 자식을 하나 갖고 있는 경우 - 삭제되는 노드 자리에 그 자식을 대신 배치
  - 삭제되는 노드가 자식을 둘 갖고 있는 경우 - 삭제되는 노드보다 바로 다음 큰 가지는 노드를 찾아 대신 배치

힙 (Heaps)

이진 트리의 한 종류 (이진 힙 - Binary Heap)
- 루트 노드가 언제나 최댓값 또는 최솟값을 가짐
- 완전 이진 트리여야 함
이진 탐색 트리와의 비교
- 원소들은 완전히 크기 순으로 정렬되어 있는가?
- 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
- 부가의 제약 조건은 어떤 것인가?
최대 힙의 추상적 자료구조
- init(): 빈 최대 힙을 생성
- insert(item): 새로운 원소를 삽입
- remove(): 최대 원소를 반환 및 이 노드를 삭제
최대 힙에 원소 삽입
- 트리의 마지막 자리에 새로운 원소를 임시로 저장
- 부모 노드와 키 값을 비교하여 위로, 위로, 이동
- 부모 노드와의 대소 비교 최대 횟수는 log2n
- 최악의 복잡도는 O(logn)의 삽입 연산
최대 힙에 원소 삭제
- 루트 노드의 제거 -> 이것이 원소들 중 최댓값
- 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
- 자식 노드들과의 값 비교와 아래로, 아래로, 이동
- 원소의 개수가 n인 최대 힙에서 최대 원소 삭제 최대 횟수는 2 * log2n
- 최악의 복잡도는 O(logn)의 삭제 연산
최대 및 최소 힙의 응용
- 우선 순위 큐 (Priority queue)
  - enqueue 할 때, 느슨한 정렬을 이루고 있도록 함 - O(logn)
  - dequeue 할 때, 최댓값을 순서대로 추출 - O(logn)
- 힙 정렬 (Heap sort)
  - 정렬되지 않은 원소들을 아무 순서대로 최대 힘에 삽입 - O(logn)
  - 삽입이 끝나면, 힙이 비게 될 떄까지 하나씩 삭제 - O(logn)
  - 원소들이 삭제된 순서가 원소들의 정렬 순서
  - 정렬 알고리즘의 복잡도: O(nlogn)

4. 파이썬을 무기로, 코딩테스트 광탈을 면하자! (1)

5. 파이썬을 무기로, 코딩테스트 광탈을 면하자! (2)

6. 코딩테스트 풀이 참고 자료

PEP8 스타일 가이드

7. 1주차 돌아보기

기간: 2022. 09. 19 ~ 2022. 09. 24

퇴사를 앞두며, 다음 스텝을 준비하기 위해 고민하던 중에 프로그래머스 데브코스를 참여하게 됐다. 그리고 그 첫 주가 시작되었고, 잠깐이지만 회사와 병행해야 했던 이번 주는 개인적으로 조금 힘들었던 것 같다. 물론 배우는 내용들은 의미있고, 재밌긴 했지만 아무래도 회사와 함께 시간을 사용해야 되다보니 약간 벅찼던 것 같다.

그럼에도 파이썬의 알고리즘과 자료구조를 다시 공부할 수 있는 기회가 되고, 누군가의 코딩테스트 문제 풀이 과정을 복기하며 내 사고를 돌아볼 수 있는 기회를 갖게 된 것 같은 참 뜻깊었던 것 같다. 나 역시 코딩테스트를 오랫동안 준비해봤던 것이 아니라, 부족한 부분들이 많이 있을텐데 이번 기회에 그런 문제점들과 개선해야 하는 부분들을 조금씩 확인할 수 있는 기회가 되었다.

다음 주부터는 회사에서는 연차를 사용하면서 퇴사를 앞두고 있는데, 퇴사 후에 나에게 주어진 시간들을 어떻게 써야 할지를 고민하며 이 시간에 대해 더 고민하고, 또 고민해보도록 하자.

출처: 프로그래머스 인공지능 데브코스 4기 1주차 강의 -> 강의 내용 정리 깃허브 링크