알고리즘(1) 그리디 알고리즘

1. 자료구조와 알고리즘

최근 IT 기업의 채용과정에서 코딩테스트 비중이 커지고 있으며, 문제해결 능력을 요구하는 알고리즘 문제 풀이에 대한 관심이 증가하고 있다.

• 코딩테스트란? 기업/기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행되는 일종의 문제 풀이 시험
• 온라인 저지 사이트 : 프로그래밍 대회나 코딩 테스트에서 나올 법한 문제를 시험해 보는 온라인 시스템
  • LeetCode : 해외 사이트 중 국내 인지도가 높은 사이트
  • 백준 온라인 저지
    : 국내에서 가장 유명한 알고리즘 문제 풀이 사이트
  • 코드업 :
    국내의 한 정보 교사가 알고리즘 교육을 목적으로 운영하는 사이트
  • 프로그래머스 :
    국내 알고리즘 학습 사이트로 카카오 코딩테스트 문제를 제공
  • SW Expert Academy :
    삼성에서 공식적으로 제공하고 있는 알고리즘 학습 사이트
  • 이외에도 다양한 국내외 사이트 존재 (codeforces, topcode, codechef, 프로젝트오일러, 코딩도장 등)
• 출제 경향
  • 2~5시간 가량의 시간을 주어 여러 개의 정해진 알고리즘 문제를 풀도록 하나.
  • 출제 빈도가 높은 알고리즘 유형
    • 그리디
    • 구현
    • DFS/BFS를 활용한 탐색

---

## 2. 알고리즘 성능평가 #### (1) 복잡도(Complexity) - 복잡도는 알고리즘의 성능을 나타내는 척도 - 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 - 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘

(1)-1 빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만 고려하는 표기법
  - 함수의 상한(차수가 가장 큰 항)만 고려
  - 예) 연산횟수가
  $5N^3 + 3N^2 + 100$
  인 알고리즘의 경우 빅오표기법에서는 $O(N^3)$으로 표현됨

• 시간복잡도 계산 예제

  • N개의 데이터 합을 계산하는 프로그램
  • N의 데이터에 대하여 2중 반복문

• 연산 : 사칙연산뿐만 아니라, 비교 연산등과 같은 기본 연산을 의미
  

• N에 따른 연산획수 BigO복잡도
  

# 2중 반복문을 이용하는 예제
a = [1,2,3,4,5] #(N=5)
for i in a:
    for j in a:
        temp = i * j
        print(temp)

(2) 알고리즘 설계 Tip

• 일반적으로 CPU기반의 컴퓨터에서 연산횟수가 5억을 넘어가는 경우, Python을 기준으로 5~15초 가량의 시간이 소요됨
• 코딩테스트 문제에서 시간제한은 통상 1~5초 가량이다. 명시되지 않는 경우 5초로 생각하고 알고리즘 설계
• N의 범위에 따라 일반적인 알고리즘 설계 기준(시간제한 1초)
  - N의 범위가 500 :
  $O(N^3)$인 알고리즘 설계 가능
  - N의 범위가 2,000 : $O(N^2)$인 알고리즘 설계 가능
  - N의 범위가 100,000 : $O(NlogN)$인 알고리즘 설계 가능
  - N의 범위가 10,000,000 : $O(N)$인 알고리즘 설계 가능

(2)-2 알고리즘 문제 해결 과정

1. 지문을 읽고 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제해결을 위한 핵심 아이디어 찾기
4. 소스코드 설계 및 코딩

• 문제를 이해하고 핵심 아이디어를 캐치해서 복잡도에 기반하여 설계 후 코딩하는 것을 추천

(3) 알고리즘 문제에서 효과적으로 사용될 수 있는 파이썬 주요 문법

(3)-1 리스트 컴프리헨션

• 리스트를 생성하는데 있어 간결하게 한줄로 작성 가능

[<생성할 값> <for문> (<조건문>)]

