20220207 APS 기본

순열(Permutation)

• 선택한 결정의 순서가 의미 있는 경우
  • nPr = n * (n-1) * (n-2) * ... * (n-r+1)

조합

• 순서가 필요없고 선택한 결정만 중요한 경우
  • $nCr = {n!\over (n-r)! r!}$
  • nCr = n-1Cr-1 + n-1Cr → 재귀적 표현
  • nC0 = 1

부분집합

순열과 조합을 이용하여 전체 집합에 대한 부분을 찾는 것

스택

• 스택의 특성 : 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 스택에 저장된 자료는 선형구조
  • 선형구조 : 자료 간의 관계가 1:1의 관계
  • 비선형구조 : 가료 간의 관계가 1:N의 관계(ex : tree)
• 후입선출구조(LIFO)
  • top : 저장된 원소 중 마지막 원소
• 주요 연산
  • push : 삽입
  • pop : 자료 삭제
  • peek : top의 원소 반환

큐

• 큐의 특성 : 뒤에서는 삽입만 하고, 앞에서는 삭제만 이루어지는 구조
• 선입설출구조(FIFO)
• 주요 연산
  • enQueue : 삽입
  • deQueue : 삭제