[TIL]230327 - 알고리즘 4주차: Decrease and Conquer

Jimin·2023년 3월 29일
0
post-thumbnail

목차

  • 기본 아이디어
  • 상수만큼 감소(일반적으로 한 개)
    • 삽입 정렬, 그래프 탐색
    • 순열, 부분집합
  • 상수 계수만큼 감소
    • 가짜 동전 문제, 루세 곱셈
  • 가변 크기만큼 감소
  • 결론

기본 아이디어

  • 문제 인스턴스를 동일한 문제의 소규모 인스턴스로 축소하고 솔루션 확장
  • 관계를 이용하는 것
  • 문제의 주어진 예에 대한 해결책과 그 작은 예에 대한 해결책
  • 작은 인스턴스를 해결한 다음 작은 인스턴스 솔루션을 확장해 원래 문제에 대한 솔루션을 얻음
  • 하향식 또는 상향식 관계를 활용할 수 있음
  • 하향식 읽기를 통해 자연스럽게 재귀적으로 구현이 가능
  • 상향식은 일반적으로 반복적인 구현 사용 (증분적 접근법)

감소 및 정복의 3가지 주요 변형

  1. 하나씩 감소:
  • 삽입 정렬
  • 그래프 검색 알고리즘: DFS 및 BFS
  • 위상 정렬
  • 순열, 부분 집합 생성 알고리즘

  1. 상수 계수만큼 감소
  • 이진 검색
  • 가짜 동전 문제
  • 곱셈알루스
  • 요세푸스 문제
  1. 가변 크기 감소
  • 유클리드 알고리즘
  • 파티션별 선택

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)
    • 방향이 지정되어 있을 수도 없을 수도 있음
    • 알고리즘을 표현하는 두 가지 일반적인 방법
    1. 인접 목록 (Adjacency lists)
    2. 인접 행렬 (Adjacency matrix)
  • 알고리즘의 실행시간을 표현하는 것은 종종 |V|와 |E| 모든 측면에서 함
  • 점근 표기법에서만 사용함
    • 카디널리티(집합의 크기)를 포기할 것임
    • ex) O(V+E)

Adjacency lists

  • |V| 목록의 배열 조정(정점당 하나씩).
  • 꼭짓점 u의 목록은 (u, v) ∈ E와 같은 모든 꼭짓점 v를 가짐
  • 방향 그래프와 방향 없는 그래프 모두에서 작동함
  • ex) 방향이 없는 그래프의 경우:
  • 가장자리에 가중치가 있는 경우 목록에 가중치를 넣을 수 있음

  • ex) Directed Graph

Adjacency matrix

  • 가중 그래프의 비트 대신 가중치를 저장할 수 있음

  • DFS & BFS
  • DFS 및 BFS의 복잡성: Θ(V^ 2)
  • 인접 테이블로 표시되는 경우, 인접 목록으로 표시되는 경우: Θ(|V| + |E|)
  • AI 문제 및 그래프 문제의 다양한 응용 프로그램
    • ex) 주기 찾기, 관절 지점'

0개의 댓글

관련 채용 정보