카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

완전탐색이란?

문제를 해결하기 위해 모든 선택지를 조사하여 정답을 찾는 방법

단순 Brute Force

단순하게 반복, 조건문으로 모든 경우를 탐색하여 정답 도출

비트마스크 (Bitmask)

나올 수 있는 모든 경우의 수가 각각 원소가 포함되거나 포함되지 않느느 두 가지 선택으로 구성되는 경우 사용

ex. 원소가 n개인 집합의 모든 부분집합을 구하는 문제

각 원소가 포함되는지, 포함되지 않는지 0, 1로 구분하여 배열에 저장 가능

재귀함수

비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용하게 사용

포함이 된다면 해당 원소를 넣어 함수 호출, 아니라면 그 상태에서의 함수 호출

ex. 피보나치 수열 등

순열

서로 다른 N개를 일렬로 나열하는 방법 (경우의 수)

N!로 완전 탐색을 이용하기 위해서 N이 한자리 수는 되어야 함

순열에 원소를 하나씩 채워가는 방식

재귀함수 이용

BFS, DFS

너비 우선 탐색과 깊이 우선 탐색

순차적으로 노드를 방문하여 모든 노드를 탐색

과정

1. 해결하고자 하는 문제의 가능한 경우의 수 계산

2. 가능한 모든 방법 고려

3. 실제 답을 구할 수 있는지 적용

!! 완전 탐색의 경우, 사용할 수 있는 알고리즘과 그에 따른 예시가 너무 다양하기 때문에 별도로 정리 !!

그리디 알고리즘이란?

선택의 순간마다 선택한 최적해가 결국 전체의 최적해

순간순간의 선택은 그 순간에 대해서는 최적이지만, 전체의 최적이라는 보장이 없기 때문에 한정된 사용

과정

1. 선택 절차 (Selection Procedure)

현재 상태에서의 최적해를 선택

2. 적절성 검사 (Feasibility Check)

선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사 (Solution Check)

문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가 반복

조건

탐욕적 선택 속성 (Greedy Choice Property)

이전의 선택이 이후의 선택에 영향을 주지 않음

최적 부분 구조 (Optimal Substructure)

문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

위 두가지 조건이 만족하지 못한다면, 그리디 알고리즘은 최적해를 구하지 못함

특별한 구조가 있는 문제에 대해서는 그리디 알고리즘이 언제나 최적해 탐색 가능

(ex. 매트로이드)

예시

매트로이드

가장 널리 드는 예시

특정 가격의 물건을 구입하는데 가장 적은 동전을 사용하고, 각 동전의 사용 개수를 구하는 문제

4650원 짜리 물건을 구매하는 상황에서

500원 9개

100원 1개

50원 1개

이렇게 사용하는 것이 가장 적은 양의 동전을 사용하는 방법

그리디 알고리즘을 위 문제의 해결에 적용

1. 선택절차

동전 개수를 줄이기 위해 가장 가치가 높은 동전의 선택을 우선

2. 적절성 검사

1번 과정을 통해 선택된 동전 합이 물건의 가격을 초과하는지 검사

초과한다면, 마지막에 선택한 동전을 삭제하고 1번으로 돌아가 한 단계 작은 동전을 선택

3. 해답 검사

선택된 동전들의 합이 물건의 가격과 일치하는지 검사

부족하면 1번 과정부터 반복

위 순서대로 500원짜리 동전을 9개(4500원) 선택 후, 한 단계 낮은 100원짜리 동전을 1개 (4600원), 50원짜리 동전을 1개( 4650) 선택

결국 각 순간에 최선의 선택이 전체에서의 최선의 선택이 됨