ssonzm.log
로그인
ssonzm.log
로그인
[TIL]230327 - 알고리즘 4주차: Decrease and Conquer
Jimin
·
2023년 3월 29일
팔로우
0
TIL
알고리즘
0
목차
기본 아이디어
상수만큼 감소(일반적으로 한 개)
삽입 정렬, 그래프 탐색
순열, 부분집합
상수 계수만큼 감소
가짜 동전 문제, 루세 곱셈
가변 크기만큼 감소
결론
기본 아이디어
문제 인스턴스를 동일한 문제의 소규모 인스턴스로 축소하고 솔루션 확장
관계를 이용하는 것
문제의 주어진 예에 대한 해결책과 그 작은 예에 대한 해결책
작은 인스턴스를 해결한 다음 작은 인스턴스 솔루션을 확장해 원래 문제에 대한 솔루션을 얻음
하향식 또는 상향식 관계를 활용할 수 있음
하향식 읽기를 통해 자연스럽게 재귀적으로 구현이 가능
상향식은 일반적으로 반복적인 구현 사용 (증분적 접근법)
감소 및 정복의 3가지 주요 변형
하나씩 감소:
삽입 정렬
그래프 검색 알고리즘: DFS 및 BFS
위상 정렬
순열, 부분 집합 생성 알고리즘
상수 계수만큼 감소
이진 검색
가짜 동전 문제
곱셈알루스
요세푸스 문제
가변 크기 감소
유클리드 알고리즘
파티션별 선택
Decrease&Conquer v.s. Divide&Conquer
Decrease&Conquer
두 부분을 모두 해결할 필요는 없음
Divide&Conquer
많은 교과서는 감소와 정복 알고리즘을 분할과 정복 알고리즘 중 하나로 분류함
Decrease by One: Insertion Sort
삽입 정렬
n개 요소를 정렬하는 알고리즘:
배열의 n-1 요소 정렬
n번째 요소를 삽입함
복잡성: 최악의 경우 Θ(n^2),
평균적인 경우 Θ(n^2),
거의 정렬된 배열에서는 Θ(n).
Graph
주어진 그래프 G = (V,E)
방향이 지정되어 있을 수도 없을 수도 있음
알고리즘을 표현하는 두 가지 일반적인 방법
인접 목록 (Adjacency lists)
인접 행렬 (Adjacency matrix)
알고리즘의 실행시간을 표현하는 것은 종종 |V|와 |E| 모든 측면에서 함
점근 표기법에서만 사용함
카디널리티(집합의 크기)를 포기할 것임
ex) O(V+E)
Adjacency lists
|V| 목록의 배열 조정(정점당 하나씩).
꼭짓점 u의 목록은 (u, v) ∈ E와 같은 모든 꼭짓점 v를 가짐
방향 그래프와 방향 없는 그래프 모두에서 작동함
ex) 방향이 없는 그래프의 경우:
가장자리에 가중치가 있는 경우 목록에 가중치를 넣을 수 있음
ex) Directed Graph
Adjacency matrix
가중 그래프의 비트 대신 가중치를 저장할 수 있음
Decrease by one: Graph Search
DFS & BFS
DFS 및 BFS의 복잡성: Θ(V^ 2)
인접 테이블로 표시되는 경우, 인접 목록으로 표시되는 경우: Θ(|V| + |E|)
AI 문제 및 그래프 문제의 다양한 응용 프로그램
ex) 주기 찾기, 관절 지점'
Jimin
팔로우
이전 포스트
[TIL]230328 - 영상처리 4주차: 영상향상(2) Histogram Specification
다음 포스트
[TIL]230329 - 컴퓨터시스템보안: 4주차 고전 대칭키 암호(3)
0개의 댓글
댓글 작성
관련 채용 정보