[알고리즘] Array - 완전 검색, 탐욕 알고리즘
* Array 기본
✔️ Array(배열) 이란?
일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
✔️ 1차원 Array의 선언
. 자료형: Array을 이루는 원소(변수)의 자료형
. 이름: 프로그램에서 사용할 Array의 이름
. 길이: Array을 이루는 원소의
✔️ 1차원 Array의 접근
. 인덱스: 원소의 위치
* Exhaustive Search
완전 검색
✔️ 완전검색?
문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
✔️ 특징
① Brute-force 혹은 Generate-and-Test 기법이라고도 불린다.
② 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.
③ 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
④ 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
⑤ 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 Algorithm을 사용하고 해답을 확인하는 것이 바람직함.
✔️ Baby-gin Game
|
0~9사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때,
3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고,
3장의 카드가 동일한 번호를 갖는 경우를 triplete라고 한다.
6장의 카드가 run과 triplete로만 구성된 경우를 baby-gin으로 부른다.
|
→ 완전검색으로 해결하는 경우
① 고려할 수 있는 모든 경우의 수 생성하기 - 6개의 숫자로 만들 수 있는 모든 숫자 나열(중복 포함)
② 해답 테스트 하기 - 앞의 3자리와 뒤의 3자리를 잘라, run과 triplete 여부를 테스트하고 최종적으로 baby-gin을 판단.
✔️ 순열(nPr)
서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것.
✔️ 구현 방법 예
① for/while loop (간단한 문제)
② 재귀함수 (조금 더 복잡한 문제)
* Greedy Algorithm
탐욕 알고리즘
✔️ 탐욕 알고리즘?
최적해를 구하는 데 사용되는 근시안적인 방법. 무조건 지금 가장 가치있는 선택을 내리고 뒤돌아보지 않는 알고리즘.
✔️ 특징
① 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달함
② 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 최적이라는 보장은 없음(현재 최적해 != 전체 최적해)
③ 일반적으로, 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됨
✔️ Greedy Algorithm의 수행 과정
① 해 선택 - 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가함
② 실행 가능성 검사 - 새로운 부분 해 집합이 실행 가능한지를 확인. 곧, 문제의 제약 조건을 위반하지 않는지를 검사함
③ 해 검사 - 새로운 부분 해 집합이 문제의 해가 되는지를 확인. 아직 전체 문제의 해가 완성되지 않았다면, 1의 해 선택부터 다시 시작
✔️ 거스름돈 줄이기
어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?
① 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가함
② 거스름돈이 손님에게 내드려야 할 액수를 초과하는지를 확인
. 만약 초과한다면, 마지막에 추가한 동전을 거스름돈에서 빼고, 1로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가함
③ 거스름돈이 손님에게 내드려야 하는 액수와 일치하는지 확인.
. 액수가 모자란다면 다시 1로 돌아가서 거스름돈에 추가할 동전을 고른다.
→ 관련 문제: 동전 0(백준 11047)
✔️ Baby-gin 다시 풀기
① 6개의 숫자는 6자리의 정수 값으로 입력됨
② COUNTS Array의 각 원소를 체크하여, run과 triplete 및 Baby-gin여부를 판단함
. COUNTS Array에서 run과 triplete 중에 가능한 것을 조사함
. 조사에 사용한 한데이터는 삭제함
. 남은 데이터를 다시 run과 triplete중에 가능한지를 조사
✔️ 코딩테스트에 활용할 수 있는 경우?
① 현재의 선택이 미래 선택에 영향을 주지 않을 때 - 탐욕스런 선택 조건(Greedy Choice Property)
② 부분의 최적 해가 모이면 전체의 최적 해가 된다 - 최적 부분 구조 조건(Optimal Substructure)
✔️ Greedy 전략
. 핵심은 정렬!
. 어떻게 정렬해야 미래를 생각하지 않고 현재만 보고도 최적을 구할 수 있을 것인가
✔️ 관련 문제: 회의실 배정 (백준 1931)
하나의 회의실을 사용하고자 하는 N개의 사용 요청을 입력받는다. 각 요청은 회의 시작 시간과 종료 시간 정보를 제공하는데, 겹치지 않는 회의를 최대한 많이 진행한다면, 몇개 까지 진행할 수 있는지?
→ 가장 빨리 끝나는 회의부터 먼저 진행해야, 가장 많은 회의를 진행할 수 있다.
→ 입력받은 정보들을 종료시간을 기준으로 오름차순으로 정렬하고, 제일 처음부터 진행 가능한 회의부터 하나씩 진행
→ 진행 가능한 회의들을 또 진행하며 반복
(+) 현실세계에서는, 완벽한 정답이 아닌 근사치 정도만 나와도 만족스러운 경우에 성능을 개선하기 위해 사용.
✔️추천문제
