이코테 강의 몰아보기 | 2-1. 그리디 & 구현

[1] 그리디

 

1. 그리디 알고리즘

: 탐욕법이라고도 하며 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩 테스트에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

 

#3-1 거스름돈(Page.87)

아이디어 : 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

정당성 분석 : 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

 

#3-1. 거스름돈

n = 1260 #예를들어 1260원을 거슬러줘야 됨
count = 0 

#큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수
    n %= coin #남은 돈 다시 n에 리셋(1260원에서 1000(500*2) 거슬러 주고 남은 260을 n에 저장)
    
print(count)

#출력 결과
6

 

 

#3-2 1이 될 때까지(Page 99)

아이디어 : 주어진 N에 대하여 최대한 많이 나누기를 실행한다.

정당성 분석 : K가 2 이상기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.

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

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k
    result += (n - target)
    n = target

    # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

 

#3-3 곱하기 혹은 더하기(Page 312)

아이디어 : 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 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)

 

#3-4 모험가 길드(Page 311)

아이디어 : 오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인한다.

'현재 그룹에 포함된 모함가의 수'가 '현재 확인하고 있는 공포도'보다 크거나 같다면 이를 그룹으로 설정한다.

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)

 

 

 

 

[2] 구현 : 시뮬레이션과 완전 탐색

 

1. 구현(Implementation)이란?

: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.

 

1-1 구현 문제 유형

- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제

- 적절한 라이브러리를 찾아서 사용해야 하는 문제

 

 

#4-1 상하좌우(Page 110)

아이디어 : 요구사항대로 충실히 구현하면 되는 문제

# N 입력 받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인하기
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
            
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx> n or ny > n:
        continue
     x,y = nx, ny
     
print(x,y)

 

#4-2 시각(Page 113)

아이디어 : 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제

이러한 유형은 완전 탐색(Brute Forcing) 문제 유형이라고 불린다.

가능한 경우의 수를 모두 검사해보는 탐색 방법을 의미한다.

# H 입력 받기
h = int(input())

count = 0
for i in range(h + 1): #시
    for j in range(60): #분
        for k in range(60): #초
            #매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1
print(count)

 

#4-3 왕실의 나이트(Page 115)

아이디어 : 요구사항대로 충실히 구현하면 되는 문제이다.

나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인한다.

리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의한다.

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0]))) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
# 상좌, 상우, 하좌, 하우, 좌상, 좌하, 우상, 우하
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + steps[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

 

#4-4 문자열 재정렬(Page 322)

아이디어 : 문자열이 입력되었을 때 문자를 하나씩 확인

숫자인 경우 따로 합계를 계산, 알파벳의 경우 별도의 리스트에 저장한다.

결과적으로 리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력하면 정답

data = input()
result = []
value = 0

#문자를 하나씩 확인하며
for x in data:
    #알파벳인 경우 결과 리스트에 삽입
    if x.isalpha():
        result.append(x)
    #숫자는 따로 더하기
    else:
        value = int(x)

#알파벳을 오름차순으로 정렬
result.sort()

#숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
    result.append(str(value))

#최종 결과 출력(리스트를 문자열로 변환하여 출력)
print(''.join(result))