[SW Intermediate] List 1 - Brute force, Greedy

List 1 - Brute force, Greedy, 순열, Sort(정렬)

• 강의 정리(필요하다고 생각되어지는 부분)
• 문제풀이 정리

---

Exhaustive Search

문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열하고 확인하는 기법을 의미한다.

→ Brute-force 혹은 Generate-and-Test 기법이라고도 부른다.

→ 모든 경우의 수를 테스트 한 후 최종 해법을 도출 하므로 수행 속도는 느릴 수 있어도 해답을 찾아내지 못할 확률이 적다. 

→ 주어진 문제를 풀 때, 우선 완전 탐색으로 해답을 도출한 후 성능 개선을 위하여 다른 알고리즘을 사용하여 해답을 확인하는 것이 이상적인 접근 방법이다. 

 

예시 문) Baby Gin 

6개의 숫자를 입력 받아 선택된 3개의 숫자가 연속된 숫자(run) 혹은 같은 숫자(triplet)가 될 수 있는지 즉, run 과 triplet 이 존재하는 숫자 집합인지를 판단한다. 

 

Brute-force 접근 방법)

1) 고려할 수 있는 모든 경우의 수를 생성한다. (완전 탐색)

→ 6개의 숫자로 만들 수 있는 모든 숫자를 나열한다.(중복포함)

2) 해답 테스트

→ 최종적으로 Baby Gin 여부를 판단한다. 

 

---

순열

서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것을 순열이라 한다.

 

1) 서로 다른 n개 중 r개를 선택하는 순열(nPr)

→ nPr = n*(n-1)*(n-2)*...(n-r+1)

 

2) nPn = n! (Factorial)

→ n! = n * (n-1) * (n-2) * .....2*1

 

---

Greedy Algorithm

최적 해를 구하는데 사용하는 근시안적인 방법을 의미한다.

 

• 여러 경우 중 하나를 결정해야할 때마다 그 순간에 최적이라고 생각되는 방법을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다. 
• 일반적으로 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 적인 접근이 된다.
• 탐욕 알고리즘 접근 법의 경우 해답을 찾아내지 못하는 경우도 존재한다.

 

[ 수행과정 ]

 

1) 해 선택:

현재 상태에서 부분 문제의 최적해를 구한 뒤 해 집합(Solution set)에 추가한다.

* 부분 문제의 최적해를 부분 해 집합이라고 한다.

 

2) 실행 가능성 검사:

새로운 부분 해 집합이 실행가능한지를 확인한다. 즉 제약  조건을 위반하지는 않는지를 검사한다.

 

3) 해 검사:

새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 시작한다.

 

예시 문) 거스름 돈 줄이기

어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까 ?

 

Greedy 접근 방법)

1) 해 선택:

→ 가장 좋은 해를 선택한다.

→ 가장 단위가 큰 동전을 하나 골라 거스름 돈에 추가한다.

 

2) 실행 가능성 검사:

→ 거스름 돈이 손님에게 내드려야 할 액수를 초과하는지를 확인한다.

→ 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고 , 해 선택으로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다.

 

3) 해 검사:

→ 거스름돈이 손님에게 내드려야 하는 액수와 일치하는지 확인한다.

→ 액수가 모자라면 다시 해 선택으로 돌아가서 거스름돈에 추가할 동전을 고른다.

 

---

Sort(정렬)

* 키(Key): 자료를 정렬하는 기준이 되는 특정 값을 의미한다.

 

버블 정렬(Bubble Sort): 

인접한 두 개의 원소를 비교하며 자리를 계속 교환해 나가는 방식이다. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬되게 된다.

 

[ 정렬 과정 ]

1) 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.

2)  한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다.

3) 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블 정렬 이라고 한다.

 

[ 시간 복잡도 ]

✔  O(n^2)

 

카운팅 정렬(Counting Sort):

항목들의 순서를 결정하기 위하여 집합에 각 항목들이 몇 개씩 있는지 세는 작업을 하여 선형시간에 정렬하는 효율적인 알고리즘이다.

 

[ 정렬 과정 ]

1) 정수나 정수로 표현할 수 있는 자료에 대해서만 적용이 가능한 알고리즘이다. 각 항목의 발생 횟수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 리스트를 사용하기 때문이다. 

2) 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

 

[ 시간 복잡도 ]

✔ O(n+k): n은 리스트의 개수, k는 정수의 최대 값

 

 

* 카운팅 정렬 참고

 

[알고리즘] 계수 정렬(Counting Sort)

 

 

---

문1) - min max

# n개의 양의 정소에서 가장 큰 수와 가장 작은 수의 차이를 출력하라

T = int(input())

for test_case in range(1, T + 1):
    n = int(input())
    a_list = list(map(int, input().split()))
    print(f'#{test_case} '+ str((max(a_list)-min(a_list))))

 

문2) 전기 버스

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    '''
    K : 한 번 충전으로 최대 이동 횟수
    N : 종점
    M : 충전기 설치된 정류장 수
    '''
    k, n, m = map(int, input().split())
    gas_stations = list(map(int, input().split()))
    bus_stations = [0 for _ in range(n+1)]

    for i in gas_stations:
        bus_stations[i] = 1

    # bus_stations = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
    cnt = 0
    curr_loc = 0
    k_loc = curr_loc + k

    while k_loc < n:
        if k_loc == curr_loc:
            cnt = 0
            break
        if bus_stations[k_loc] == 1:
            cnt += 1
            curr_loc = k_loc
            k_loc = curr_loc + k
            continue
        if not bus_stations[k_loc]:
            k_loc -= 1
            continue
            
    print(f'#{test_case} {cnt}')

 

* 풀이:

최소 충전 횟수를 만들어야 하므로 한번에 갈 수 있는 K 만큼의 정류장까지 간다고 가정하였을 때 충전소가 존재하는지 여부를 판단. K 만큼의 정류장 안에만 충전소가 있으면 되므로 K = K-1 을 하며 충전소 존재여부를 판단. 존재하는 경우 충전 횟수에 1을 더해주고 현재 위치를 업데이트 해준다. 

 

문3) 숫자 카드

from collections import defaultdict

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    n = int(input())
    card_list = input()
    int_dict = defaultdict(int)

    for card_num in card_list:
        int_dict[card_num] += 1

    max_count = max(int_dict.values())
    num = [k for k, v in int_dict.items() if v == max_count]
    print(f'#{test_case} {max(num)} {max_count}')

* 풀이:

입력 된 숫자카드들 중 가장 많이 발생 된 숫자와 그 개수를 출력하는 문제이다. DefaultDict(int)를 이용하여 카드 정수를 key 값으로 발생 횟수를 Value 값으로 하여 문제를 풀이했다. 같은 발생 횟수를 가지는 경우 가장 큰 정수 값을 출력해야 하므로 max(num) 로 출력했다.

 

문4) 구간 합

T = int(input())
for test_case in range(1, T + 1):
    n,m = map(int, input().split())
    num_list = list(map(int, input().split()))
    st = 0
    res_list = []

    while st+m<n+1:
        res_list.append(sum(num_list[st:st+m]))
        st += 1
    print(f'#{test_case} {max(res_list)-min(res_list)}')

* 풀이:

카드리스트에서 연속 되는 m개의 숫자들을 뽑았을 때 가장 합이 큰 값과 가장 합이 작은 값을 뺀 값을 출력하는 문제이다. 시퀀스 자료 형이므로 슬라이싱을 이용하여 문제를 풀이하였다.