✅ 23 회차 모의고사 D-08일
🚀 1차 코딩테스트 대비
- 백준 14503 (로봇 청소기)
- 백준 1010 (다리 놓기)
- 백준 11286 (절댓값 힙)
- 백준 1202 (보석 도둑)
- SQL 물고기 종류 별 잡은 수 구하기
1차 풀이
⭐ 1. 백준 14503 (로봇 청소기)
# 1. 알고(구현): 백준 14503 (로봇 청소기) - https://www.acmicpc.net/problem/14503
import sys
from io import StringIO
sys.stdin = StringIO('''11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
r, c, d = map(int, input().split())
wall = [tuple(map(int, input().split())) for _ in range(N)]
cleaned = [[False] * M for _ in range(N)]
directions = [(-1, 0), (0, +1), (+1, 0), (0, -1)]
clean_cnt = 0
while True:
if not cleaned[r][c]:
cleaned[r][c] = True
clean_cnt += 1
for i in range(1, 5):
temp_d = (d - i) % 4
dr, dc = directions[temp_d] # 진행 방향 반시계 방향 부터 조사.
nr, nc = r + dr, c + dc
if wall[nr][nc]:
continue
if not cleaned[nr][nc]:
r, c, d = nr, nc, temp_d # 전진, 방향 저장.
break
else: # 청소할 칸이 주변에 없으면
dr, dc = directions[(d + 2) % 4]
nr, nc = r + dr, c + dc
if wall[nr][nc]:
break
r, c = nr, nc
print(clean_cnt)
solve()⭐ 2. 백준 1010 (다리 놓기)
# 2. 알고(수학): 백준 1010 (다리 놓기) - https://www.acmicpc.net/problem/1010
import sys
from math import comb
from io import StringIO
sys.stdin = StringIO('''3
2 2
1 5
13 29''')
input = sys.stdin.readline
def solve():
T = int(input())
answer = []
for _ in range(T):
N, M = map(int, input().split())
answer.append(str(comb(M, N)))
print("\n".join(answer))
solve()⭐ 3. 백준 11286 (절댓값 힙)
# 3. 알고(Heap): 백준 11286 (절댓값 힙) - https://www.acmicpc.net/problem/11286
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0''')
input = sys.stdin.readline
def solve():
N = int(input())
out = []
pq = []
for _ in range(N):
num = int(input())
if not num:
out.append(str(heappop(pq)[1]) if pq else '0')
else:
heappush(pq, (abs(num), num))
print("\n".join(out))
solve()⭐ 4. 백준 1202 (보석 도둑)
# 4. 알고(그리디): 백준 1202 (보석 도둑) - https://www.acmicpc.net/problem/1202
import sys
from heapq import heappush, heappop
from io import StringIO
sys.stdin = StringIO('''3 2
1 65
5 23
2 99
10
2''')
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
jewels = sorted(tuple(map(int, input().split())) for _ in range(N))
bags = sorted(int(input()) for _ in range(K))
total_value = 0
jewel_idx = 0
pq = []
for can_bring in bags:
while True:
if jewel_idx == N:
break
weight, value = jewels[jewel_idx]
if weight > can_bring:
break
heappush(pq, -value)
jewel_idx += 1
if pq:
total_value += -heappop(pq)
print(total_value)
solve()✏️ 5. SQL 물고기 종류 별 잡은 수 구하기
-- 5. SQL(Lv.2): 물고기 종류 별 잡은 수 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/293257
SELECT
COUNT(*) AS FISH_COUNT,
FISH_NAME
FROM
FISH_INFO
JOIN
FISH_NAME_INFO USING (FISH_TYPE)
GROUP BY
FISH_TYPE, FISH_NAME
ORDER BY
FISH_COUNT DESC;🚀 2차 코딩테스트 대비
- 백준 20058 (마법사 상어와 파이어스톰)
- 백준 10942 (팰린드롬?)
- 백준 1516 (게임 개발)
- 백준 14889 (스타트와 링크)
- SQL 보호소에서 중성화한 동물
2차 풀이
⭐ 1. 백준 20058 (마법사 상어와 파이어스톰)
# 1. 알고(시뮬): 백준 20058 (마법사 상어와 파이어스톰) - https://www.acmicpc.net/problem/20058
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1''')
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
M = 2 ** N
board = [list(map(int, input().split())) for _ in range(M)]
levels = list(map(int, input().split()))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for L in levels:
sub_size = 2**L
new_board = [[0] * M for _ in range(M)]
# 배열 시계방향 회전
for r, c in product(range(0, M, sub_size), repeat=2): # 왼쪽 모서리
for i, j in product(range(sub_size), repeat=2):
new_board[r + j][c + sub_size-1 - i] = board[r+i][c+j]
melt_candi = []
for r, c in product(range(M), repeat=2):
if new_board[r][c] == 0:
continue
adjust_cnt = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
in_range = 0 <= nr < M and 0 <= nc < M
if in_range and new_board[nr][nc] > 0:
adjust_cnt += 1
if adjust_cnt < 3:
melt_candi.append((r, c))
for r, c in melt_candi:
new_board[r][c] -= 1
board = new_board
max_chunk = 0
visited = [[False] * M for _ in range(M)]
total_ice = sum(map(sum, board))
for r, c in product(range(M), repeat=2):
if board[r][c] == 0 or visited[r][c]:
continue
chunk = 1
visited[r][c] = True
stack = [(r, c)]
while stack:
cur_r, cur_c = stack.pop()
for dr, dc in directions:
nr, nc = cur_r + dr, cur_c + dc
in_range = 0 <= nr < M and 0 <= nc < M
if in_range and not visited[nr][nc] and board[nr][nc] > 0:
chunk += 1
visited[nr][nc] = True
stack.append((nr, nc))
max_chunk = max(max_chunk, chunk)
print(total_ice)
print(max_chunk)
solve()⭐ 2. 백준 10942 (팰린드롬?)
# 2. 알고(DP): 백준 10942 (팰린드롬?) - https://www.acmicpc.net/problem/10942
import sys
from io import StringIO
sys.stdin = StringIO('''7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = list(map(int, input().split()))
M = int(input())
# dp[i][j] i ~ j 까지 펠린드롬인지 여부
dp = [[0] * N for _ in range(N)]
for i in range(N - 1, -1, -1):
for j in range(i, N):
if nums[i] != nums[j]:
continue
if j - i < 2:
dp[i][j] = 1
elif dp[i + 1][j - 1]:
dp[i][j] = 1
answer = []
for _ in range(M):
S, E = map(int, input().split())
answer.append(str(dp[S - 1][E - 1]))
print("\n".join(answer))
solve()⭐ 3. 백준 1516 (게임 개발)
# 3. 알고(그래프): 백준 1516 (게임 개발) - https://www.acmicpc.net/problem/1516
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1''')
input = sys.stdin.readline
def solve():
N = int(input())
build_time = [0] * N # 건물 자체를 건설하는데 필요한 시간
graph = [[] for _ in range(N)]
in_degree = [0] * N # 건설하는데 필요한 건물 수
for i in range(N):
line = list(map(int, input().split()))
build_time[i] = line[0]
for pre in line[1:-1]:
graph[pre-1].append(i)
in_degree[i] += 1
dp = build_time[:] # dp[i] = i 완료 최소 시간 (자신 값으로 시작)
# 선수 건물 필요 없는 것 부터 조사.
dq = deque(i for i in range(N) if in_degree[i] == 0)
while dq:
cur = dq.popleft()
for nxt in graph[cur]:
dp[nxt] = max(dp[nxt], dp[cur] + build_time[nxt])
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
dq.append(nxt)
print("\n".join(map(str, dp)))
solve()⭐ 4. 백준 14889 (스타트와 링크)
# 4. 알고(백트래킹): 백준 14889 (스타트와 링크) - https://www.acmicpc.net/problem/14889
import sys
from itertools import combinations
from io import StringIO
sys.stdin = StringIO('''6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0''')
input = sys.stdin.readline
def solve():
N = int(input())
score = [tuple(map(int, input().split())) for _ in range(N)]
all_members = set(range(N))
min_diff = float('inf')
for comb in combinations(range(N - 1), (N - 2) // 2):
star_team = (N - 1,) + comb # 한명 고정
link_team = tuple(all_members.difference(star_team))
star_ability = sum(
score[a][b] + score[b][a]
for a, b in combinations(star_team, 2)
)
link_ability = sum(
score[a][b] + score[b][a]
for a, b in combinations(link_team, 2)
)
min_diff = min(min_diff, abs(star_ability - link_ability))
if min_diff == 0:
break
print(min_diff)
solve()✏️ 5. SQL 보호소에서 중성화한 동물
-- 5. SQL(Lv.4): 보호소에서 중성화한 동물
-- https://school.programmers.co.kr/learn/courses/30/lessons/59045
WITH
AIN AS (
SELECT
ANIMAL_ID,
ANIMAL_TYPE,
DATETIME AS IN_DATE_TIME
FROM
ANIMAL_INS
WHERE
SEX_UPON_INTAKE LIKE 'Intact%'
),
AOUT AS (
SELECT
ANIMAL_ID,
NAME,
DATETIME AS OUT_DATE_TIME
FROM
ANIMAL_OUTS
WHERE
SEX_UPON_OUTCOME LIKE 'Spayed%'
OR SEX_UPON_OUTCOME LIKE 'Neutered%'
)
SELECT
ANIMAL_ID,
ANIMAL_TYPE,
NAME
FROM AIN
JOIN AOUT USING (ANIMAL_ID)
WHERE
IN_DATE_TIME <= OUT_DATE_TIME
ORDER BY
ANIMAL_ID