✅ 07 회차 모의고사 D-24일
🚀 1차 코딩테스트 대비
- 백준 13335 (트럭)
- 백준 1057 (토너먼트)
- 백준 1764 (듣보잡)
- 백준 11000 (강의실 배정)
- SQL 카테고리 별 상품 개수 구하기
1차 풀이
⭐ 1. 백준 13335 (트럭)
# 1. 알고(구현): 백준 13335 (트럭) - https://www.acmicpc.net/problem/13335
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''4 2 10
7 4 5 6''')
input = sys.stdin.readline
def solve():
n, w, L = map(int, input().split())
trucks = deque(map(int, input().split()))
bridge = deque([0] * w)
time = 1
cur_weight = trucks.popleft()
bridge.append(cur_weight) # 다리위에 올리고
bridge.popleft() # 다리에서 하나 뺴고
while trucks:
time += 1
cur_weight -= bridge.popleft()
# 다리 올라갈 수 있으면
if cur_weight + trucks[0] <= L:
truck = trucks.popleft()
bridge.append(truck) # 다리 위에 올리고
cur_weight += truck # 다리 중량 추가하고
else: # 못 올라가면
bridge.append(0) # 빈공간 추가
print(time + w)
solve()⭐ 2. 백준 1057 (토너먼트)
# 2. 알고(수학): 백준 1057 (토너먼트) - https://www.acmicpc.net/problem/1057
import sys
from io import StringIO
sys.stdin = StringIO('''65536 1000 35000''')
input = sys.stdin.readline
def solve():
N, kim, eim = map(int, input().split())
count = 0
while kim != eim:
count += 1
kim = (kim + 1) // 2
eim = (eim + 1) // 2
print(count)
solve()⭐ 3. 백준 1764 (듣보잡)
# 3. 알고(Map): 백준 1764 (듣보잡) - https://www.acmicpc.net/problem/1764
import sys
from io import StringIO
sys.stdin = StringIO('''3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
not_heard = set([input().rstrip() for _ in range(N)])
not_seen = set([input().rstrip() for _ in range(M)])
not_seens_heard = list(not_heard.intersection(not_seen))
not_seens_heard.sort()
print(len(not_seens_heard))
print("\n".join(not_seens_heard))
solve()⭐ 4. 백준 11000 (강의실 배정)
# 4. 알고(그리디): 백준 11000 (강의실 배정) - https://www.acmicpc.net/problem/11000
import sys
from collections import deque
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''3
1 3
2 4
3 5''')
input = sys.stdin.readline
def solve():
N = int(input())
lectures = [tuple(map(int, input().split())) for _ in range(N)]
lectures.sort()
dq = deque(lectures)
pq_rooms = [] # (끝나는 시간, [(),()] 튜플 배열) - 첫 수업 배정
while dq:
start, end = dq.popleft() # 수강 신청할 수업
# 룸이 비어있거나, 제일 빨리 끝나는 방의 종료시간이 시작시간보다 크면
if not pq_rooms or pq_rooms[0][0] > start:
heappush(pq_rooms, (end, [(start, end)])) # 새 강의실 배정
else:
_, letures = heappop(pq_rooms)
letures.append((start, end)) # 강의실 추가하고
heappush(pq_rooms, (end, letures)) # 종료시간 갱신해서 재 삽입
print(len(pq_rooms))
solve()✏️ 5. SQL 카테고리 별 상품 개수 구하기
-- 5. SQL(Lv.2): 카테고리 별 상품 개수 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/131529
SELECT
LEFT(PRODUCT_CODE, 2) AS CATEGORY,
COUNT(*) AS PRODUCTS
FROM
PRODUCT
GROUP BY
CATEGORY
ORDER BY
CATEGORY;🚀 2차 코딩테스트 대비
- 백준 21608 (상어 초등학교)
- 백준 11066 (파일 합치기)
- 백준 11404 (플로이드)
- 백준 17136 (색종이 붙이기)
- SQL 대여 기록이 존재하는 자동차 리스트 구하기
2차 풀이
⭐ 1. 백준 21608 (상어 초등학교)
# 1. 알고(시뮬): 백준 21608 (상어 초등학교) - https://www.acmicpc.net/problem/21608
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''3
4 2 5 1 7
3 1 9 4 5
9 8 1 2 3
8 1 9 3 4
7 2 3 4 8
1 9 2 5 7
6 5 2 3 4
5 1 9 2 8
2 9 3 1 4''')
input = sys.stdin.readline
def solve():
N = int(input())
directions = [(-1, 0), (+1, 0), (0, -1), (0, +1)]
room = [[-1] * (N + 2)]
for _ in range(N):
room.append([-1] + ([0] * N) + [-1])
room.append([-1] * (N + 2))
empty_set = set((r, c) for r in range(1, N+1) for c in range(1, N+1))
likeinfo = [tuple(map(int, input().split())) for _ in range(N*N)]
student_sits = dict()
# 좌석값 리턴
def find_set(a, b, c, d):
likes = set([a, b, c, d])
candi_pq = [] # heap 으로 (-like, -empty, 행, 열) 순서 항상 유지.
for r, c in empty_set:
like_count = 0
empty_count = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
sit_val = room[nr][nc]
if sit_val == 0:
empty_count += 1
elif sit_val in likes:
like_count += 1
heappush(candi_pq, (-like_count, -empty_count, r, c))
_, _, fr, fc = heappop(candi_pq)
return fr, fc
# 학생 배치 시작
for num, a, b, c, d in likeinfo:
fr, fc = find_set(a, b, c, d)
room[fr][fc] = num
student_sits[num] = (fr, fc) # 학생 위치 기록.
empty_set.remove((fr, fc))
# 점수 계산
sum_val = 0
for num, a, b, c, d in likeinfo:
likes = set([a, b, c, d])
r, c = student_sits[num]
like_count = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
if room[nr][nc] in likes:
like_count += 1
if like_count > 0:
sum_val += 10**(like_count - 1)
print(sum_val)
solve()⭐ 2. 백준 11066 (파일 합치기)
# 2. 알고(DP): 백준 11066 (파일 합치기) - https://www.acmicpc.net/problem/11066
import sys
from io import StringIO
sys.stdin = StringIO('''2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32''')
input = sys.stdin.readline
def solve():
K = int(input())
files = tuple(map(int, input().split()))
S = [0] * (K+1)
for i in range(K):
S[i+1] = S[i] + files[i]
# dp[i][j] = i 부터 j 까지 합치는 최소 비용
# dp[i][j] = dp[i][k] + dp[k+1][j] + sum(i ~ k)
# k[i][j] = i 부터 j까지 합칠 때 최소였던 k(중간) 값 저장
dp = [[0]*K for _ in range(K)]
kp = [[0]*K for _ in range(K)]
# 초기값 세팅
for i in range(K - 1):
kp[i][i+1] = i
dp[i][i+1] = files[i] + files[i+1]
for length in range(3, K + 1):
for i in range(K - length + 1):
j = i + length - 1
best_k = 0
min_cost = float('inf')
start_k = kp[i][j-1]
end_k = kp[i+1][j]
for k in range(start_k, end_k + 1):
best_cost = dp[i][k] + dp[k+1][j]
if best_cost < min_cost:
best_k = k
min_cost = best_cost
dp[i][j] = min_cost + (S[j + 1] - S[i])
kp[i][j] = best_k
print(dp[0][K-1])
T = int(input())
for _ in range(T):
solve()⭐ 3. 백준 11404 (플로이드)
# 3. 알고(그래프): 백준 11404 (플로이드) - https://www.acmicpc.net/problem/11404
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4''')
input = sys.stdin.readline
def solve():
n = int(input())
m = int(input())
# min_dist[i][j] => i 에서 j 로 가는 최단거리
dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]
indexs = tuple(product(range(1, n + 1), repeat=2))
for i in range(1, n + 1):
dist[i][i] = 0
for _ in range(m):
s, e, c = map(int, input().split())
dist[s][e] = min(dist[s][e], c)
# 플로이드 워셜
for k in range(1, n + 1):
for i, j in indexs:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
for row in dist[1:]:
print(*[num if num != float('inf') else 0 for num in row[1:]])
solve()⭐ 4. 백준 17136 (색종이 붙이기)
# 4. 알고(백트래킹): 백준 17136 (색종이 붙이기) - https://www.acmicpc.net/problem/17136
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 0 0 0 0 1''')
input = sys.stdin.readline
def solve():
board = [list(map(int, input().split())) for _ in range(10)]
paper = [0, 5, 5, 5, 5, 5]
min_paper = float('inf')
def is_possible(r, c, length):
if r + length > 10 or c + length > 10:
return False
for i in range(r, r + length):
for j in range(c, c + length):
if board[i][j] == 0:
return False
return True
def mark(r, c, length, val):
for i, j in product(range(r, r + length), range(c, c + length)):
board[i][j] = val
def dfs(row, col, spend_paper):
nonlocal min_paper
if row >= 10: # 가능한 색종이 다 붙임
min_paper = min(min_paper, spend_paper)
return
if col >= 10: # 다음 row 조사. col 초기화
dfs(row + 1, 0, spend_paper)
return
if spend_paper >= min_paper: # 최소 종이보다 더 많이 필요하면 가지치기
return
if board[row][col] == 1: # 1이면 조사,
for length in range(5, 0, -1):
if paper[length] > 0 and is_possible(row, col, length):
mark(row, col, length, 0)
paper[length] -= 1
dfs(row, col + 1, spend_paper + 1)
paper[length] += 1
mark(row, col, length, 1)
else: # 0이면 오른쪽 칸 이동
dfs(row, col + 1, spend_paper)
dfs(0, 0, 0)
print(min_paper if min_paper != float('inf') else -1)
solve()✏️ 5. SQL 대여 기록이 존재하는 자동차 리스트 구하기
--5. SQL(Lv.3): 대여 기록이 존재하는 자동차 리스트 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/157341
SELECT
DISTINCT C.CAR_ID
FROM
CAR_RENTAL_COMPANY_CAR C
JOIN
CAR_RENTAL_COMPANY_RENTAL_HISTORY H
ON C.CAR_ID = H.CAR_ID
WHERE
C.CAR_TYPE = '세단'
AND MONTH(H.START_DATE) = 10
ORDER BY
C.CAR_ID DESC;