TIL(Today I Learned)

12월 9일(수)

학습내용

• 야곰이 업로드한 재미난 컴퓨터 기초 2편을 보고 공부하였다.
  • 알고리즘
    • 문제 해결을 위한 절차/방법, 어떠한 문제를 해결하기 위한 동작들의 모음.
    • 대표적인 알고리즘: 정렬, 탐색, 재귀 등
    • 정렬 알고리즘의 작동 영상을 보면서 더 직관적으로 정렬 알고리즘을 깨달을 수 있었다.
    • 시간복잡도, 공간복잡도를 이용해서 알고리즘 성능을 표현한다
    • 병합, 퀵 정렬을 O(nlogn), 선택, 버블, 삽입 정렬은 O(n^2)이다.
    • 선형탐색 O(n), 이진탐색 O(logn)이다.
    • 이진탐색은 반씩 나눠서 탐색하는 방법이다.
  • 자료구조
    • 자료를 효율적으로 이용할 수 있는 방법론, 데이터를 구조적으로 표현하는 방식
    • 원시구조, 배열, 연결리스트(단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트)
    • 배열은 크기를 정해놓고 데이터를 순서대로 저장하는 방식이다.
    • 연결리스트는 원소가 다음 원소 주소를 갖고 있는 방식으로 구성되어있다.
    • 연결리스트는 넣고 빼는 것이 자유롭다. 하지만 특정 원소를 찾아가는 것이 오래걸린다.
    • Stack: First In Last Out, 웹페이지 뒤로가기가 스택 구조이다.
    • Queue: 선입 선출, 대기열.
    • Dequeue: Stack과 Queue를 합쳐놓은것, Double-Ended Queue
    • Tree: 뿌리로부터 노드가 파생되어 나가는 구조.
    • Graph: 서로 연결된 그물망.
    • Tree VS Graph: 트리는 뿌리가 있고 그로부터 가지가 뻗어나가는 모양이지만, 그래프는 시작과 끝이 없다.

문제점/고민한점

• 왜 이진탐색의 공간복잡도는 O(logn)일까?

해결방법

• 왜 이진탐색의 공간복잡도는 O(logn)일까?
  • 만약 총 128개 데이터 중 1개를 찾아야 한다면, 이를 반씩 계속 나누면 64, 32, 16, 8, 4, 2, 1의 순으로 7번 데이터를 나누게 된다. 즉 최악의 경우 7번을 시행해야한다. 7 = log128(밑이 2)이므로 시간복잡도는 O(logn)인 것이다.