✅ 15 회차 모의고사 D-16일
🚀 1차 코딩테스트 대비
- 백준 2960 (에라토스테네스의 체)
- 백준 1676 (팩토리얼 0의 개수)
- 백준 19583 (싸이버개강총회)
- 백준 19941 (햄버거 분배)
- SQL 성분으로 구분한 아이스크림 총 주문량
1차 풀이
⭐ 1. 백준 2960 (에라토스테네스의 체)
# 1. 알고(구현): 백준 2960 (에라토스테네스의 체) - https://www.acmicpc.net/problem/2960
import sys
from io import StringIO
sys.stdin = StringIO('''10 7''')
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
nums = set(range(2, N+1)) # Set 으로 풀어봄
del_cnt = 0
while nums:
P = min(nums)
nxt = P
while nxt <= N: # 지울 숫자 없어도 진행
if nxt in nums:
nums.discard(nxt)
del_cnt += 1
if del_cnt == K:
print(nxt)
return
nxt += P
solve()⭐ 2. 백준 1676 (팩토리얼 0의 개수)
# 2. 알고(수학): 백준 1676 (팩토리얼 0의 개수) - https://www.acmicpc.net/problem/1676
import sys
from io import StringIO
sys.stdin = StringIO('''10''')
input = sys.stdin.readline
def solve():
N = int(input())
def cnt_factor(num, p):
count = 0
while num > 0:
count += num // p
num //= p
return count
print(cnt_factor(N, 5))
solve()⭐ 3. 백준 19583 (싸이버개강총회)
# 3. 알고(Map): 백준 19583 (싸이버개강총회) - https://www.acmicpc.net/problem/19583
import sys
from io import StringIO
sys.stdin = StringIO('''22:00 23:00 23:30
21:30 malkoring
21:33 tolelom
21:34 minjae705
21:35 hhan14
21:36 dicohy27
21:40 906bc
23:00 906bc
23:01 tolelom
23:10 minjae705
23:11 hhan14
23:20 dicohy27''')
input = sys.stdin.readline
def solve():
S, E, Q = input().split()
start_set = set()
attend_set = set()
def convert_minute(time_str):
hour, min = map(int, time_str.split(':'))
return hour*60 + min
start_time = convert_minute(S)
end_time = convert_minute(E)
stream_end = convert_minute(Q)
while True:
temp = input().split()
if not temp:
break
time, name = temp
time = convert_minute(time)
if time <= start_time:
start_set.add(name)
elif end_time <= time <= stream_end and name in start_set:
attend_set.add(name)
print(len(attend_set))
solve()⭐ 4. 백준 19941 (햄버거 분배)
# 4. 알고(그리디): 백준 19941 (햄버거 분배) - https://www.acmicpc.net/problem/19941
import sys
from io import StringIO
sys.stdin = StringIO('''20 1
HHPHPPHHPPHPPPHPHPHP''')
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
infos = list(input().rstrip())
for i, info in enumerate(infos):
if info == 'P':
start = i - K if i - K >= 0 else 0 # max(0, i - K)
end = i + K if i + K < N else N - 1 # min(N - 1, i + K)
for possible in range(start, end + 1):
if infos[possible] == 'H':
infos[possible] = "#"
break
print(infos.count("#"))
solve()✏️ 5. SQL 성분으로 구분한 아이스크림 총 주문량
-- 5. SQL(Lv.2): 성분으로 구분한 아이스크림 총 주문량
-- https://school.programmers.co.kr/learn/courses/30/lessons/133026
SELECT
II.INGREDIENT_TYPE,
SUM(FH.TOTAL_ORDER) AS TOTAL_ORDER
FROM
FIRST_HALF FH
JOIN
ICECREAM_INFO II USING (FLAVOR)
GROUP BY
II.INGREDIENT_TYPE
ORDER BY
TOTAL_ORDER ASC;🚀 2차 코딩테스트 대비
- 백준 17142 (연구소 3)
- 백준 2631 (줄세우기)
- 백준 1197 (최소 스패닝 트리)
- 백준 2239 (스도쿠)
- SQL 자동차 대여 기록 별 대여 금액 구하기
2차 풀이
⭐ 1. 백준 17142 (연구소 3)
# 1. 알고(시뮬): 백준 17142 (연구소 3) - https://www.acmicpc.net/problem/17142
import sys
from itertools import product, combinations
from collections import deque
from io import StringIO
sys.stdin = StringIO('''7 3
2 0 2 0 1 1 0
0 0 1 0 1 0 0
0 1 1 1 1 0 0
2 1 0 0 0 0 2
1 0 0 0 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
directions = [(0, -1), (0, +1), (-1, 0), (+1, 0)]
emptys_len = 0
virus = []
for r, c in product(range(N), repeat=2):
val = board[r][c]
if val == 0:
emptys_len += 1
if val == 2:
virus.append((r, c))
# 활성 바이러스 좌표 받아서, 퍼트린 후 최대값 리턴, 좌표 0 set
def activate_virus(active_list, best):
max_val = 0
remain_cnt = emptys_len
visited = [[-1] * N for _ in range(N)]
dq = deque()
for r, c, in active_list:
dq.append((r, c))
visited[r][c] = 0
while dq:
r, c = dq.popleft()
nxt_time = visited[r][c] + 1
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == -1:
val = board[nr][nc]
if val == 0:
if nxt_time >= best: # Best 사례 있으면 종료.
return best, -1
max_val = max(max_val, nxt_time)
remain_cnt -= 1
if remain_cnt == 0: # 남은 칸 없으면 종료.
return max_val, 0
visited[nr][nc] = nxt_time
dq.append((nr, nc))
elif val == 1: # 벽
visited[nr][nc] = -2
elif val == 2: # 바이러스 활성
visited[nr][nc] = nxt_time
dq.append((nr, nc))
return max_val, remain_cnt
min_val = float('inf')
for active_combi in combinations(virus, M):
time, remain = activate_virus(active_combi, min_val)
if remain == 0:
min_val = min(min_val, time)
print(min_val if min_val != float('inf') else -1)
solve()⭐ 2. 백준 2631 (줄세우기)
# 2. 알고(DP): 백준 2631 (줄세우기) - https://www.acmicpc.net/problem/2631
import sys
from bisect import bisect_left
from io import StringIO
sys.stdin = StringIO('''7
3
7
5
2
6
1
4''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = [int(input()) for _ in range(N)]
# Longest Increasing Subsequence, 최장 증가 부분 수열
LIS = list()
for n in nums:
insert_idx = bisect_left(LIS, n)
if insert_idx == len(LIS):
LIS.append(n)
else:
LIS[insert_idx] = n
print(N - len(LIS))
solve()⭐ 3. 백준 1197 (최소 스패닝 트리)
# 3. 알고(그래프): 백준 1197 (최소 스패닝 트리) - https://www.acmicpc.net/problem/1197
import sys
from io import StringIO
sys.stdin = StringIO('''3 3
1 2 1
2 3 2
1 3 3''')
input = sys.stdin.readline
def solve():
# Minimum Spanning Tree(최소 신장 트리) MST
# 크루스칼(Kruskal) 알고리즘 + Union Find
V, E = map(int, input().split())
edges = list()
parent = list(range(V + 1))
size = [1] * (V + 1)
for _ in range(E):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
def union(ra, rb, cost):
nonlocal total_cost, edge_cnt
size_a = size[ra]
size_b = size[rb]
if size_a > size_b: # 작은쪽을 a 로 고정 (오름차순)
ra, rb = rb, ra # a길이가 크면 교환
parent[ra] = rb
size[rb] += size[ra] # 커진 노드 사이즈 증가.
edge_cnt += 1
total_cost += cost # 두 노드 합치고 비용 추가.
edge_cnt = 0 # 연결한 간선 수
total_cost = 0
for cost, a, b, in sorted(edges):
ra, rb = find(a), find(b)
if ra != rb: # 합쳐지지 않은 간선이면
union(ra, rb, cost)
if edge_cnt == V - 1: # 연결한 간선 수 연결 다 되면 종료.
break
print(total_cost)
solve()⭐ 4. 백준 2239 (스도쿠)
# 4. 알고(백트래킹): 백준 2239 (스도쿠) - https://www.acmicpc.net/problem/2239
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107''')
input = sys.stdin.readline
def solve():
board = [list(map(int, input().rstrip())) for _ in range(9)]
zeros = list()
need_serch = True
row_i = [[False] * 10 for _ in range(9)]
col_i = [[False] * 10 for _ in range(9)]
sqr_i = [[False] * 10 for _ in range(9)]
for r, c in product(range(9), repeat=2):
num = board[r][c]
if num == 0:
zeros.append((r, c))
else:
s = (r // 3) * 3 + c // 3 # 인덱스 계산
row_i[r][num] = True
col_i[c][num] = True
sqr_i[s][num] = True
def dfs(zero_idx):
nonlocal need_serch
if not need_serch: # sys.exit(0) 사용안함
return
if zero_idx == len(zeros):
print("\n".join("".join(map(str, row)) for row in board))
need_serch = False
return
r, c = zeros[zero_idx]
s = (r // 3) * 3 + c // 3
for n in range(1, 10):
if not row_i[r][n] and not col_i[c][n] and not sqr_i[s][n]:
row_i[r][n], col_i[c][n], = True, True
sqr_i[s][n], board[r][c] = True, n
dfs(zero_idx + 1)
row_i[r][n], col_i[c][n], = False, False
sqr_i[s][n], board[r][c] = False, 0
dfs(0)
solve()✏️ 5. SQL 자동차 대여 기록 별 대여 금액 구하기
-- 5. SQL(Lv.4): 자동차 대여 기록 별 대여 금액 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/151141
WITH
CF AS (
SELECT
CAR_ID,
DAILY_FEE
FROM CAR_RENTAL_COMPANY_CAR
WHERE CAR_TYPE = '트럭'
),
CH AS (
SELECT
HISTORY_ID,
CAR_ID,
DATEDIFF(END_DATE, START_DATE) + 1 AS DAY,
CASE
WHEN 90 <= DATEDIFF(END_DATE, START_DATE) + 1 THEN 90
WHEN 30 <= DATEDIFF(END_DATE, START_DATE) + 1 THEN 30
WHEN 7 <= DATEDIFF(END_DATE, START_DATE) + 1 THEN 7
ELSE NULL
END
AS DT_ID
FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY
),
DP AS (
SELECT
CASE
WHEN DURATION_TYPE = '7일 이상' THEN 7
WHEN DURATION_TYPE = '30일 이상' THEN 30
WHEN DURATION_TYPE = '90일 이상' THEN 90
END AS DT_ID,
DISCOUNT_RATE
FROM CAR_RENTAL_COMPANY_DISCOUNT_PLAN
WHERE CAR_TYPE = '트럭'
)
SELECT
HISTORY_ID,
(DAILY_FEE * (100 - IFNULL(DISCOUNT_RATE, 0) )) DIV 100 * DAY AS FEE
FROM CF
JOIN CH USING (CAR_ID)
LEFT JOIN DP USING (DT_ID)
ORDER BY
FEE DESC,
HISTORY_ID DESC;