WIL, 0613-0619, 2021

이번 주 한 것

문제 풀이 마라톤

걱정했던 알고리즘 주간의 반환점을 통과했다. 겁 먹었던 것처럼 고전하고 있나 스스로 묻자면, 의외로 재미를 느끼며 문제풀이를 하고 있다. 일정 난이도 이상의 문제나 익숙하지 않은 유형의 문제를 만나면 여전히 머리를 뜯지만, 그래도 노려보다 보면 이렇게 쪼개어 생각해볼까 저렇게 접근해볼까, 적어도 어떻게 덤벼볼지 고민하고 그 고민대로 엉성한 알고리즘이라도 짜 보게 된 게 이번 주의 가장 큰 성과. 물론 이렇게 엉성하게 짠 알고리즘으로 접근했다가는 조져지는 건 언제나 나라는 걸 명심하자...

- 일본 작가 이와무라 카즈오의 그림책 '생각하는 개구리'

• asymptotic notation : 내가 짠 알고리즘의 성능이 어떤가? 얼마나 효율적인가?
  • 지금은 일단 문제를 푸는 알고리즘 찾는 데 초점을 두고 있지만, 항상 복잡도에 대한 고민을 하며 코드를 작성하자.
  • 항상 최선의 알고리즘은 없다. 상황에 따라, 데이터 패턴에 따라 효율적인 알고리즘이 따로 있다.
• Array/Linked list, Stack/Queue, Hash, Tree/Heap, Graph
• Binary Search
  • 업앤다운 게임을 생각해보라;
    - 반 탐색 후, 버리거나/취하거나; 다시 반 탐색 후, 버리거나/취하거나 반복.
    - 순차적으로 탐색할 때(O(N))에 비해 시간복잡도 낮음; O(logN)
    - 정렬된 데이터일 때 이진탐색 가능
  • Divide and Conquer; merge sort 참조
    - 분할한 부분들 해결 > 결합, 다시 해결 > 결합 > 최종적으로 원래 문제의 답을 구하는 알고리즘
• Sort; bubble, selection, insertion, merge sort
  • 정렬은 다시 공부!
• DFS/BFS - 맹목적인 탐색 방법; 백트래킹
  • 깊이 우선 탐색
    - 트리/그래프에서 탐색 시 한 루트로 최대한 깊이까지 탐색, 돌아가 다른 루트로 탐색
    - 찾고자 하는 노드가 깊은 곳에 있을 때 좋고, 지나온 경로 노드 기억하면 되므로 비교적 쓰는 공간이 적은 방식
    - 미로찾기 생각해보라; 길이 아닌데 너무 깊이 들어갈 경우(특히 출구는 다른 쪽인데 내가 택한 길이 끝이 없는 길이라면?😵), 일단 길을 찾긴 했는데 최적의 길이 아닌 경우.
  • 너비 우선 탐색
    - 미로찾기를 또 생각해보자면; 최적의 길은 무조건 찾을 수 있다.
    - 그러나 찾고자 하는 노드가 깊이 있다면?
• Recursion, Dynamic Programming, Memoization
  • 재귀함수를 이용한 알고리즘; 반복할 수록 치솟는 시간복잡도
  • 계속 중복되는 작은 단위의 문제를 푼 후 반복을 통해 큰 문제를 풀 수 있다면; 동적계획법 써 볼 수 있다.
  • 작은 단위 문제의 답을 미리 저장해 두었다 중복계산을 하게 될 때 참조해서 쓴다.
    - 즉, 메모리 공간을 조금 내어주고 시간복잡도를 낮출 수 있다.

할 것

문법 익히기에 알고리즘 짜 보는 게 도움이 된다는 걸 새삼 느끼고 있다.

• 파이썬 기본 내장함수 사용법 다시 정리해보기
• int-float 간 형변환시 생기는 오차는 어디에서 오는 걸까?
  • 부동소수점
  • decimal
• 파이썬에서 list 사용시 유의할 것;
  • array list와 linked list가 어떻게 동작하는지 항상 생각하기, 구현하기
• 스택/큐/해쉬 다시 구현하기. 파이썬이나 자바스크립트를 쓰면서 내가 클래스를 어떻게 가지고 놀까 고민.
• 강의 다시 복습.