동빈나 님의 이코테 2021 강의 몰아보기 를 보면서 공부한 내용을 정리하고 있습니다. 더 자세한 내용은 이것이 취업을 위한 코딩 테스트다 with 파이썬 을 참고해주세요 학습 도구로는 리플렛 을 사용하고 있고 원본 소스코드는 동빈님의 Github 에서 확인할 수 있고 스스로 공부한 소스코드는 Github 에서 확인할 수 있습니다.그리디 알고리즘
•
현재 상황에서 지금 당장 좋은 것만 고르는 방법
•
일반적으로는 문제를 받자마자 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
•
그리디 해법은 그 정당성 분석이 매우 중요함
◦
단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
•
일반적으로는 최적의 해를 보장할 수 없을 때가 많다.
•
하지만 코테에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 논할 수 있어야 풀리도록 문제가 풀제된다.
◦
탐욕법이 최적의 해가 되는 상황에서 문제가 출제된다.
거스름돈 문제
문제
•
편의점 알바가 500, 100, 50, 10 원짜리 동전을 무한정 가지고 있다.
•
손님에게 거스름돈을 최소한의 동전개수로 거슬러주기 위해서는 어떻게 해야할까
해결
•
풀이
◦
돈의 단위가 큰 동전부터 우선적으로 거술러주면 된다.
◦
예를 들어 거스름돈이 1,250 원일 경우, 총 5개의 동전으로 거술러 주는 것이 동전 수를 최소화 하는 방법이다.
▪
500 * 2
▪
100 * 2
▪
50 * 1
•
정당성 분석
◦
왜 큰 화폐단위부터 거슬러주는게 최적의 해를 보장하는 것일까?
◦
가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수가 되므로 작은 단위의 동전을 종합해서 다른 해가 나올 수 없기 때문이다.
◦
예를 들면 800원이 거스름 돈이라고 할 때, 500원, 400원, 100원이 있다면,
▪
그리디로 풀게되면 5001 + 1003 = 총 4개의 동전이 답이 된다.
▪
하지만 정답은 400*2 = 2개이다.
▪
이 경우, 500원이 400원의 배수가 아니기 때문에 400원을 조합해서 다른 해가 나올 수 있게 되는 것!
•
그리디 알고리즘 정리
1.
문제 풀이를 위해서 최소한의 아이디어 떠올리기
2.
그 해답이 정당한지 분석하기
#### 최소동전개수 거스름돈array = [500, 100, 50, 10]
coin_num = 0change = 1260for coin in array:
coin_num += change // coin
change %= coin
print("거스름돈 동전의 개수는 ", coin_num, " 개 입니다.")
Python
복사
1이 될 때까지
문제
•
두 개의 숫자 N, K가 주어진다.
•
어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다.
◦
N에서 1을 뺀다.
◦
N에서 K를 나눈다.
•
예를들면 N=17, K=4 이면,
◦
1번 수행 후, N=16
◦
2번 수행 후, N=4
◦
3번 수행 후, N=1
•
전체적으로 실행한 횟수는 3이 된다.
•
이처럼 어떤 조건과 수행해야할 일이 주어지고 그 수행의 최소 횟수를 구하는 프로그램을 작성해야하는 것
해결
•
주어진 N에 대하여 최대한 많이 나누는 것이 이득이다.
•
목표는 N의 값을 줄여서 1까지 만드는 것
•
N의 값을 작게 만드는데 가장 좋은 방법은 1을 빼는 것보다는 K로 나누는 것이다.
•
정당성 분석
◦
N이 아무리 큰 수여도 K로 계속 나눈다면 기하 급수적으로 빠르게 줄일 수 있다.
◦
K가 2이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음
# 1이 될 때까지n = 25k = 5cnt = 0while True:
if n % k == 0:
n = n // k
else:
n -= 1 cnt += 1 if n == 1:
breakprint(cnt)
# 1이 될 때까지 - 참고n, k = map(int, input().split())
result = 0while True:
target = (n // k) * k
result += (n - target)
n = target
if n < k:
break result += 1 n //= k
result += (n - 1)
print(result)
Python
복사
곱하기 혹은 더하기 문제
문제
•
각 자리가 숫자(0-9)로만 이루어진 문자열 S 가 주어졌을 때,
•
왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 * 혹은 + 연산자를 넣어서
•
결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램
•
단, + 보다 * 를 먼저 게산하는 일반적인 방식과 다르게, 모든 연산은 왼쪽에서부터 차례대로 이루어진다고 가정한다.
•
예를 들어 “02984” 라는 문자열로 만들 수 있는 가장 큰 수는 (0+2) * 9 * 8 * 4 = 576 이다.
•
만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수이다.
◦
정수의 최대 범위가 21억이기 때문!
◦
파이썬에서는 정수 범위가 정해져있지 않기 때문에 큰 문제가 되지 않음
해결
•
조건에 맞으면 더하기, 조건 안맞으면 곱하기 -> 전형적인 그리디 알고리즘
•
두 수 중 하나라도 0 또는 1인 경우 더하기가 유리하다.
•
나머지 경우에는 모두 곱셈이 유리함!
•
java 의 경우 : 문자열의 특정 포인트 접근을 위하여 charAt(n) method 사용
### 곱하기 혹은 더하기 문제# 0일 경우 무조건 더하기# 0이 아니면 무조건 곱하기가 유리numbers = list(map(int, input()))
sum = 0for num in numbers:
if sum == 0 or num == 0:
sum += num
else:
sum *= num
print(sum)
## 풀이# 두 수 중 하나라도 0 또는 1인 경우 더하기가 유리하다.# 나머지 경우에는 모두 곱셈이 유리함!data = input()
# 첫번째 문자를 숫자로 변경하여 대입한다.result = int(data[0])
for i in range(1, len(data)):
num = int(data[i])
if num <= 1 or result <= 1:
result += num
else :
result *= num
print(result)
Python
복사
모험가 길드 문제
문제
•
한 마을에 모험가가 n 명 존재
•
이들을 대상으로 공포도를 측정함
•
공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
•
모험가 그룹 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X 명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정함
•
동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있을까?
•
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 잇는 그룹 수의 최댓값을 구하는 프로그램을 작성해야함!
해결
•
입력값을 오름차순으로 정렬 후
•
현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도 -> 바로 그룹결성가능!
# 모험가 길드 문제x = int(input())
scare_points = list(map(int, input().split()))
scare_points.sort()
result = 0count = 0for point in range(len(scare_points)):
count += 1 if count >= point:
result += 1 count = 0print(result)
Python
복사
구현 : 시뮬레이션과 완전 탐색
•
기본적으로 머리속에 있는 알고리즘을 소스코드로 옮기는 작업!
•
보통 알고리즘 대회에서 구현 유형의 문제
◦
풀이를 떠올리는 건 쉬운데 소스코드로 옮기기 어려운 문제
•
대표적인 유형은 다음과 같음
◦
알고리즘은 간단하지만 코드가 지나칠만큼 길어지는 문제
◦
실수 연산을 다루고 특정 소수점 자리까지 출력해야하는 문제
◦
문자열 특정한 기준에 따라서 끊어 처리해야하는 문제
◦
적절한 라이브러리를 찾아서 사용해야하는 문제
•
2차원 공간 -> 행렬의 의미로 사용
•
2차원 공간에서의 방향 벡터가 많이 사용됨
상하좌우 문제
문제
•
N 이 100이하로 주어짐
•
N * N 정사각형 공간 위에 서있음
•
가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N) 이다.
•
여행가 A는 상, 하, 좌, 우로 이동 가능하며 시작 좌표는 항상 (1, 1)
•
여행할 계획표가 주어진다. 계획표에는 L, R, U, D 가 적혀있고 각각 왼쪽, 오른쪽, 위, 아래로 1칸씩 이동하는 것을 의미함
해결
•
요구사항대로 충실히 구현하면 됨
# 상하좌우 문제# 상하좌우 이동시 변경될 좌표값 -> 미리 배열로 정의size = int(input())
plans = input().split()
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
x, y = 1, 1for plan in plans:
for i in range(len(move_types)):
if plan == move_types[i]:
tx = x + dx[i]
ty = y + dy[i]
if tx < 1 or tx > size or ty < 1 or ty > size:
continue x, y = tx, ty
print(x, y)
Python
복사
시각 문제
문제
•
정수 N이 입력되면 00시 00분 00초 ~ N시 59분 59초까지 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성
•
1을 입력했다면,
◦
00시 00분 03초
◦
00시 13분 30초
•
다음은 세면 안되는 시각
◦
00시 02분 55초
◦
01시 27분 45초 등
풀이
•
가능한 모든 시각의 경우의 수를 모두 세서 풀 수 있는 문제 = 완전 탐색 문제!
•
하루는 24 * 60 * 60 = 86,400 초 -> 하루에 가능한 경우의 수는 86,400가지
◦
python 기준 1초에 2000 만번 연산을 처리한다고 가정하면 모든 경우의 수를 돌아도 전혀 무리되지 않음
•
시각을 단순히 0부터 1씩 증가시키면서 3이 하나라도 포함되어있는지를 검사한다.
# 시각# 3이 하나라도 포함되는 시각의 모든 경우의 수# 00:00:00 ~ N:59:59hour = int(input())
count = 0for h in range(hour+1):
for m in range (60):
for s in range(60):
if '3' in str(h) + str(m) + str(s):
count += 1print(count)
# 5# 11475
Python
복사
왕실의 나이트 문제
문제
•
행복왕국의 왕실 정원은 체스판과 같은 8 * 8 좌표 평면 -> 2차원!
•
특정 칸에 나이트가 서있다.
•
말을 타고 있어서 이동할 때에는 L자 형태로만 이동할 수 있고
◦
수평으로 2칸 + 수직으로 1칸
◦
수직으로 2칸 + 수평으로 1칸
•
정원 밖으로는 이동할 수 없다.
•
나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램
•
행 위치는 1 - 8
•
열 위치는 a - h 로 표현한다.
해결
•
역시 구현문제의 일종이다. 요구사항대로 충실하게 구현만 하면 됨
•
리스트를 활용하여 8가지 방향에 대한 방향 벡터를 정의한다.
# 왕실의 나이트 문제# 역시 구현문제 -> 요구사항대로 충실히 구현만 하면 됨# 풀이pin = input()
# a - h 의 문자값을 숫자로 바꾸는 작업 필요tx = ord(pin[0])
x = tx - ord('a') + 1y = int(pin[1])
result = 0# 총 경우의 수는 8가지 일듯moves = [(+2, -1), (+2, +1), (-2, -1), (-2, +1), (-1, +2), (-1, -2), (+1, -2), (+1, +2)]
for move in moves:
nx = x + move[0]
ny = y + move[1]
if nx < 1 or nx > 8 or ny < 1 or ny > 8:
continue result += 1print(result)
Python
복사
문자의 재정렬 문제
문제
•
알파벳 대문자와 숫자 (0-9)로만 구성된 문자열이 입력으로 주어짐
•
모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.
•
예를 들어, K1KA5CB7 이라는 값이 들어오면 ABCKK13 으로 출력한다.
•
참고
◦
코딩에서 숫자와 수
▪
숫자 : 0 - 9
▪
수 : 100, 1230 와 같은 정수
해결
•
주어진 요구를 충실하게 수행하면 될듯.
•
주어진 요구
◦
알파벳 먼저 앞으로 정렬
◦
숫자를 알파벳 정렬 이후에 정렬
•
해결 아이디어
1.
입력값받고
2.
반복 -> 문자는 문자배열에, 숫자는 숫자배열에 넣기
3.
문자배열 정렬, 출력
4.
숫자배열 정렬, 출력
•
풀이
# 문자의 재정렬# 문자정렬+숫자정렬문제일때# ord('0') : 48# ord('9') : 57# ord('A') : 65# ord('Z') : 90chars = list(input())
alpabets = []
nums = []
for char in chars:
if ord(char) <= ord('9'):
nums.append(int(char))
else:
alpabets.append(char)
alpabets.sort()
nums.sort()
print(''.join(str(w) for w in (alpabets+nums)))
# K1KA5CB7# ABCKK157# AJKDLSI412K4JSJ9D# ADDIJJJKKLSS12449# 문자의 재정렬 : 문자 정렬 + 숫자 합계# 풀이# 문자의 재정렬 풀이# 문자정렬 + 숫자의 합chars = input()
result = []
sum = 0for char in chars:
if char.isalpha():
result.append(char)
else:
sum += int(char)
result.sort()
if sum != 0:
result.append(str(sum))
print(''.join(result))
# K1KA5CB7# ABCKK13# AJKDLSI412K4JSJ9D# ADDIJJJKKLSS20
Python
복사