• 2차원 리스트를 초기화할 때 효과적으로 사용 가능
  • N,M 크기의 2차원 리스트 초기화

[[0] * m for _ in range(n)]

- 반복을 수행하되, 반복을 위한 변수의 값을 무시하고자 할때 언더바(_)를 사용

(3)-2 자료형

알고리즘에서 튜플을 사용하면 좋은 경우

• 서로 다른 성질의 데이터를 묶어서 관리해야 할때 (최단 경로 알고리즘 (비용, 노드번호))
• 데이터의 나열을 해싱(Hashing)의 키 값을 사용할 때
• 리스트보다 메모리를 효율적으로 사용해야 할 때 (단, 선언된 값은 변경할 수 없다)

사전 자료형/집합 자료형

• 순서가 없기 때문에 내부적으로 해시테이블(Hash Table)을 이용
• key값을 이용하여 데이터의 조회 및 수정하므로 상수시간(O(1))에 처리할 수 있음

(3)-3 해시테이블(Hash Table)

• 키(key)와 값(value) 쌍을 저장하는 자료 구조로, 해시 함수(hash function)를 사용하여 키를 고유한 인덱스로 변환되어 저장됨
• 해시테이블의 구성요소
  • 키(key): 데이터를 고유하게 식별할 수 있는 값
  • 값(value): 키에 해당하는 실제 데이터
  • 해시 함수(hash function): 키를 입력받아 특정 인덱스를 반환하는 함수
• 해시테이블의 장단점
  • 장점
    • 키를 통한 빠른 데이터 접근으로 빠른 검색, 삽입, 삭제 연산 (평균 시간복잡도 O(1))
    • 데이터의 중복 확인이 용이함
  • 단점
    • 해시 충돌 가능성
    • 상대적으로 많은 메모리 공간 필요
    • 순서가 있는 데이터에는 적합하지 않음

(4) 알고리즘 문제에서 유용한 라이브러리

• 내장함수 : 기본 입출력 함수부터 정렬함수까지 기본적인 함수들을 제공
  • 프로그램을 작성할 때 없어서는 안되는 필수적인 기능 제공
• itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능 제공
  • 순열과 조합 라이브러리가 자주 사용됨
• heapq : 힙(Heap) 자료 구조 제공
  • 우선순위 큐 기능 구현 시 사용
• bisect : 이진탐색(Binary Search) 기능 제공
• collections : 덱(deque), 카운터(Counter) 등의 유용한 기능 제공
• math : 필수적인 수학 기능 제공
  • 팩토리얼(factorial), 제곱근(sqrt), 최대공약수(lcd), 삼각함수(sin, cos, tanh) 관련 함수부터 파이(pi)와 같은 상수 포함

(4)-1 내장함수

(4)-2 map 함수

• 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용

map(<함수>, <데이터>)

# 입력된 값을 공백을 기준으로 나누어 정수형으로 데이터 타입 변경
list(map(int, input().split()))

# lambda 함수 적용 가능
map(lambda <인자>:<연산>,<입력 인자>)

(4)-3 순열과 조합

• 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것 (나열 순서 중요)
  
  $_{n}P_{r} = \frac{n!}{(n-r)!}= n * (n-1) * (n-2)* \cdots * (n-r-1)$
  - 중복 허용 : $P_{with repeat}(n,r) = n^{r}$
• 조합 : 서로 다른 n개에서 순서와 상관없이 서로 다른 r개를 선택하는 것
  
  $_{n}C_{r} = \frac{n!}{(n-r)!r!}=\frac{n * (n-1) * (n-2)* \cdots * (n-r-1)}{r * (r-1) * \cdots * 1}$
  - 중복 허용 : $C_{with repeat}(n,r) = \frac{(n+r+1)!}{r!(n-1)!}$
  

(4)-4 counter

• 원소의 개수를 세는 기능 제공
• 리스트와 같이 반복가능한(iterable) 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지 계산
  

---

3. 그리디 알고리즘(Greedy Algorithm)

