[SUAPC 대비] 알고리즘 정리

화질이 깨지니 아래 pdf로 보길 추천
알고리즘 정리본

1. 자료구조

01. 배열과 리스트

• 배열 : 메모리의 연속 공간에 값이 채워져 있는 형태의 자료ㄱ조
  중간 인덱스의 값을 수정하기엔 어려움

*파이썬에서는 배열과 리스트를 구분X

02. 구간 합

• 합 배열 S는 다음과 같이 정의한다.
  S[i] = A[0]+A[1]+...+A[I]

• 합 배열 S를 만드는 공식2
  S[i] = S[i-1] + A[i]

• 구간합을 구하는 공식
  S[i] = A[0]+A[1]+...+A[I]

구간합 백준 문제
11659 11660

03. 투 포인터

• 2개의 포인터를 이용해 알고리즘 시간 복잡도를 최적화
  start_index & end_index

투 포인터 백준 문제
2018 1940 1253

04. 슬라이딩 윈도우

• 2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 슬라이딩하며 문제를 해결

슬라이딩 윈도우 백준 문제
12891 11003

05. 스택과 큐

• 스택
  후입선출로 이뤄지는 자료 구조
  DFS에서 사용
  .append() .pop()

• 17298 정리 velog

• 큐
  선입선출로 이뤄지는 자료구조
  .append() .popleft()

from collections import deque

que = deque()

• Priority Que
  골드 문제에서 자주 사용되는 자료구조
  힙 트리를 이용해 우선순위에 따라 정렬
  시간복잡도 O(nlogn)

스택 & 큐 백준 문제
1874 17298 2164 11286

2. 정렬

01. 버블 정렬

• 2개의 수끼리 비교해 크기 순서대로 swap 실행
  O(n^2)

버블 정렬 백준 문제
2750 1377

02. 선택 정렬

• 해당 범위의 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap
  O(n^2)

선택 정렬 백준 문제
1427

03. 삽입 정렬

• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬
  O(n^2)

삽입 정렬 백준 문제
11399

04. 퀵 정렬

• 퀵정렬은 기준값을 선정해 해당값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘
  O(nlogn)

퀵 정렬 백준 문제
11004

05. 병합 정렬

• 병합정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
  O(nlogn)

병합 정렬 백준 문제
2751 1517

06. 기수 정렬

• 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교
  O(kn) (k는 데이터 자릿수)

병합 정렬 백준 문제
10989

3. 탐색

01. DFS

• 그래프 완전 탐색 기법 중 하나
• 그래프의 시작 노드에서 출발하여 한 쪽 분기를 정하여 최대 깊이 까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색 수행
• 재귀함수 (BFS 사용 추천하는 이유)
  sys.setrecrusionlimit(depth)
• 11724 정리 velog

DFS 백준 문제
11724 2023 13023

02. BFS

• 그래프를 완전 탐색 기법 중 하나
• 시작 노드에서 출발해 시작노드를 기준으로 가까운 노드를 번저 방문하면서 탐색하는 알고리즘
• 1260 정리 velog

BFS 백준 문제
1260 2178 1167

03. 이진 탐색

• 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이며 대상 찾기

이진 탐색 백준 문제
1920 2343 1300

4. 그리디

01. 그리디 알고리즘

• 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지 중 최선의 선택지라고 가정하는 알고리즘
• 따라서 항상 최적의 해를 보장하지는 않는다.

그리디 알고리즘 백준 문제
11407 1715 1744 1931 1541

5. 그래프

01. 그래프 표현

그래프 구현 방법

• 에지 리스트
  [출발노드, 도착 노드1]
[출발노드, 도착 노드1, 가중치]

• 인접 행렬
  도착노드는 열, 출발노드는 행으로 설정해 2차원 행렬에 입력

• 인접리스트 추천
  [출발노드] - [도착 노드1, 도착노드2 ...]
[출발노드] - [(도착 노드1, 가중치1), (도착노드2, 가중치2)...]

• 18352 velog 정리

그래프 표현 백준 문제
18352 1325 1707 2251

02. 유니온 파인드

