✅ 12 회차 모의고사 D-19일
🚀 1차 코딩테스트 대비
- 백준 10157 (자리배정)
- 백준 2004 (조합 0의 개수)
- 백준 16165 (걸그룹 마스터 준석이)
- 백준 11501 (주식)
- SQL 이름에 el이 들어가는 동물 찾기
1차 풀이
⭐ 1. 백준 10157 (자리배정)
# 1. 알고(구현): 백준 10157 (자리배정) - https://www.acmicpc.net/problem/10157
import sys
from io import StringIO
sys.stdin = StringIO('''7 6
11''')
input = sys.stdin.readline
def solve():
C, R = map(int, input().split())
K = int(input())
total_seat = C*R
if total_seat < K:
print(0)
return
visited = [[False] * R for _ in range(C)] # board를 세움
directions = [(0, +1), (+1, 0), (0, -1), (-1, 0)]
x, y = 0, 0
visited[0][0] = True
set_count = 1
dir_idx = 0
while set_count < K:
dx, dy = directions[dir_idx]
nx, ny = x + dx, y + dy
if 0 <= nx < C and 0 <= ny < R and not visited[nx][ny]:
x, y = nx, ny
visited[x][y] = True
set_count += 1
else:
dir_idx = (dir_idx + 1) % 4
print(x+1, y+1)
solve()⭐ 2. 백준 2004 (조합 0의 개수)
# 2. 알고(수학): 백준 2004 (조합 0의 개수) - https://www.acmicpc.net/problem/2004
import sys
from io import StringIO
sys.stdin = StringIO('''25 12''')
input = sys.stdin.readline
def solve():
# (n, m) = n! // (m!*(n-m)!)
n, m = map(int, input().split())
def cnt_factor(num, p):
count = 0
while num > 0:
num //= p
count += num
return count
nomer_cnt_5 = cnt_factor(n, 5)
nomer_cnt_2 = cnt_factor(n, 2)
left_denom_5 = cnt_factor(m, 5)
left_denom_2 = cnt_factor(m, 2)
right_denom_5 = cnt_factor(n - m, 5)
right_denom_2 = cnt_factor(n - m, 2)
final_factor_5 = nomer_cnt_5 - left_denom_5 - right_denom_5
final_factor_2 = nomer_cnt_2 - left_denom_2 - right_denom_2
print(min(final_factor_5, final_factor_2))
solve()⭐ 3. 백준 16165 (걸그룹 마스터 준석이)
# 3. 알고(Map): 백준 16165 (걸그룹 마스터 준석이) - https://www.acmicpc.net/problem/16165
import sys
from io import StringIO
sys.stdin = StringIO('''3 4
twice
9
jihyo
dahyeon
mina
momo
chaeyoung
jeongyeon
tzuyu
sana
nayeon
blackpink
4
jisu
lisa
rose
jenny
redvelvet
5
wendy
irene
seulgi
yeri
joy
sana
1
wendy
1
twice
0
rose
1''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
team_member = dict()
member_team = dict()
for _ in range(N):
team = input().rstrip()
member_cnt = int(input())
members = []
for _ in range(member_cnt):
member_name = input().rstrip()
members.append(member_name)
member_team[member_name] = team
members.sort()
team_member[team] = members
answers = list()
for _ in range(M):
quize = input().rstrip()
cmd = int(input())
if cmd == 0:
member = team_member[quize]
member.sort()
answers.extend(member)
else:
team_name = member_team[quize]
answers.append(team_name)
print("\n".join(answers))
solve()⭐ 4. 백준 11501 (주식)
# 4. 알고(그리디): 백준 11501 (주식) - https://www.acmicpc.net/problem/11501
import sys
from io import StringIO
sys.stdin = StringIO('''3
3
10 7 6
3
3 5 9
5
1 1 3 1 2''')
input = sys.stdin.readline
def solve():
input()
prices = list(map(int, input().split()))
max_price = 0
profit = 0
for price in reversed(prices):
if price > max_price:
max_price = price
else:
profit += max_price - price
print(profit)
T = int(input())
for _ in range(T):
solve()✏️ 5. SQL 이름에 el이 들어가는 동물 찾기
-- 5. SQL(Lv.2): 이름에 el이 들어가는 동물 찾기
-- https://school.programmers.co.kr/learn/courses/30/lessons/59047
SELECT
ANIMAL_ID,
NAME
FROM
ANIMAL_INS
WHERE
NAME LIKE '%el%'
AND ANIMAL_TYPE = 'Dog'
ORDER BY
NAME;🚀 2차 코딩테스트 대비
- 백준 16235 (나무 재테크)
- 백준 2294 (동전 2)
- 백준 2638 (치즈)
- 백준 1038 (감소하는 수)
- SQL 우유와 요거트가 담긴 장바구니
2차 풀이
⭐ 1. 백준 16235 (나무 재테크)
# 1. 알고(시뮬): 백준 16235 (나무 재테크) - https://www.acmicpc.net/problem/16235
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''5 2 6
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3
3 2 3''')
input = sys.stdin.readline
def solve():
N, M, K = map(int, input().split())
# 8방향
directions = [
(r, c)
for r, c, in product([-1, 0, +1], repeat=2)
if (r, c) != (0, 0)
]
# rows, cols 조합 미리 저장.
rows_cols = tuple(product(range(0, N), repeat=2))
A = [list(map(int, input().split())) for _ in range(N)]
# dict() 넣을때 * N 사용 금지.
trees_arr = [[dict() for _ in range(N)] for _ in range(N)]
trees = [list(map(int, input().split())) for _ in range(M)]
for x, y, age in trees:
trees_arr[x-1][y-1][age] = 1 # 입력으로 주어지는 나무위치는 모두 다름
nutrition = [[5] * N for _ in range(N)] # 영양분
while K > 0: # 1년 사이클.
# 봄 + 여름: 나이만큼 양분 먹고 -> 나이가 1 증가, 나이만큼 양분을 먹을 수 없으면 즉사, # 어린 나무부터 양분,
for (r, c) in rows_cols:
trees_dict = trees_arr[r][c]
cur_nutri = nutrition[r][c]
grown_trees = dict()
dead_nutri = 0 # 여름에 추가될 영양성분
for tree_age, count in sorted(trees_dict.items()): # 어린 나무 부터
survive_count = min(count, cur_nutri // tree_age)
dead_count = count - survive_count
if survive_count > 0:
cur_nutri -= tree_age * survive_count
grown_trees[tree_age + 1] = survive_count
if dead_count > 0:
dead_nutri += (tree_age // 2) * dead_count
trees_arr[r][c] = grown_trees # 성장한 트리 값 추가.
nutrition[r][c] = cur_nutri + dead_nutri # 최종 영양 성분 저장.
# 가을 나무 번식, (나이가 5배수) => 인접칸 나이 나무 1
for r, c in rows_cols:
trees_dict = trees_arr[r][c]
for tree_age, count in trees_dict.items():
if tree_age % 5 == 0: # 나이가 5의 배수이면
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N:
nxt_tree_dict = trees_arr[nr][nc]
nxt_tree_dict[1] = nxt_tree_dict.get(1, 0) + count
# 겨울 A[R][C] 양분 추가.
for r, c in rows_cols:
nutrition[r][c] += A[r][c]
K -= 1 # 다음 해
# 살아있는 나무 개수.
live_trees_sum = 0
for r, c in rows_cols:
trees_dict = trees_arr[r][c]
for count in trees_dict.values():
live_trees_sum += count
print(live_trees_sum)
solve()⭐ 2. 백준 2294 (동전 2)
# 2. 알고(DP): 백준 2294 (동전 2) - https://www.acmicpc.net/problem/2294
import sys
from io import StringIO
sys.stdin = StringIO('''3 15
1
5
12''')
input = sys.stdin.readline
def solve():
n, k = map(int, input().split())
coins = set()
for _ in range(n):
coin = int(input())
if coin <= k:
coins.add(coin)
# dp[i] i 원을 만들기 위한 최소 길이
dp = [0] + [float('inf')] * k # 0원 만드는 최소길이는 0원
for coin in coins:
for i in range(coin, k + 1):
dp[i] = min(dp[i], dp[i - coin] + 1) # 사용 안할 때 , 사용할 때
print(dp[k] if dp[k] != float('inf') else -1)
solve()⭐ 3. 백준 2638 (치즈)
# 3. 알고(그래프): 백준 2638 (치즈) - https://www.acmicpc.net/problem/2638
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
directions = [(+1, 0), (-1, 0), (0, +1), (0, -1)]
time = 0
while True:
melt_target = list() # 녹을 대상.
visited = [[0]*M for _ in range(N)]
dq = deque([(0, 0)])
visited[0][0] = -1 # 빈곳 -1, 녹일곳 +1
while dq:
r, c = dq.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < M:
nxt_val = board[nr][nc]
visit_info = visited[nr][nc]
if nxt_val == 0 and visit_info == 0:
dq.append((nr, nc))
visited[nr][nc] = -1
elif nxt_val == 1 and visit_info < 2:
visit_info += 1
if visit_info == 2:
melt_target.append((nr, nc))
visited[nr][nc] = visit_info
if melt_target:
for r, c in melt_target:
board[r][c] = 0
else:
break # 녹을 대상 더 이상 없으면 종료.
time += 1
print(time)
solve()⭐ 4. 백준 1038 (감소하는 수)
# 4. 알고(백트래킹): 백준 1038 (감소하는 수) - https://www.acmicpc.net/problem/1038
import sys
from io import StringIO
sys.stdin = StringIO('''18''')
input = sys.stdin.readline
def solve():
N = int(input())
answers = []
digits = []
def dfs(max_val):
if max_val == -1:
return
if not digits:
for num in range(max_val):
digits.append(num)
dfs(num)
digits.pop()
else:
answers.append(int("".join(map(str, digits)))) # 출력
last_num = digits[-1]
for num in range(max_val):
if num < last_num:
digits.append(num)
dfs(num)
digits.pop()
dfs(10)
if N >= len(answers):
print(-1)
else:
answers.sort()
print(answers[N])
solve()✏️ 5. SQL 우유와 요거트가 담긴 장바구니
-- 5. SQL(Lv.4): 우유와 요거트가 담긴 장바구니
-- https://school.programmers.co.kr/learn/courses/30/lessons/62284
SELECT
CART_ID
FROM
CART_PRODUCTS
WHERE
NAME IN ('Milk', 'Yogurt')
GROUP BY
CART_ID
HAVING
COUNT(DISTINCT NAME) = 2
ORDER BY
CART_ID;