• 탐욕 알고리즘이라고도 하며, 현재 상황에서 가장 좋은 것만 고르는 방법을 의미
• 정당성 분석이 중요
  • 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요
• 루트노드부터 시작하여 노드값의 합을 최대
  • 최적의 경로 및 값은?

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 있음
• 하지만 알고리즘 문제에서의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황을 추론할 수 있어야 해결 가능

(1) 거스름돈

• 문제설명
  당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일때 거슬러 주어야 할 동전의 최소 개수를 구하세요.

• 입력조건 : 거슬러주어야 할 돈 N(10≤N)의 자연수가 주어지며, 항상 10의 배수 (예시: 1260)

• 출력조건 : 거슬러주어야 할 동전의 최소개수를 출력합니다. (예시: 6)

• 문제해결 아이디어 : 가장 큰 화폐단위부터 돈을 거슬러 준다.

• 정당성 분석 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음

# 거스름돈
n = 1260
count = 0

# 큰화폐단위로 정렬
coin_types = [500, 100, 50, 10]

for c in coin_types:
    count += n // c
    n %= c

print(count)

6

• 화폐의 종류가 K라고 할때, 소스코드의 복잡도는 $O(K)$
• 해당 알고리즘은 거슬러줘야하는 금액(N)과는 무관하며, 동전의 종류의 수(K)에만 영향을 받음

(2) 1이 될 때까지

• 문제 설명
  어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다. N과 K가 주어질 때 N이 1이 될때까지 1번 혹은 2번 과정을 수행해야 하는 최소 횟수를 구하세요.
  1. N에서 1을 뺍니다.
  2. N을 K로 나눕니다.

• 입력조건 : N(1≤N≤100,000)과 K(2≤K≤100,000)가 공백을 기준으로 하여 각각 자연수로 주어집니다. (예시: 25 5)

• 출력조건: N이 1이 될때까지 1번 혹은 2번 과정을 수행해야 하는 최소 횟수를 출력합니다. (예시: 2)

• 문제해결 아이디어

  • 주어진 N에 대하여 최대한 많이 나누기를 수행한다.
  • N의 값을 줄일 때, 나누는 작업이 1을 빼는 작업보다 횟수를 많이 줄일 수 있다.

• 정당성 분석

  • K가 2이상이라면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음
  • N은 항상 1에 도달하게 됨 (최적의 해 성립)

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k #target은 k의 배수
    result += (n - target) #해당 배수가 될때까지 1씩 빼기
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기(K로 나누는 과정의 횟수 추가, 몫을 N으로 변경)
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기 (1이 되어야 하므로 n-1만큼 반복)
result += (n - 1)
print(result)

25 5
2

(3) 곱하기 혹은 더하기

• 문제설명
  각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 문자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰수를 구하세요. (단, +보다 x를 먼저 계산하는 일반적인 방식과 달리, 모든 연산은 왼쪽부터 순서대로 이루어진다고 가정합니다.)

• 입력조건: 각 자리가 숫자로만 이루어진 문자열 S(1≤S의 길이≤20)가 주어집니다. 또한 만들어진 가장 큰수가 20억 이하의 정수가 되도록 입력이 주어집니다. (예시: 02984)

• 출력조건: 곱하기 또는 더하기 연산으로 만들수 있는 가장 큰수를 출력합니다. (예시: 576)

• 문제해결 아이디어

  • 대부분, 곱하기가 더 큰 값은 만든다.
  • 두 수 중 하나라도 0또는 1이라면, 더하기가 큰 수를 만든다.

• 정당성 분석

  • 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하고, 모두 2 이상인 경우 곱할 때 항상 가장 큰수를 만듦

data = input()

# 첫번째 문자를 숫자로 변경하여 대입
result = int(data[0])

# 왼쪽부터 순서대로 연산하므로 입력된 문자열을 순서대로 가져와서 계산
for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0'또는 '1'인 경우, 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

02945 -> 360

