✅ 06 회차 모의고사 D-25일
🚀 1차 코딩테스트 대비
- 백준 2567 (색종이 - 2)
- 백준 1004 (어린 왕자)
- 백준 7785 (회사에 있는 사람)
- 백준 1449 (수리공 항승)
- SQL 중성화 여부 파악하기
1차 풀이
⭐ 1. 백준 2567 (색종이 - 2)
# 1. 알고(구현): 백준 2567 (색종이 - 2) - https://www.acmicpc.net/problem/2567
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''4
3 7
5 2
15 7
13 14''')
input = sys.stdin.readline
def solve():
board = [[0] * 102 for _ in range(102)]
dirs = ((0, +1), (0, -1), (+1, 0), (-1, 0))
N = int(input())
min_r, min_c = 100, 100
max_r, max_c = 0, 0
for _ in range(N):
r, c = map(int, input().split())
# 최대 최소 범위 찾기
min_r, min_c = min(min_r, r), min(min_c, c)
max_r, max_c = max(max_r, r), max(max_c, c)
for i in range(r, r + 10):
for j in range(c, c + 10):
board[i][j] = 1
r_range = range(min_r, max_r + 11)
c_range = range(min_c, max_c + 11)
edge_length = 0
for r, c in product(r_range, c_range):
if board[r][c] == 1:
for dr, dc in dirs:
if board[r + dr][c + dc] == 0:
edge_length += 1
print(edge_length)
solve()⭐ 2. 백준 1004 (어린 왕자)
# 2. 알고(수학): 백준 1004 (어린 왕자) - https://www.acmicpc.net/problem/1004
import sys
from io import StringIO
sys.stdin = StringIO('''2
-5 1 12 1
7
1 1 8
-3 -1 1
2 2 2
5 5 1
-4 5 1
12 1 1
12 1 2
-5 1 5 1
1
0 0 2''')
input = sys.stdin.readline
def get_dist_sq(x1, y1, x2, y2):
return (x2 - x1)**2 + (y2 - y1)**2
def solve():
sx, sy, ex, ey = map(int, input().split())
N = int(input())
count = 0
for _ in range(N):
x, y, r = map(int, input().split())
r_sq = r ** 2
start_in_circle = get_dist_sq(sx, sy, x, y) < r_sq
end_in_circle = get_dist_sq(ex, ey, x, y) < r_sq
if start_in_circle != end_in_circle:
count += 1
print(count)
T = int(input())
for _ in range(T):
solve()⭐ 3. 백준 7785 (회사에 있는 사람)
# 3. 알고(Map): 백준 7785 (회사에 있는 사람) - https://www.acmicpc.net/problem/7785
import sys
from io import StringIO
sys.stdin = StringIO('''4
Baha enter
Askar enter
Baha leave
Artem enter''')
input = sys.stdin.readline
def solve():
N = int(input())
working = set()
for _ in range(N):
name, info = input().rsplit()
if info == 'enter':
working.add(name)
else:
working.discard(name)
existing = list(working)
existing.sort(reverse=True)
print("\n".join(existing))
solve()⭐ 4. 백준 1449 (수리공 항승)
# 4. 알고(그리디): 백준 1449 (수리공 항승) - https://www.acmicpc.net/problem/1449
import sys
from io import StringIO
sys.stdin = StringIO('''4 3
1 2 3 4''')
input = sys.stdin.readline
def solve():
N, L = map(int, input().split())
leaks = list(map(int, input().split()))
leaks.sort()
count = 0
last_fix = 0 # 마지막 수리 지점
for location in leaks:
if location > last_fix:
count += 1
last_fix = location + L - 1
print(count)
solve()✏️ 5. SQL 중성화 여부 파악하기
-- 5. SQL(Lv.2): 중성화 여부 파악하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/59409
SELECT
ANIMAL_ID,
NAME,
CASE
WHEN
SEX_UPON_INTAKE LIKE '%Neutered%'
OR SEX_UPON_INTAKE LIKE '%Spayed%'
THEN 'O'
ELSE 'X'
END AS 중성화
FROM
ANIMAL_INS
ORDER BY
ANIMAL_ID;🚀 2차 코딩테스트 대비
- 백준 14502 (연구소)
- 백준 2293 (동전 1)
- 백준 14938 (서강그라운드)
- 백준 15684 (사다리 조작)
- SQL 즐겨찾기가 가장 많은 식당 정보 출력하기
2차 풀이
⭐ 1. 백준 14502 (연구소)
# 1. 알고(시뮬): 백준 14502 (연구소) - https://www.acmicpc.net/problem/14502
import sys
from itertools import product, combinations
from collections import deque
from io import StringIO
sys.stdin = StringIO('''7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
room = [[1] * (M + 2)]
for _ in range(N):
room.append([1] + list(map(int, input().split())) + [1])
room.append([1] * (M + 2))
directions = [(0, +1), (0, -1), (-1, 0), (+1, 0)]
virus = []
emptys = []
# 바이러스 & 빈공간 위치 탐지
for r, c in product(range(1, N + 1), range(1, M + 1)):
if room[r][c] == 2:
virus.append((r, c))
elif room[r][c] == 0:
emptys.append((r, c))
emptys_size = len(emptys)
# 바이러스 중심으로 확산 후, 감염 안된 셀 개수 찾기.
def virus_start(three_wall_set):
injected_set = set()
dq = deque(virus) # 모든 바이러스 넣고 시작
while dq:
r, c = dq.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if room[nr][nc] == 0: # 빈칸이고, 감염아직 안되고, 추가된 벽이 아니면
nxt_rc = (nr, nc)
if nxt_rc not in injected_set \
and nxt_rc not in three_wall_set:
dq.append(nxt_rc)
injected_set.add(nxt_rc)
return emptys_size - len(injected_set) - len(three_wall_set)
# 벽 세울 후보군 선정, 컴비네이션으로 3개 세우고 확산
max_val = 0
for three_wall in combinations(emptys, 3):
empty_val = virus_start(set(three_wall))
max_val = max(max_val, empty_val)
print(max_val)
solve()⭐ 2. 백준 2293 (동전 1)
# 2. 알고(DP): 백준 2293 (동전 1) - https://www.acmicpc.net/problem/2293
import sys
from io import StringIO
sys.stdin = StringIO('''3 10
1
2
5''')
input = sys.stdin.readline
def solve():
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
# dp[i] = i원을 만들 수 있는 경우의 수
dp = [0] * (k+1)
dp[0] = 1
for coin in coins:
for i in range(coin, k + 1):
# 코인을 안쓰고 기존 방식 + 코인을 쓰고 가격을 추가한 방식
dp[i] += dp[i - coin]
print(dp[k])
solve()⭐ 3. 백준 14938 (서강그라운드)
# 3. 알고(그래프): 백준 14938 (서강그라운드) - https://www.acmicpc.net/problem/14938
import sys
from heapq import heappush, heappop
from io import StringIO
sys.stdin = StringIO('''5 5 4
5 7 8 2 3
1 4 5
5 2 4
3 2 3
1 2 3''')
input = sys.stdin.readline
def solve():
n, m, r = map(int, input().split())
items = tuple(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(r):
s, e, c = map(int, input().split())
graph[s].append((e, c))
graph[e].append((s, c))
# 방문한 노드의 아이템 총 합계
def check_items(start):
min_dist = [float('inf')] * (n + 1)
min_dist[start] = 0
pq = [(0, start)]
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]:
heappush(pq, (nxt_dist, nxt))
min_dist[nxt] = nxt_dist
# 다익스트라로 모두 조사한 한뒤 필터
can_visit = [v for v in range(1, n + 1) if min_dist[v] <= m]
return sum(map(lambda x: items[x - 1], can_visit))
max_val = 0
for start in range(1, n + 1):
sum_val = check_items(start)
if sum_val > max_val:
max_val = sum_val
print(max_val)
solve()⭐ 4. 백준 15684 (사다리 조작)
# 4. 알고(백트래킹): 백준 15684 (사다리 조작) - https://www.acmicpc.net/problem/15684
import sys
from io import StringIO
sys.stdin = StringIO('''5 5 6
1 1
3 2
2 3
5 1
5 4''')
input = sys.stdin.readline
def solve():
N, M, H = map(int, input().split())
# 패딩을 포함한 사다리 맵 (N+2)
board = [[False] * (N + 2) for _ in range(H + 1)]
for _ in range(M):
a, b = map(int, input().split())
board[a][b] = True
# 사다리 놓을 수 있는 후보지 미리 추출
candidates = []
for i in range(1, H + 1):
for j in range(1, N):
if not board[i][j] and not board[i][j-1] and not board[i][j+1]:
candidates.append((i, j))
# 현재 상태에서 결과가 다른 세로선의 개수 카운트
def count_wrong():
wrong = 0
for start in range(1, N + 1):
curr = start
for h in range(1, H + 1):
if board[h][curr]:
curr += 1
elif board[h][curr-1]:
curr -= 1
if curr != start:
wrong += 1
return wrong
def dfs(cnt, target, idx):
wrong_cnt = count_wrong()
if wrong_cnt == 0:
return True
# [가지치기] 남은 기회로 틀린 선을 모두 고칠 수 없는 경우
if wrong_cnt > 2 * (target - cnt):
return False
if cnt == target:
return False
for i in range(idx, len(candidates)):
r, c = candidates[i]
# 인접한 곳에 사다리가 없을 때만 설치
if not board[r][c-1] and not board[r][c+1]:
board[r][c] = True
if dfs(cnt + 1, target, i + 1):
return True
board[r][c] = False
return False
# 0개부터 3개까지 순차 시도
for limit in range(4):
if dfs(0, limit, 0):
print(limit)
return
print(-1)
solve()✏️ 5. SQL 즐겨찾기가 가장 많은 식당 정보 출력하기
-- 5. SQL(Lv.3): 즐겨찾기가 가장 많은 식당 정보 출력하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/131123
SELECT
FOOD_TYPE,
REST_ID,
REST_NAME,
FAVORITES
FROM
REST_INFO
WHERE
(FOOD_TYPE, FAVORITES) IN (
SELECT
FOOD_TYPE,
MAX(FAVORITES)
FROM
REST_INFO
GROUP BY
FOOD_TYPE
)
ORDER BY
FOOD_TYPE DESC;