자료구조

자료구조는 선형과 비선형 자료구조로 나눌 수 있다.

  • 선형 자료구조: 배열, 큐, 연결 리스트(이중/원형), 해시 테이블(선형/체이닝/딕셔너리), 스택, 데크

  • 비선형 자료구조: 그래프(BFS/DFS), 트리(이진/이진탐색), 힙, 트라이


알고리즘

1. 알고리즘 복잡도 (시간 복잡도)

입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법

algorithm

3가지 점근적 표현법

  • O (빅오): 최악의 상황을 고려하여 성능 측정 결과 표현
  • Θ (세타): 평균적인 경우에서의 성능 측정 결과 표현
  • Ω (오메가): 최선의 상황일 때의 성능 측정 결과 표현

2. 경우의 수 (순열과 조합)

어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현


일상생활에서의 경우의 수

  • 주사위: 던지는 결과, 1~6 사이의 숫자이므로 경우의 수는 6
  • 윷: 던지는 결과, 도, 개, 걸, 윷, 모 이므로 경우의 수는 5
  • 가위바위보: 게임 결과, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 3
  • 동전: 던지는 결과, 앞면 혹은 뒷면이므로 경우의 수는 2

완전 탐색으로 경우의 수를 푸는 알고리즘

  • 순열: 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관있게 나열하는 경우의 수 (nPr)
  • 조합: 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관없이 나열하는 경우의 수 (nCr)
  • 중복 순열: 서로 다른 n개의 원소 중에서 r개를 중복 있게 골라 순서에 상관없이 나열하는 경우의수 (nH)

3. 점화식(재귀식)

점화식(재귀식)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타내는 관계식이다.

recurrence relation

대표적인 점화식

  • 등차 수열: 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)

Copy