알고리즘 9강 :: 알고리즘 목차, 분할정복, 동적프로그래밍, 욕심쟁이

알고리즘 9강을 보며 배운내용

 

 

이번 강의는

10강부터 배울 정렬 알고리즘에 들어가기전에

1강부터 8강까지 배운 내용 리마인드 시간

 

 

정리(TL;DR)

1. 기본 자료구조
=> 모든 구현은 배열과 연결리스트
2. 알고리즘 기초
=> 대표적인 3가지 알고리즘, 점근 성능

3. 분할정복
=> 이진 탐색, 퀵 정렬
4. 분할정복
=> 합병정렬, 선택 문제

5. 동적 프로그래밍
=> 동적 프로그래밍 원리, 연쇄 행렬 곱셈
6. 동적 프로그래밍
=> 편집 거리, 모든 정점 최단 경로, 저울 문제

7. 욕심쟁이
=> 동전 거스름돈, 배낭문제, 신장트리
8. 욕심쟁이
=> 한 정점 최단 경로, 데이크스트라, 작업 스케쥴링, 작업 선택, 허프만코딩

 

 

 

1강 기본 자료구조

정의, 특징, 동작 등을 알아두자

• 배열, 연결리스트
• 스택, 큐
• 트래, 그래프

 

2강 알고리즘의 기초

알고리즘은 뭘까?

• 대표적인 알고리즘
  1. 분할정복
  2. 동적 프로그래밍
  3. 욕심쟁이 방법
• 점근성능으로 시간 복잡도 표현
• 유명 기본 점화식

 

3강 분할정복 알고리즘 (1/2)

순환적으로 문제를 푸는 하향식 접근

 

이진 탐색

절반씩 줄여가며 찾는 방법

성능

• O(logn)

특징

• 정렬된 데이터에 사용
• 삽입/삭제 많이 발생하면 이진탐색 X

 

퀵 정렬
피벗을 기준으로 나누는 방법

성능

• 최악: O(n제곱) => 피벗이 최솟값이나 최댓값일 때
• 최선: O(nlogn) => 피벗이 중간 값일 때
• 평균: O(nlogn)

특징

• 피벗 선택시 랜덤하게 고르면 평균 수행시간 보장 가능!

 

4강 분할정복 알고리즘 (2/2)

합병 정렬

전형적인 분할, 정복, 결합이 적용된 정렬

성능

• O(nlogn)

특징

• n만큼 추가 저장 장소 필요

 

선택 문제

i번째 작은 원소 찾는 문제

성능

• 최악: O(n제곱) => 분할함수 이용
• 평균: O(n) => 중간값의 중간값

 

5강 동적 프로그래밍 알고리즘 (1/2)

작은 문제의 해를 저장해서 점진적으로 큰 문제의 해를 구하는 방법

• 상햑식 접근
• 최적화 문제(최솟값, 최댓값 ...)에 주로 사용
• 소문제 독립일 필요 없다

 

연쇄 행렬 곱셈

n개 행렬 연쇄적으로 곱할 때 기본 곱셈 횟수가 최소가 되는 행렬의 곱셈 순서

성능

• O(n3제곱)

 

6강 동적 프로그래밍 알고리즘 (2/2)

스트링 편집 거리

문자열 X를 Y로 변경할 때 편집 연산의 최소 비용('편집 거리'라고 한다)

성능

• O(nm)

 

모든 정점 간의 최단 경로

가중 방향 그래프에서 두 정점의 모든 조합의 최단 경로

=> 플로이드 알고리즘 이용

가정

가중치의 합이 음수의 사이클이 존재하지 않는다

성능

• O(|V|3제곱)

 

저울 문제

무게 M인 물체를 n개의 추를 이용해서

양팔 저울로 달 수 있는지 확인하는 문제

가정

추의 무게와 물체 무게 모두 정수

성능

• O(nM)

 

7강 욕심쟁이 알고리즘 (1/2)

각 단계에서 가장 최선이라고 여겨지는 해를 선택

특징

• 각 단계에서 하나의 최적해만 고려
• 전체적인 최적해 못 구할 수도 있다

 

동전 거스름돈

동전의 개수를 최소로 하는 거스름돈 찾는 방법

액면가 가장 큰 동전부터 최대한 사용

 

성능

• O(n)

특징

• 액면가 임의로 주어지면 욕심쟁이 X
• => 동적 프로그래밍 사용해야 된다

 

배낭 문제

물체의 이익의 합이 최대가 되도록 배낭에 물체 넣는 방법

가정

• 물체를 쪼개서 넣을 수 있다

성능

• 정렬 되있으면: O(n)
• 정렬 해야되면: O(nlogn)

특징

• 물체 쪼갤 수 없으면 욕심쟁이로 X
• => 무지 어려워진다 지금은 눈 돌리자

 

최소 신장 트리

가중 무방향 그래프를 트리로 만들때

간선의 가중치 함이 가장 가장 작은 트리

그래프가 트리가 되는 조건

• 무방향, 모든 정점 연결, 사이클 X

 

최소 신장 트리를 푸는 알고리즘

1. 크루스칼

서로 다른 연결 성분중 최소 가중치 간선 선택

 

2. 프림

선택된 정점, 선택되지 정점의 간선중 가중치가 최소인 간선 선택

 

8강 욕심쟁이 알고리즘 (2/2)

단일 출발점 최단 경로

 

데이크스트라 알고리즘 이용

• 하나의 정점에서 다른 모든 정점으로 최단 경로
• 내비게이션에 적용

가정

• 음의 가중치를 갖는 간선이 없다

 

 

작업 스케쥴링

최소 기계 사용 모든 작업 처리

시작 시간이 빠른 작업 우선

성능

• O(nlogn)

 

작업 선택

하나의 기계 사용 최대 작업 개수

완료 시간이 빠른 작업부터 

성능

• O(nlogn)

 

허프만 코딩

 

문자의 출현 빈도수에따라 다른 길이 부호 부여

• 통계적 압축 방법
• 접두부 코드, 최적 코드

허프만 트리 만들 때 욕심쟁이 방법 이용

성능

• O(nlogn + m)

특징

• 각 문자수 빈도수 모르면 텍스트 2번 읽어야 된다 => 속도 저하
• 디코딩 위한 정보 압축에 포함해줘야 된다 => 압축률 저하

 

허프만 트리

빈도수가 가장 작은 두 트리 합치는 과정 반복

• 완전 이진 트리
• 좌우 간선 0과 1로 레이블링
• 빈도수가 같은 트리가 여러개 있으면 허프만 트리 모양 달라진다

 

 

Organize by Kelly Sikkema #unsplash