자료구조
자료구조는 선형과 비선형 자료구조로 나눌 수 있다.
- 선형 자료구조: 배열, 큐, 연결 리스트(이중/원형), 해시 테이블(선형/체이닝/딕셔너리), 스택, 데크
- 비선형 자료구조: 그래프(BFS/DFS), 트리(이진/이진탐색), 힙, 트라이
알고리즘
1. 알고리즘 복잡도 (시간 복잡도)
입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법
3가지 점근적 표현법
- O (빅오): 최악의 상황을 고려하여 성능 측정 결과 표현
- Θ (세타): 평균적인 경우에서의 성능 측정 결과 표현
- Ω (오메가): 최선의 상황일 때의 성능 측정 결과 표현
경우의 수 (순열과 조합)
어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현
일상생활에서의 경우의 수
- 주사위: 던지는 결과, 1~6 사이의 숫자이므로 경우의 수는 6
- 윷: 던지는 결과, 도, 개, 걸, 윷, 모 이므로 경우의 수는 5
- 가위바위보: 게임 결과, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 3
- 동전: 던지는 결과, 앞면 혹은 뒷면이므로 경우의 수는 2
완전 탐색으로 경우의 수를 푸는 알고리즘
- 순열: 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관있게 나열하는 경우의 수 (nPr)
- 조합: 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관없이 나열하는 경우의 수 (nCr)
- 중복 순열: 서로 다른 n개의 원소 중에서 r개를 중복 있게 골라 순서에 상관없이 나열하는 경우의수 (nH)
3. 점화식(재귀식)
점화식(재귀식)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타내는 관계식이다.
대표적인 점화식
- 등차 수열:
F(n) = F(n-1) + a*a: 고정된 상수 - 등비 수열:
F(n) = F(n-1) * a - 팩토리얼:
F(n) = F(n-1) * n - 피보나치 수열:
F(n) = F(n-1) + F(n-2)
개발자