[Section 2] Algorithm

Kim·2022년 9월 27일

Algorithms

Boot Camp

목록 보기

22/64

Greedy Algorithm

탐욕 알고리즘은 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종 해답에 도달하는 방법이다. 탐욕 알고리즘으로 문제를 해결하는 방법은 아래와 같이 단계적으로 구분할 수 있다.

선택 절차 : 현재 상태에서의 최적의 해답을 선택
적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

간단한 예시를 들어보자.

지금 사탕을 받으면 1개를 받을 수 있지만, 밤까지 기다리면 3개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하므로 지금 사탕 1개를 받는다는 선택을 한다.
하지만 전체적으로 봤을 때, 밤까지 기다려 3개를 받는 선택이 최적의 선택이 된다.

따라서, 두 조건을 만족하는 특정한 상황이 아니면, 탐욕 알고리즘은 최적의 해답을 보장하지 못한다. 텀욕 알고리즘을 적용하려면 해결하려는 문제가 아래의 2가지 조건을 만족해야 한다.

탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다는 장점이 있다.

Implementation - Simulation

구현 (Implementation)

알고리즘 문제를 푼다는 것은 "내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환" 하여 코드로 구현한다는 것과 같다. 수많은 문제 해결 과정은 대부분 여러 개의 카테고리로 묶여진다.

데이터를 정렬할 수 있는가?
데이터를 효율적을 탐색할 수 있는가?
데이터를 조합할 수 있는가?
etc ...

이와 같이 카테고리를 분류해도 생각한 로직을 코드로 구현한다는 것은 공통적인 속성이다. 이런 문제 해결을 코드로 풀어낼 때, 정확하고 빠를 수록 구현 능력이 좋다고 한다.

선택한 프로그래밍 언어의 문법을 정확히 알고, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제 혹은 구현 유형이라 통칭할 수 있다.

시뮬레이션 (Simulation)

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 것이다.

메신저로 대화를 할 때 조건을 붙이기로 했다.

* 캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분한다.
* 소속은 'true', 'false', 'null' 중 하나다.
* 소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꾼다.
* 아이디와 닉네임은, 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더한다.
* 캐릭터와 대화 내용을 구분할 땐 공백:공백으로 구분합니다: 'Blue', 'Green', 'null' : hello.
* 띄어쓰기를 기준으로 문자열을 반전한다. : 'abc' -> 'cba'
* 띄어쓰기를 기준으로 소문자와 대문자를 반전한다. : 'Abc' -> 'aBC'

1. "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'" 입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱을 하고, 파싱한 문자열을 상대로 캐릭터와 대화를 구분한다.

첫 번째 파싱은 공백을 기준으로 ['Blue', 'Green', 'null'] : 'hello. im G.', ['Black', 'red', 'true']: '? what? who are you?' 두 부분으로 나눈다.

두 번째 파싱은 : 을 기준으로 ['Blue', 'Green', 'null'] 배열과 'hello. im G.' 문자열로 나눈다.

2. 배열과 문자열을 사용해, 조건에 맞게 변형한다.
소속이 셋 중 하나인지를 판별한다.

"hello. im G." 띄어쓰기를 기준으로 문자열을 반전한다: ".olleh mi .G"
".olleh mi .G" 소문자와 대문자를 반전한다: ".OLLEH MI .g"

3. 변형한 배열과 문자열을 키와 값으로 받아 Map에 넣는다.
{ "[1, 2, 'null']": '.OLLEH MI .g' }

Brute-Force Algorithm (완전 탐색 알고리즘)

완전 탐색 알고리즘은 무차별 대입 방법을 나타내는 알고리즘이다. 순수 컴퓨팅 성능에 의존해 모든 가능성을 시도해 문제를 해결한다.
공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법이다.

프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 경우나, 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 경우 BFA룰 사용한다.

'hello'란 문자열을 찾아야 한다고 가정해보자.
사전과 같이 모든 단어가 정렬돼 있다면 이진 탐색 알고리즘을 통해 절반씩 범위를 줄여가며 찾을 수 있다. 하지만, 문서는 사전처럼 정렬되어 있지 않다. 'hello'에 도달하려면 각 단어를 반복해 비교해야 하므로 시간 복잡도는 O(n)과 같다.

BFA는 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법이지만, 데이터의 범위가 커질 수록 비효율적이므로 더 효율적인 알고리즘을 사용해야 한다.