이 포스트는 동빈나 "이것이 취업을 위한 코딩테스트다 with 파이썬" 유튜브 강의를 기반으로 작성하였습니다. https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

그리디 (Greedy)

현재 상황에서 지금 당장 좋은 것만 고르는 방법
정당성 분석이 중요함 → 단순히 가장 좋아 보이는 것만 선택해도 최적의 해를 구할 수 있는지…

일반적으로 그리디 알고리즘은 최적의 해를 보장할 수 없다. 그러나 코테에서는 그리디로 얻은 결과가 최적해를 보장하는 경우를 추론해야함

(ex) 거스름 돈 문제 - N원을 거슬러 줄 때 거슬러 줘야 할 동전의 최소 개수를 구하시오

• 500, 100, 50, 10원처럼 화폐 단위에서 큰 단위가 모두 작은 단위의 배수일 경우 그리디가 최적해 보장
• 500, 400, 100원이면 그리디가 보장 못해줌

n=1260
count = 0
arr = [500, 100, 50, 10]

for coin in arr: # O(화폐의 개수)
	count += n // coin
	n %=coin

print(count)

1일 될 때까지

문제 설명)

어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택하여 수행하려한다.

• N에서 1을 뺀다

• N을 K로 나눈다

  N이 1이 될 때까지 수행해야 하는 과정의 최소 횟수를 구하시오

문제 풀이)

K가 2 이상이면 무조건 나누는게 1을 빼는 것보다 빠르게 N을 줄일 수 있음

n, k = map(int, input().split())
result = 0

while True:
	#N이 K로 나누어 떨어지는 수가 될 때까지 빼기
	target = (n // k) * k # 가장 가까운 K로 나누어 떨어지는 수
	result += (n - target)
	n = target
	# N이 K보다 작을 때 (더이상 나눌 수 없을때) break
	if n < k:
		break
	# K로 나누기
	result += 1
	n //= k

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

곱하기 혹은 더하기

문제 설명)

각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘x’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하시오. 단 +보다 x를 먼저 계산하는 일반적인 방식이 아니라 왼쪽에서부터 그냥 수식을 수행하면 된다.

ex) 02984 : ((((0+2) x 9) x 8) x 4) = 576

문제 풀이)

숫자 둘 중 0, 1이 있으면 더하는게 유리, 숫자 둘 다 2 이상은 곱하는게 유리

nums = input().split()
result = int(nums[0])
for i in range(1, len(nums))
	if nums[i] < 2 or result < 2:
		result += int(nums[i])
	else:
		result *= int(nums[i])
print(result)

모험가 길드

문제 설명)

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’를 측정했는데 ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.

동빈이는 최대 몇 개의 모험가 그룹을 만들수 있는지 궁금합니다. N명의 모험가에 대한 정보(공포도)가 주어졌을 때 여행을 떠날 수 있는 그룹 수의 최대값을 구하시오

ex) n = 5, 모험가 = [2, 3, 1, 2, 2]

그룹 1에 1,2,3 총 세 명 / 그룹 2에 2,2 총 두 명

총 2그룹 → 몇 명의 모험가는 마을에 남아있어도 된다. 무조건 모험가들을 특정 그룹에 넣을 필요는 없다

문제 풀이)

공포도가 낮은 모험가부터 차례로 그룹을 결성

