공부한 내용을 적었습니다. 안다고 생각했는데, 아는 게 아니었던 것 같습니다.
자료구조
컴퓨터는 현실 세계에서의 반복적이고 복잡한 자료들을 효율적으로 처리하기 위한 기계이다. 컴퓨터를 이용해서 자료를 처리하려면 먼저 컴퓨터가 잘 다룰 수 있는 형태로 표현해주어야만 한다. 사람들이 사물을 편리하고 효율적으로 사용하기 위해 정리하는 것과 마찬가지로 컴퓨터에서도 자료들을 정리하고 조직화 하는 여러 가지 구조들이 있다. 이를 자료구조(data structure)라고 한다.
자료구조 분류
- 단순 자료구조
숫자나 문자
- 복합 자료구조
여러 자료들을 한꺼번에 보관하는 컨테이너(container)
복합 자료구조
- 선형(linear) 자료구조
종류: 스택, 큐, 덱(deque), 리스트
항목들을 순서적으로 나열하여 저장하는 창고로 항목들을 접근하는 방법에 따라 다시 세분화된다.
스택, 큐, 덱: 항목의 접근이 맨 앞(잔단)이나 맨 뒤(후단)로 제한된다.
리스트: 가장 자유로운 선형 자료구조로 임의의 위치에 항목을 삽입하거나 삭제할 수 있다.
- 비선형(non-linear) 자료구조
종류: 트리(이진 탐색트리, AVL트리, 힙 트리), 그래프(가중치 그래프)
저장되는 항목들이 보다 복잡한 연결 관계를 가진다.
트리: 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조를 표현하기에 적합하다.
힙 트리: 우선순위 큐를 효율적으로 구현할 수 있다.
이진 탐색트리, AVL트리: 탐색을 위한 트리 구조
그래프: 지도나 인터넷 망 등 가장 복잡한 연결 관계를 표현할 수 있다.
가중치 그래프: 간선에 가중치가 포함되어 최단경로탐색과 같은 다양항 문제를 해결하기 위한 기본 구조로 사용된다.
알고리즘
대부분의 프로그램은 어떤 데이터를 처리하고 그 결과를 제공하는데, 이때 데이터는 자료구조를 이용해서 표현되고, 이를 이용해 주어진 문제를 처리하기 위한 효과적인 절차가 필요하다. 이와 같이 어떤 문제를 해결하는 절차를 알고리즘(algorithm)이라고 한다.
주어진 문제를 논리적으로 해결하기 위해 필요한 절차나 방법, 명령어들을 모아놓은 것
특히 컴퓨터에서는 알고리즘을 특정한 일을 수행하는 명령어들의 집합으로 볼 수 있다.+ 결국 프로그램은 자료구조와 알고리즘으로 구성되어 있다고 볼 수 있다.
자료구조와 알고리즘
더 좋은 알고리즘을 사용하기 위해서는 대부분의 경우 더 복잡한 자료구조를 사용해야 한다.__
*위의 문장에 공감했던 게 다익스트라를 구현할 때, 시간복잡도를 줄이기 위해서 for loop로 가장 작은 값을 찾는 대신 최소 힙 트리를 사용했다. heapq 모듈을 사용해서 heappush, heappop하면 되었기 때문에 매우 쉬웠지만, 최소 힙에 대해서는 다시 공부해야했다.
빅오 표기법
시간 복잡도 함수에서 불필요한 정보를 제거하고 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다.
빅오 표기법은 입력의 개수에 따른 기본 연산의 수행 횟수를 개략적으로 나타낸 것으로 알고리즘의 성능 비교에 사용된다.정의: 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > x에 대해 |f(n)| <= c|g(n)|을 만족하는 상수 c와 x이 존재하면 f(n) = O(g(n))이다.
(어떤 수 c와 x에 대해서는 아무런 제한이 없고, 위의 부등식을 만족하는 c나 x는 무수히 많을 수 있다.)
O(1): 상수형
O(logn): 로그형
O(n): 선형
O(nlogn): 선형로그형
O(n^2): 2차형
O(n^3): 3차형
O(2^n): 지수형
O(n!): 팩토리얼형
입력 데이터에 따른 성능 차이
최선의 경우(best case)
평균적인 경우(average case)
최악의 경우(worst case)대부분의 경우 알고리즘에 최대한 불리한 입력 데이터를 사용하는 최악의 경우의 실행시간이 가장 중요하다.
(같은 알고리즘도 입력의 종류에 따라 처리시간이 크게 달라질 수 있다.)
