✅ 21 회차 모의고사 D-10일
🚀 1차 코딩테스트 대비
- 백준 2493 (탑)
- 백준 1011 (Fly me to the Alpha Centauri)
- 백준 1253 (좋다)
- 백준 1715 (카드 정렬하기)
- SQL 노선별 평균 역 사이 거리 조회하기
1차 풀이
⭐ 1. 백준 2493 (탑)
# 1. 알고(구현): 백준 2493 (탑) - https://www.acmicpc.net/problem/2493
import sys
from io import StringIO
sys.stdin = StringIO('''5
6 9 5 7 4''')
input = sys.stdin.readline
def solve():
N = int(input())
heights = list(map(int, input().split()))
stack = list()
answer = [0] * N
for i, cur_h in enumerate(heights):
while stack and stack[-1][0] < cur_h: # 단조스택, 내림차순유지
stack.pop()
answer[i] = stack[-1][1] if stack else 0
stack.append((cur_h, i + 1)) # 인덱스 소절
print(*answer)
solve()⭐ 2. 백준 1011 (Fly me to the Alpha Centauri)
# 2. 알고(수학): 백준 1011 (Fly me to the Alpha Centauri) - https://www.acmicpc.net/problem/1011
import sys
from math import isqrt
from io import StringIO
sys.stdin = StringIO('''3
0 3
1 5
45 50''')
input = sys.stdin.readline
def solve():
x, y = map(int, input().split())
distance = y - x
n = isqrt(distance) # n: 도달 가능한 최대 속도
base = n * n # base: 최대 속도 n을 찍었을 때의 기본 이동 거리 (n^2)
# 패턴 1: 완벽한 대칭 피라미드 (예: 1, 2, 1)
if distance == base:
return print(2*n - 1)
# 패턴 2: 거리가 살짝 남아 이동 횟수 1번 추가
if base < distance <= base + n:
return print(2*n)
# 패턴 3: 거리가 많이 남아 이동 횟수 2번 추가
if base + n < distance < (n+1)**2:
return print(2*n + 1)
T = int(input())
for _ in range(T):
solve()⭐ 3. 백준 1253 (좋다)
# 3. 알고(Map): 백준 1253 (좋다) - https://www.acmicpc.net/problem/1253
import sys
from io import StringIO
sys.stdin = StringIO('''10
1 2 3 4 5 6 7 8 9 10''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = sorted(map(int, input().split()))
good_cnt = 0
for i in range(N):
base = nums[i]
left, right = 0, N - 1
while left < right:
if left == i:
left += 1
continue
if right == i:
right -= 1
continue
target = nums[left] + nums[right]
if target == base:
good_cnt += 1
break
elif target > base:
right -= 1
else:
left += 1
print(good_cnt)
solve()⭐ 4. 백준 1715 (카드 정렬하기)
# 4. 알고(그리디): 백준 1715 (카드 정렬하기) - https://www.acmicpc.net/problem/1715
import sys
from heapq import heappop, heappush, heapify
from io import StringIO
sys.stdin = StringIO('''3
10
20
40''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = [int(input()) for _ in range(N)]
heapify(nums)
cnt_sum = 0
while len(nums) >= 2:
two_sum = heappop(nums) + heappop(nums)
cnt_sum += two_sum
heappush(nums, two_sum)
print(cnt_sum)
solve()✏️ 5. SQL 노선별 평균 역 사이 거리 조회하기
-- 5. SQL(Lv.2): 노선별 평균 역 사이 거리 조회하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/284531
SELECT
ROUTE,
CONCAT(ROUND(SUM(D_BETWEEN_DIST), 1), 'km') AS TOTAL_DISTANCE,
CONCAT(ROUND(AVG(D_BETWEEN_DIST), 2), 'km') AS AVERAGE_DISTANCE
FROM
SUBWAY_DISTANCE
GROUP BY
ROUTE
ORDER BY
SUM(D_BETWEEN_DIST) DESC;🚀 2차 코딩테스트 대비
- 백준 21610 (마법사 상어와 비바라기)
- 백준 15486 (퇴사 2)
- 백준 1753 (최단경로)
- 백준 16987 (계란으로 계란치기)
- SQL 조건에 맞는 사용자 정보 조회하기
2차 풀이
⭐ 1. 백준 21610 (마법사 상어와 비바라기)
# 1. 알고(시뮬): 백준 21610 (마법사 상어와 비바라기) - https://www.acmicpc.net/problem/21610
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8''')
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), (-1, -1), (-1, 0), (-1, +1),
(0, +1), (+1, +1), (+1, 0), (+1, -1)
]
clouds = set([
(N-1, 0), (N-1, 1),
(N-2, 0), (N-2, 1)
])
for _ in range(M):
d, s = map(int, input().split())
dr, dc = directions[d-1]
add_water = set()
for cr, cc in clouds:
nr, nc = (cr + dr*s) % N, (cc + dc*s) % N
board[nr][nc] += 1
add_water.add((nr, nc))
clouds.clear()
for wr, wc in add_water:
for i in range(0, 8, 2):
dr, dc = directions[i+1]
nr, nc = wr + dr, wc + dc
in_range = 0 <= nr < N and 0 <= nc < N
if in_range and board[nr][nc] != 0:
board[wr][wc] += 1
for r, c in product(range(N), repeat=2):
if (r, c) not in add_water and board[r][c] >= 2:
clouds.add((r, c))
board[r][c] -= 2
print(sum(map(sum, board)))
solve()⭐ 2. 백준 15486 (퇴사 2)
# 2. 알고(DP): 백준 15486 (퇴사 2) - https://www.acmicpc.net/problem/15486
import sys
from io import StringIO
sys.stdin = StringIO('''10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50''')
input = sys.stdin.readline
def solve():
N = int(input())
plans = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0] * (N + 1) # dp[i] = i 일까지 얻을 수 있는 최대 수익
for i in range(N):
day, profit = plans[i]
dp[i + 1] = max(dp[i + 1], dp[i]) # 상담 건너뛰기
due_day = i + day
if due_day <= N: # 상담 끝나는 날 벌 수익보다 크면 갱신
dp[due_day] = max(dp[due_day], dp[i] + profit) # Forward DP
print(dp[N])
solve()⭐ 3. 백준 1753 (최단경로)
# 3. 알고(그래프): 백준 1753 (최단경로) - https://www.acmicpc.net/problem/1753
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6''')
input = sys.stdin.readline
def solve():
V, E = map(int, input().split())
S = int(input()) - 1
graph = [[] for _ in range(V)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u-1].append((v-1, w)) # 0 index
pq = [(0, S)] # 거리
min_dist = [float('inf')] * V
min_dist[S] = 0
while pq:
cur_dist, cur = heappop(pq)
if cur_dist > min_dist[cur]:
continue
for nxt, cost in graph[cur]:
nxt_dist = cur_dist + cost
if nxt_dist >= min_dist[nxt]:
continue
min_dist[nxt] = nxt_dist
heappush(pq, (nxt_dist, nxt))
print("\n".join(
'INF' if dist == float('inf') else str(dist)
for dist in min_dist
))
solve()⭐ 4. 백준 16987 (계란으로 계란치기)
# 4. 알고(백트래킹): 백준 16987 (계란으로 계란치기) - https://www.acmicpc.net/problem/16987
import sys
from io import StringIO
sys.stdin = StringIO('''8
222 117
176 92
287 6
284 81
221 96
263 96
188 40
225 1''')
input = sys.stdin.readline
def solve():
N = int(input())
eggs = [list(map(int, input().split())) for _ in range(N)]
max_broken = 0
def dfs(hand_idx): # 손에 들 계란 인덱스
nonlocal max_broken
if hand_idx == N: # 끝까지 고려 한 뒤.
cur_broken = sum(s <= 0 for s, _ in eggs)
max_broken = max(max_broken, cur_broken)
return
if eggs[hand_idx][0] <= 0: # 손에 들 계란이 깨진계란
dfs(hand_idx + 1)
return
for target in range(N): # 칠 계란이 있는지 조사.
if target != hand_idx and eggs[target][0] > 0:
break # 칠 계란 하나라도 남아있으면 탈출
else:
dfs(hand_idx + 1) # 다 깨졌으면 hand_idx == N 까지 보냄
return
for target in range(N):
if target == hand_idx or eggs[target][0] <= 0:
continue # 깨졌거나, 자기 자신 인덱스는 통과
hand_egg = eggs[hand_idx]
target_egg = eggs[target]
hand_egg[0] -= target_egg[1]
target_egg[0] -= hand_egg[1]
dfs(hand_idx + 1)
hand_egg[0] += target_egg[1]
target_egg[0] += hand_egg[1]
dfs(0)
print(max_broken)
solve()✏️ 5. SQL 조건에 맞는 사용자 정보 조회하기
-- 5. SQL(Lv.3): 조건에 맞는 사용자 정보 조회하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/164670
WITH U AS (
SELECT
WRITER_ID AS USER_ID
FROM
USED_GOODS_BOARD
GROUP BY
WRITER_ID
HAVING
COUNT(*) >= 3
)
SELECT
USER_ID,
NICKNAME,
CONCAT(
CITY, ' ',
STREET_ADDRESS1, ' ',
STREET_ADDRESS2
) AS `전체주소`,
CONCAT(
SUBSTR(TLNO,1,3), '-',
SUBSTR(TLNO, 4, 4), '-',
SUBSTR(TLNO,8,4)
) AS `전화번호`
FROM U
JOIN USED_GOODS_USER USING (USER_ID)
ORDER BY
USER_ID DESC;