✅ 13 회차 모의고사 D-18일
🚀 1차 코딩테스트 대비
- 백준 1713 (후보 추천하기)
- 백준 9613 (GCD 합)
- 백준 14425 (문자열 집합)
- 백준 2012 (등수 매기기)
- SQL 가격대 별 상품 개수 구하기
1차 풀이
⭐ 1. 백준 1713 (후보 추천하기)
# 1. 알고(구현): 백준 1713 (후보 추천하기) - https://www.acmicpc.net/problem/1713
import sys
from io import StringIO
sys.stdin = StringIO('''3
9
2 1 4 3 5 6 2 7 2''')
input = sys.stdin.readline
def solve():
N = int(input())
M = int(input())
likes = list(map(int, input().split()))
candidates = dict() # (추천수, 등록순서)
for i, number in enumerate(likes):
if number in candidates: # 사진 명단에 있으면
count, order = candidates[number]
candidates[number] = (count + 1, order)
continue
if len(candidates) == N: # 길이가 3이면 삭제
del_number = min(candidates, key=lambda x: candidates[x])
del candidates[del_number]
candidates[number] = (1, i)
print(*sorted(candidates))
solve()⭐ 2. 백준 9613 (GCD 합)
# 2. 알고(수학): 백준 9613 (GCD 합) - https://www.acmicpc.net/problem/9613
import sys
from itertools import combinations, islice
from math import gcd
from io import StringIO
sys.stdin = StringIO('''3
4 10 20 30 40
3 7 5 12
3 125 15 25''')
input = sys.stdin.readline
def solve():
data = map(int, input().split())
nums = islice(data, 1, None)
gcd_sum = 0
for a, b in combinations(nums, 2):
gcd_sum += gcd(a, b)
print(gcd_sum)
t = int(input())
for _ in range(t):
solve()⭐ 3. 백준 14425 (문자열 집합)
# 3. 알고(Map): 백준 14425 (문자열 집합) - https://www.acmicpc.net/problem/14425
import sys
from io import StringIO
sys.stdin = StringIO('''5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
S = set(input().rstrip() for _ in range(N))
A = sum(1 for _ in range(M) if input().rstrip() in S)
print(A)
solve()⭐ 4. 백준 2012 (등수 매기기)
# 4. 알고(그리디): 백준 2012 (등수 매기기) - https://www.acmicpc.net/problem/2012
import sys
from io import StringIO
sys.stdin = StringIO('''5
1
5
3
1
2''')
input = sys.stdin.readline
def solve():
N = int(input())
exp_rank = sorted(int(input()) for _ in range(N))
diff_sum = 0
for actual, exp in enumerate(exp_rank, start=1):
diff_sum += abs(actual - exp)
print(diff_sum)
solve()✏️ 5. SQL 가격대 별 상품 개수 구하기
-- 5. SQL(Lv.2): 가격대 별 상품 개수 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/131530
SELECT
TRUNCATE(price, -4) AS PRICE_GROUP,
COUNT(*) AS PRODUCTS
FROM
PRODUCT
GROUP BY
PRICE DIV 10000
ORDER BY
PRICE_GROUP;🚀 2차 코딩테스트 대비
- 백준 20056 (마법사 상어와 파이어볼)
- 백준 1106 (호텔)
- 백준 10282 (해킹)
- 백준 1182 (부분수열의 합)
- SQL 입양 시각 구하기(2)
2차 풀이
⭐ 1. 백준 20056 (마법사 상어와 파이어볼)
# 1. 알고(시뮬): 백준 20056 (마법사 상어와 파이어볼) - https://www.acmicpc.net/problem/20056
import sys
from collections import defaultdict
from io import StringIO
sys.stdin = StringIO('''7 5 3
1 3 5 2 4
2 3 5 2 6
5 2 9 1 7
6 2 1 3 5
4 4 2 4 2''')
input = sys.stdin.readline
def solve():
N, M, K = map(int, input().split())
ball_dict = defaultdict(list)
for _ in range(M):
r, c, mass, speed, dir = map(int, input().split())
ball_dict[(r-1, c-1)].append((mass, speed, dir))
directions = [
(-1, +0), (-1, +1), (+0, +1), (+1, +1),
(+1, +0), (+1, -1), (+0, -1), (-1, -1)
]
while K > 0:
# 이동
moved_ball_dict = defaultdict(list)
for (r, c), balls in ball_dict.items():
for m, s, d in balls:
dr, dc = directions[d]
nr = (r + dr * s) % N
nc = (c + dc * s) % N
moved_ball_dict[(nr, nc)].append((m, s, d))
merged_dict = defaultdict(list)
for (r, c), balls in moved_ball_dict.items():
if len(balls) >= 2:
total_mess = 0
total_speed = 0
dirs = []
for m, s, d in balls:
total_mess += m
total_speed += s
dirs.append(d % 2)
nm = total_mess // 5
ns = total_speed // len(balls)
if nm == 0: # 다음 질량이 0이면 모두 소멸
continue
odd_cnt = sum(dirs) # 홀수 개수 카운트
is_same_type = odd_cnt == 0 or odd_cnt == len(balls)
next_dirs = [0, 2, 4, 6] if is_same_type else [1, 3, 5, 7]
for nd in next_dirs:
merged_dict[(r, c)].append((nm, ns, nd))
else:
merged_dict[(r, c)] = balls
ball_dict = merged_dict
K -= 1
final_mass_sum = 0
for (r, c), ball_lst in ball_dict.items():
final_mass_sum += sum(m for m, *_ in ball_lst)
print(final_mass_sum)
solve()⭐ 2. 백준 1106 (호텔)
# 2. 알고(DP): 백준 1106 (호텔) - https://www.acmicpc.net/problem/1106
import sys
from io import StringIO
sys.stdin = StringIO('''12 2
3 5
1 1''')
input = sys.stdin.readline
def solve():
C, N = map(int, input().split())
# dp[i] = i명 이상을 모으는데 필요한 최소 비용
dp = [0] + [float('inf')] * C
for _ in range(N):
cost, custom = map(int, input().split())
for c in range(1, C + 1):
dp[c] = min(dp[c], dp[max(0, c-custom)] + cost)
print(dp[C])
solve()⭐ 3. 백준 10282 (해킹)
# 3. 알고(그래프): 백준 10282 (해킹) - https://www.acmicpc.net/problem/10282
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4''')
input = sys.stdin.readline
def solve():
n, d, c = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(d):
a, b, s = map(int, input().split())
graph[b].append((a, s))
pq = [(0, c)] # (누적 소요시간, 컴퓨터)
min_time = [float('inf')] * (n + 1)
min_time[c] = 0
while pq:
cur_time, cur = heappop(pq)
if cur_time != min_time[cur]:
continue
for nxt, time in graph[cur]:
nxt_time = cur_time + time
if nxt_time < min_time[nxt]:
heappush(pq, (nxt_time, nxt))
min_time[nxt] = nxt_time
result = list(filter(lambda x: x != float('inf'), min_time))
print(len(result), max(result))
T = int(input())
for _ in range(T):
solve()⭐ 4. 백준 1182 (부분수열의 합)
# 4. 알고(백트래킹): 백준 1182 (부분수열의 합) - https://www.acmicpc.net/problem/1182
import sys
from io import StringIO
sys.stdin = StringIO('''5 0
-7 -3 -2 5 8''')
input = sys.stdin.readline
def solve():
N, S = map(int, input().split())
nums = list(map(int, input().split()))
count = 0
def dfs(idx, sum_val):
nonlocal count
if idx == N:
return
num = nums[idx]
sum_val += num
if sum_val == S:
count += 1
dfs(idx + 1, sum_val) # 선택
dfs(idx + 1, sum_val - num) # 선택 안함
dfs(0, 0)
print(count)
solve()✏️ 5. SQL 입양 시각 구하기(2)
-- 5. SQL(Lv.4): 입양 시각 구하기(2)
-- https://school.programmers.co.kr/learn/courses/30/lessons/59413
WITH RECURSIVE
RECUR AS (
SELECT 0 AS HOUR
UNION ALL
SELECT HOUR + 1
FROM RECUR
WHERE HOUR < 23
),
CNT AS (
SELECT
HOUR(DATETIME) AS HOUR,
COUNT(*) AS COUNT
FROM ANIMAL_OUTS
GROUP BY HOUR
)
SELECT
HOUR,
IFNULL(COUNT, 0)
FROM RECUR
LEFT JOIN
CNT USING (HOUR)
ORDER BY HOUR;