거스름돈
- 1260원을 가장 적은 갯수의 잔돈으로 나눠주려면 어떻게 해야 하는 가?
a = 1240
b = [500, 100, 50, 10]
count = 0
for i in b:
count += a//i
print(f"{i}원 : {a//i}개")
a %= i
print(count)시간 복잡도
화폐의 종류가 k라고 할 때, k 번 반복하므로 O(k)이다.
1이 될때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 두 번째 연산을 N이 K로 나누어떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후 2번을 2번 반복하면 N은 1이된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오
# 내가 푼 문제
# Solution
본 문제의 원리는
# N이 K로 나누어떨어지는 숫자가 될 때까지 빼기에서target은 n에서 가까운 숫자 중에서 K로 나누어떨어지는 숫자이다. 또 이를 통해 n과 target의 차이를 통해 result에 몇 번을 빼야 하는지 알려주고,n을 target으로써 업데이트 한다.
그리고 만약 이 시점에서 n이 k보다 작다면, 더 이상 나눌 수 없는 상태를 의미하기 때문에 반복문을 멈춘다.
그 후 result는 k로 한 번 나눠줘야 했기 때문에 횟수를 한 번 추가하고 n을 k로 나눠줌으로써, 업데이트 한다. 이렇게 반복함으로써, 더 이상 n을 나눌 수 없을 때까지 반복한다.
그 후 마지막에 반복문을 나간뒤에, 남아있는 더 이상 나눌 수 없는 n을-1한 횟수로써 더해주어 문제를 해결한다.
후기
내꺼가 조금 더 느리네. 또 solution의 시간 복잡도가 O(log(n))으로 더 적게 되기 때문에, 더 효율적이다.
곱하기 혹은 더하기
각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0+2)x9)x8)x4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.
- 입력
: 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다.
(1<=S의 길이<=20) - 출력
: 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.
풀이
data = input()
# 첫 번째 문자를 숫자로 바꾸어 대입
result = int(data[0])
for a in data[1:]:
num = int(a)
# 둘 중에 하나라도 0 혹은 1인 경우, 곱하기 보다는 더하기 수행
if result <= 1 or num <=1:
result += num
else:
result *= num
print(result)문제의 핵심은 0이나 1은 더하는 게 조금이라도 더 커지는 방법이고, 그 이외에는 그냥 곱하는 것이 더 커지는 방법이라는 점이다. 따라서 다음과 같이 코드를 구성해야 한다.
후기
코드에 많이 익숙하지 않아, 아이디어를 떠올려도 구현하는 능력이 부족하다. 반복 연습해서 이를 키우도록 하자. 그래도 원리는 잘 떠올려서 좋다
모험가 길드
공포도가 높을수록 공포를 많이 느끼는 사람이다.
X 공포도를 가진 사람은 X 명 이상의 그룹에 속해야 그룹을 형성할 수 있다.
모험을 떠날 수 있는 최대 그룹수를 구하라
( 단, 모든 사람이 그룹이 결성이 되지 않아도 된다. )
- 입력 조건
N 명 , 전체 인원 수
모험가의 공포도 간격을 두고 N 개수 만큼 들어온다. - 출력 조건
모험을 떠날 수 있는 최대 그룹수를 구하라. - 입력 예시
5
2 2 1 2 3 - 출력 예시
2
풀이
n = int(input())
list_n = list(map(int, input().split()))
list_n.sort()
result = 0
count = 0
for i in list_n:
count += 1 #현재 그룹에 하나씩 포함하기
if count >= i: #현재 그룹에 포함된 모험가의 수가 현재의 콩포도 이상이라면, 그룹 결성
result += 1 #결성한 그룹 수 증가
count = 0 # 포함한 모험사의 수 초기화
print(result)후기
연습이 많이 필요해보인당.
상하좌우:
여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다.
가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는(N x N)에 해당한다.
여행가 A는 상, 하,좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다.
우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.
L : 왼쪽으로 한 칸 이동
R : 오른쪽으로 한 칸 이동
U : 위로 한 칸 이동
D : 아래로 한 칸 이동
이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어(1,1)의 위치에서 L 혹은 U를 만나면 무시된다.
이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다.
다시말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오
풀이
n = int(input())
x, y = 1, 1
plans = list(map(str, 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)후기
모든 유형에 익숙해질 필요가 있다. 차근차근히 해보자.
시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.
- 입력 조건
첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)- 출력 조건
00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.- 입력 예시
5- 출력 예시
511475
풀이
hour = int(input())
count =0
for i in range(hour+1):
for min in range(60):
for sec in range(60):
if '3' in str(i) + str(min) + str(sec):
count += 1
print(count)후기
머리가 아프다 머리가 아파. 해당 문제는 완전 탐색 문제로, 전부 다 확인해보면 된다. 왜냐하면 24*60*60으로 경우 수가 86400만 있기 때문에 많지 않기 때문이다. 고로 다 살펴보고 구하면 된다.
왕실의 나이트
행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
- 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
- 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
이처럼 8 × 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a 부터 h로 표현한다
예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음과 같은 2가지이다. a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.
오른쪽으로는 두 칸 이동 후 아래로 한 칸 이동하기 (c2)
아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기 (b3)
또 다른 예로 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다. 이건 직접 계산해보시오.
- 입력 조건
첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입련된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.- 출력 조건
첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.출처
나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬, 한빛미디어(2020)
풀이
location = input()
row = int(location[1])
column = int(ord(location[0])) - int(ord('a')) + 1
steps = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (-1, 2), (1, -2),
(-1, -2)]
result = 0
for i in steps:
next_row = row + i[0]
next_column = column + i[1]
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)
후기
column = int(ord(location[0])) - int(ord('a')) + 1 해당 문법이 귀찮음을 덜 수 있는 최고의 방법 같다. 여기서 알아야 하는 점은
ord(location[0]): ord() 함수는 주어진 문자의 유니코드 코드 포인트를 반환한다는 점이다. 예를 들어, ord('a')는 97, ord('b')는 98이다.
그 점을 잘 생각해서 풀자.
문자열 재정렬
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.
예를 들어 K1KA5CB7 이라는 값이 들어오면 ABCKK13을 출력합니다.
- 입력 조건
첫째 줄에 하나의 문자열 S가 주어집니다. (1 <= S의 길이 <= 10,000)- 출력 조건
첫째 줄에 문제에서 요구하는 정답을 출력합니다.- 입력 예시
K1KA5CB7- 출력 예시
ABCKK13
풀이
data = input()
result = []
value = 0
# 문자를 하나씩 확인하기
for a in data:
# 만약 문자가 알파벳이라면
if a.isalpha():
result.append(a)
else:
value += int(a)
# 알파벳을 오름차순으로 정렬
result.sort()
# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
result.append(str(value))
# 최종 결과 출력 (리스트를 문자열로 변환하여 출력)
print(''.join(result))후기
열심히 따라해서 익숙해지면 나도 할 수 있을 거 같당.
참고
print(''.join(result))
주어진 코드는 파이썬에서 리스트 result의 요소들을 문자열로 합쳐서 출력하는 코드입니다. join() 메서드는 리스트의 각 요소를 연결할 때 사용되며, ''는 요소들 사이에 아무것도 넣지 않겠다는 의미입니다.
예를 들어, result가 ['a', 'b', 'c']일 경우, print(''.join(result))는 abc를 출력합니다.