(4) 모험가 길드

• 문제설명
  한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데 '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 제임스는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하세요.

• 입력조건

  • 첫째줄에는 모험가의 수 N이 주어집니다.(1≤N≤100,000)
  • 둘째줄에는 각 모험가의 공포도의 값을 N이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.
  • 입력예시

    5
    2 3 1 2 2

• 출력조건 : 여행을 떠날 수 있는 그룹 수의 최대값을 출력합니다. (예시: 2)

• 문제해결 아이디어

  • 모험가의 공포도를 오름차순으로 정렬한 후 공포도가 낮은 모험가부터 하나씩 확인하여 그룹을 생성한다.

• 정당성 분석

  • 공포도가 낮은 모험가부터 그룹을 결성하게 되어 항상

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
    count += 1 # 현재 그룹에 해당 모험가를 포함시키기
    if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        result += 1 # 총 그룹의 수 증가시키기
        count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result) # 총 그룹의 수 출력

5
2 1 3 2 2
2

(5) 숫자 카드 게임

• 문제설명
  숫자카드게임은 여러개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임입니다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같습니다.

• 숫자가 쓰인 카드들이 N x M형태로 높여있다. N은 행의 길이, M은 열의 길이를 의미한다.

• 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

• 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 드를 뽑아야 한다.

• 입력조건

  • 첫째줄에는 숫자 카드들이 놓인 행의 개수 N과 M이 공백기준으로 하여 각각 자연수로 주어집니다. (1≤N,M≤100)
  • 둘째줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어집니다. 각 숫자는 1이상 10,000이하의 자연수입니다.
  • 입력예시

    3 3
    3 1 2
    4 1 4
    2 2 2

• 출력조건: 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력합니다. (예시: 2)

• 문제해결 아이디어

  • 각 행마다 가장 작은 수를 찾은 후, 그 수 중에서 가장 큰수를 구한다.

• 정당성 분석

  • 행을 먼저 선택하지만, 해당 행에서 가장 낮은 카드를 뽑아 최종적으로 가장 높은 숫자를 뽑는 것이므로, 각 행별로 최소값을 뽑고 그중 최대값을 뽑으면 항상 가장 큰 수를 고를 수 있다.

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

6 6
1 2 7
2 5 6
3 1 0
8 7 9
6 3 4
7 1
7

(6) 회의실 배정

• 문제설명
  한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 합니다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있습니다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

• 입력조건

  • 첫째줄에는 회의의 수 N(1≤N≤100,000)이 주어진다.
  • 둘째줄부터 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
    시작 시간과 끝나는 시간은 $2^{31}-1$보다 작거나 같은 자연수 또는 0이다.
  • 입력예시

    3
    1 3
    2 4
    3 5

• 출력조건 : 최대 사용할 수 있는 회의실의 최대 개수를 출력한다. (예시: 2)

• 문제해결 아이디어

  • 회의 종료시간을 기준으로 정렬하여 이후 회의를 시작가능하도록 한다.
  • 가장 먼저 끝나는 회의를 선택하고, 그 회의가 끝나는 시간이후에 시작하는 회의를 다시 선택하여 겹치지 않게 회의실의 수를 배정한다.

# N과 회의의 시작과 끝나는 시간 정보 입력 받기
n = int(input())  # 회의의 수
meetings = [tuple(map(int, input().split())) for _ in range(n)]

result = 0 #회의실의 개수
# 회의들을 끝나는 시간 기준으로 오름차순 정렬
meetings.sort(key=lambda x: x[1])
# 회의실 사용을 위한 초기 설정
end_time = -1  # 마지막으로 선택한 회의의 끝나는 시간

for start, end in meetings:
    # 현재 회의의 시작시간이 끝나는 시간 이후에 시작하면 선택
    if start >= end_time:
        result += 1
        end_time = end  # 끝나는 시간을 갱신

# 최대 회의실 개수 출력
print(result)

3
1 2
3 5
2 6
2