• 특정 2개의 노드를 연결해 1개의 집합으로 묵는 union 연산과 두 노드가 같은 집합에 속해있는지를 확인하는 find 연산
• 1717 velog 정리
• 1976 velog 정리
• 1043 velog 정리

유니온 파인드 백준 문제
1717 1976 1043

03. 위상 정렬

• 사이클이 없는 그래프에서 노드 순서를 찾는 알고리즘
• 위상정렬에서는 항상 유일한 값으로 정렬되지 않는다
• 2252 velog 정리
• 1516 velog 정리
• 1948 velog 정리

위상 정렬 백준 문제
2252 1516 1948

04. 다익스트라

• 그래프에서 최단 거리를 구하는 알고리즘
• 1753 velog 정리
• 1916 velog 정리

다익스트라 백준 문제
1753 1916 1854

05. 벨만-포드

• 최단 거리를 구하는 알고리즘
• 에지리스트로 그래프를 구현하고 모든 에지를 확인해 정답리스트 업데이트
• 음수사이클 유무 확인(음수 사이클 있을 경우 수행 불가)
• 11657 velog 정리
• 1219 velog 정리

벨만-포드 백준 문제
11657 1219

04. 플로이드-워셜

• 알고리즘 그래프에서 최단거리 구하는 알고리즘
• 음수 가중치 에지가 있어도 수행 가능
• 11404 velog 정리
• 11403 velog 정리
• 1389 velog 정리

플로이드-워셜 백준 문제
11404 11403 1389

04. 최소 신장 트리

• 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
• 유니온 파인드 이용
• N개의 노드가 있으면 최소 신장트리 구성하는 에지개수는 N-1개
• 1197 velog 정리
• 17472 velog 정리
• 1414 velog 정리

최소 신장 트리 백준 문제
1197 17472 1414

6. 트리

01. 트리 알아보기

• 트리는 노드와 에지로 연결된 그래프의 특수 형태 (트리는 그래프 종류 중 하나)
• 사이클이 없고 1개의 루트노드가 존재
• 각 노드는 1개의 부모 노드를 가진다.

coding test - tree 영역 유형
🅰 그래프로 푸는 tree : Node Edge
=> 인접리스트로 표현 -> DFS, BFS
🅱 tree만을 위한 문제 (인접리스트로 표현 불가)
=> 이진트리 & 세그먼트 트리 & LCA 트리

• 11725 velog 정리
• 1068 velog 정리

트리 알아보기 백준 문제
11725 1068

02. 트라이

• 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료 구조
• O(M)으로 문자열을 검색한다. (가장 길이가 긴 string의 길이 M만큼만 검색)
• 14425 velog 정리

03. 이진 트리

• 각 노드의 자식노드 개수가 2개 이하로 구성돼 있는 트리
• 부모노드 index = index / 2
• 왼쪽 자식 노드 index = index * 2
• 오른쪽 자식 노드 index = index * 2 + 1
• 1991 velog 정리

이진 트리 백준 문제
1991

04. 세그먼트 트리

• 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 구안해낸 자료구조 형태
• 2^(k) >= N 만족하는 k의 최솟값구하기
• 2^(k)를 시작인덱스로 설정하기
• 2042 velog 정리
• 10868 velog 정리
• 11505 velog 정리

세그먼트 트리 백준 문제
2042 10868 11505

05. 최소 공통 조상

• 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 처음 공통으로 만나게 되는 부모노드를 최소공통조상이라 한다.
• P[K][N] N번 노드의 2^(k)번째 부모의 노드 번호
• 부모노드 리스트 점화식
  P[K][N] = P[K-1][P[K-1][N]]
• 11437 velog 정리

최소 공통 조상 백준 문제
11437 11438

7. 동적 계획법

01. 동적 계획법

• 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법
• 그냥 점화식 잘 세워야 되는 문제
• 작은 문제들은 한번만 계산해 DP 테이블에 저장해 추후 재사용할 때는 이 DP 테이블을 이용
• 1463 velog 정리

동적 계획법 백준 문제
많아서 생략, 아래 링크 참조
동적계획법