n = int(input())
explorers = list(map(int, input().split())
explorers.sort()
result, i = 0, 0

while i < len(explorers):
	result += 1
	i += explorers[i]
print(result)

# 동빈나 풀이
n = int(input())
data = list(map(int, input().split())
data.sort()
result, count = 0, 0 # 총 그룹 수, 현재 그룹에 포함된 모험가의 수

for i in data:
	count += 1 # 현재 그룹에 해당 모험가 포함시키기
	if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이면 그룹 결성
		result += 1 # 총 그룹 수 증가
		count = 0 # 현재 그룹에 포함된 모험가 수 초기화

구현

풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정 기준에 따라 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

방향 벡터가 자주 활용됨

(0, 0)	(0, 1)	(0, 2)	(0, 3)	(0, 4)
(1, 0)	(1, 1)	(1, 2)	(1, 3)	(1, 4)
(2, 0)	(2, 1)	(2, 2)	(2, 3)	(2, 4)
(3, 0)	(3, 1)	(3, 2)	(3, 3)	(3, 4)
(4, 0)	(4, 1)	(4, 2)	(4, 3)	(4, 4)

#동,북,서,남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

#현재 위치
x, y = 2, 2
for i in range(4):
	# 다음 위치
	nx = x + dx[i]
	ny = y + dy[i] 
	print(nx, ny)

상하좌우 문제

문제 설명)

A는 n x n 크기 정사각형 공간위에 서 있다. 가장 왼쪽 위 죄표가 (1, 1)이고 가장 오른쪽 아래 좌표가 (n, n)에 해당한다. A는 상하좌우 방향으로 이동할 수 있으며 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 A가 이동할 계획이 적힌 계획서가 있다.

계획서에는 하나의 줄 띄어쓰기를 기준으로 L,R,U,D 중 하나의 문자가 반복적으로 적혀 있다.

• L : 왼쪽으로 한 칸 이동
• R : 오른쪽으로 한 칸 이동
• U : 위로 한 칸 이동
• D : 아래로 한 칸 이동

이 때, A가 정사각형 공간을 벗어나는 움직임은 무시된다.

A가 최종적으로 도착할 좌표를 구하시오

문제 풀이)

n = int(input()) # 공간의 크기
actions = list(map(int, input().split()))

for a in actions:
	if a == 'L':
	elif a == 'R':
	elif a == 'U':
	elif a == 'D':

# 동빈나 풀이 참고

시각

문제 설명)

정수 n이 입력되면 00시 00분 00초부터 N시 59분 59초까지 모든 시각 중 3이 하나라도 포함하는 모든 경우의 수를 구하는 프로그램을 작성하시오

1이 입력되면 다음은 3이 하나라고 포함되어 있으므로 세어야 한다.

• 00시 00분 3초
• 00시 13분 30초

반면 다음은 3이 하나도 포함되지 않으므로 세면 안된다.

• 00시 02분 55초
• 01시 27분 45초

문제 풀이)

하루는 86400초이므로 그냥 00시 00분 00초부터 n시 59분 59초까지 모두 다 세어봄 (brute force)

n = int(input))
total_sec = (n * 60 * 60) + (59 * 60) + 59
cnt = 0
for time in total_sec:
	tmp = time 
	h = tmp // 3600
	tmp -= h * 3600
	m = tmp // 60
	tmp -= m * 60
	s = tmp

#동빈나 풀이
h = int(input))
cnt = 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):
				cnt += 1
print(cnt)

왕실의 나이트

문제 설명)

행복 왕궁의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.

나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다.

나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

• 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
• 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 왕실의 정원에서 행 위치를 표현할 때는 1 - 8로 표현하며 열 위치를 표현할때는 a부터 h로 표현한다.

• c2에 있을 때 이동할 수 있는 경우의 수는 다음과 같다.
  

문제 풀이)

나이트가 이동할 수 있는 경우는 8가지이다. 나이트의 초기 위치가 주어지면 이 8가지 가능한 경로들로 이동했을 때 왕실의 범위를 벗어나는지 체크한다.

input_data = input()
row = int(input_data[0])
col = int(input_data[1]) - int(ord('a')) + 1

# 나이트가 갈 수 있는 8가지 방향
steps = [(-2. -1), (-1, -2), (-2, 1), (-1, 2), (2, -1), (2, 1), (1, -2), (1, 2)]
case = 0
for step in steps:
	next_row = row + step[0]
	next_col = col + step[1]
	if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
		case += 1
print(case)

문자열 재정렬

문제 설명)

알파벳 대문자와 숫자(0 - 9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다.

문제 풀이)

파이썬 string과 관련된 내장 함수를 이용하여 문제를 푼다.