✅ 16 회차 모의고사 D-15일
🚀 1차 코딩테스트 대비
- 백준 16926 (배열 돌리기 1)
- 백준 1748 (수 이어 쓰기 1)
- 백준 5568 (카드 놓기)
- 백준 1092 (배)
- SQL 조건에 맞는 도서와 저자 리스트 출력하기
1차 풀이
⭐ 1. 백준 16926 (배열 돌리기 1)
# 1. 알고(구현): 백준 16926 (배열 돌리기 1) - https://www.acmicpc.net/problem/16926
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28''')
input = sys.stdin.readline
def solve():
N, M, R = map(int, input().split())
board = [list(input().split()) for _ in range(N)]
directions = [(+1, 0), (0, +1), (-1, 0), (0, -1)]
for layer in range(min(N, M) // 2):
sr, er = 0 + layer, N - 1 - layer # 경계 값
sc, ec = 0 + layer, M - 1 - layer
r, c = sr, sc
row_col = list()
value_dq = deque()
d = 0
while True:
dr, dc = directions[d]
nr, nc = r + dr, c + dc
if sr <= nr <= er and sc <= nc <= ec:
row_col.append((nr, nc))
value_dq.append(board[nr][nc])
r, c = nr, nc
if (r, c) == (sr, sc): # 시작위치 오면 탈출
break
else:
d = (d + 1) % 4
value_dq.rotate(R) # 회전 시킨 값
for new_r, new_c in row_col:
board[new_r][new_c] = value_dq.popleft()
for row in board:
print(*row)
solve()⭐ 2. 백준 1748 (수 이어 쓰기 1)
# 2. 알고(수학): 백준 1748 (수 이어 쓰기 1) - https://www.acmicpc.net/problem/1748
import sys
from io import StringIO
sys.stdin = StringIO('''120''')
input = sys.stdin.readline
def solve():
N = int(input())
answer = 0
start = 1
length = 1
while start <= N: # n자리수 * ( n자리수 중 가장 큰 수 - 가장 작은 수 +1 )
end = min(N, 10**length - 1)
answer += length * (end - start + 1)
start *= 10
length += 1
print(answer)
solve()⭐ 3. 백준 5568 (카드 놓기)
# 3. 알고(Map): 백준 5568 (카드 놓기) - https://www.acmicpc.net/problem/5568
import sys
from itertools import permutations
from io import StringIO
sys.stdin = StringIO('''6
3
72
2
12
7
2
1''')
input = sys.stdin.readline
def solve():
n, k = int(input()), int(input())
nums = (input().rstrip() for _ in range(n))
answers = {"".join(p) for p in permutations(nums, k)}
print(len(answers))
solve()⭐ 4. 백준 1092 (배)
# 4. 알고(그리디): 백준 1092 (배) - https://www.acmicpc.net/problem/1092
import sys
from bisect import bisect
from io import StringIO
sys.stdin = StringIO('''3
6 8 9
5
2 5 2 4 7''')
input = sys.stdin.readline
def solve():
N = int(input())
crains = sorted(map(int, input().split()), reverse=True)
M = int(input())
weights = sorted(map(int, input().split()))
if crains[0] < weights[-1]: # 제일 강한 크레인이 못드는 무게가 있으면
print(-1)
return
time = 0
while weights:
for i, can in enumerate(crains):
can_move_idx = bisect(weights, can) # 2진 탐색
if can_move_idx == 0: # 들 수 있는 무게가 없을 때
del crains[i:] # 이후 크레인 모두 제거
break
else:
del weights[can_move_idx-1] # 들 수 있는 무게 중 가장 무거운거 제거
time += 1
print(time)
solve()✏️ 5. SQL 조건에 맞는 도서와 저자 리스트 출력하기
-- 5. SQL(Lv.2): 조건에 맞는 도서와 저자 리스트 출력하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/144854
WITH
CG AS (
SELECT
BOOK_ID,
AUTHOR_ID,
PUBLISHED_DATE
FROM BOOK
WHERE CATEGORY = '경제'
)
SELECT
CG.BOOK_ID,
A.AUTHOR_NAME,
DATE_FORMAT(CG.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE
FROM CG
JOIN AUTHOR A USING (AUTHOR_ID)
ORDER BY PUBLISHED_DATE ASC;🚀 2차 코딩테스트 대비
- 백준 16236 (아기 상어)
- 백준 11055 (가장 큰 증가하는 부분 수열)
- 백준 17396 (백도어)
- 백준 1405 (미친 로봇)
- SQL 없어진 기록 찾기
2차 풀이
⭐ 1. 백준 16236 (아기 상어)
# 1. 알고(시뮬): 백준 16236 (아기 상어) - https://www.acmicpc.net/problem/16236
import sys
from heapq import heappush, heappop
from itertools import product
from collections import deque
from io import StringIO
sys.stdin = StringIO('''6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1''')
input = sys.stdin.readline
def solve():
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
directions = [(0, +1), (0, -1), (+1, 0), (-1, 0)]
baby = [2, 0, 0, 0] # 크기, r, c, 먹은 물고기 수
for r, c in product(range(N), repeat=2):
value = board[r][c]
if value == 9:
baby[1:3] = r, c
board[r][c] = 0 # 제거 안하면 벽이 되어버림
time = 0
while True: # 크기가 가장 작은 물고기가 사냥 가능하다면
b_size, br, bc, eat_cnt = baby
# 아기 위치 기준으로 사냥 가능한 물고기 거리 측정, BFS
min_dist = [[-1] * N for _ in range(N)]
target_fishs = list()
dq = deque([(br, bc)])
min_dist[br][bc] = 0
best_min_dist = float('inf')
while dq:
r, c = dq.popleft()
nxt_dist = min_dist[r][c] + 1
if nxt_dist > best_min_dist: # 최단거리까지만 탐색
break
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and min_dist[nr][nc] == -1:
val = board[nr][nc]
if val <= b_size: # 사이즈가 아기보다 작거나 같으면 무시 하고 진행
dq.append((nr, nc))
min_dist[nr][nc] = nxt_dist
if 0 < board[nr][nc] < b_size: # 먹을 수 있다면 후보 선정
heappush(target_fishs, (nxt_dist, nr, nc))
if best_min_dist == float('inf'): # 한번만 갱신
best_min_dist == nxt_dist
if not target_fishs: # 후보 없으면 종료
break
eat_dist, er, ec = heappop(target_fishs) # 제일 앞에 것 이 타겟.
time += eat_dist # 거리 만큼 시간 쓰고
eat_cnt += 1 # 먹은 수 증가
board[er][ec] = 0
if eat_cnt == b_size: # 현재 사이즈 만큼 먹었으면
eat_cnt = 0 # 먹은 수 갱신
b_size += 1 # 성장
baby = b_size, er, ec, eat_cnt # 아기 정보 갱신
print(time)
solve()⭐ 2. 백준 11055 (가장 큰 증가하는 부분 수열)
# 2. 알고(DP): 백준 11055 (가장 큰 증가하는 부분 수열) - https://www.acmicpc.net/problem/11055
import sys
from io import StringIO
sys.stdin = StringIO('''10
1 100 2 50 60 3 5 6 7 8''')
input = sys.stdin.readline
def solve():
N = int(input())
A = list(map(int, input().split()))
dp = A[:]
for i in range(N):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + A[i])
print(max(dp))
solve()⭐ 3. 백준 17396 (백도어)
# 3. 알고(그래프): 백준 17396 (백도어) - https://www.acmicpc.net/problem/17396
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''5 7
0 0 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
vision = list(map(int, input().split()))
vision[N-1] = 0
graph = [[] for _ in range(N)]
for _ in range(M):
a, b, c = map(int, input().split())
if vision[a] == 0 and vision[b] == 0:
graph[a].append((b, c))
graph[b].append((a, c))
min_time = [float('inf')] * N
pq = [(0, 0)] # (시간, 분기점)
min_time[0] = 0
while pq:
cur_time, cur = heappop(pq)
if cur == N - 1:
break
if cur_time > min_time[cur]:
continue
for nxt, cost in graph[cur]:
nxt_time = cur_time + cost
if nxt_time < min_time[nxt]:
min_time[nxt] = nxt_time
heappush(pq, (nxt_time, nxt))
print(min_time[N-1] if min_time[N-1] != float('inf') else -1)
solve()⭐ 4. 백준 1405 (미친 로봇)
# 4. 알고(백트래킹): 백준 1405 (미친 로봇) - https://www.acmicpc.net/problem/1405
import sys
from io import StringIO
sys.stdin = StringIO('''14 25 25 25 25''')
input = sys.stdin.readline
def solve():
# 동, 서, 남, 북
N, e, w, s, n = map(int, input().split())
probs = [e/100, w/100, s/100, n/100]
directions = [(0, +1), (0, -1), (+1, 0), (-1, 0)]
visited = {(0, 0)}
answer = 0.0
def dfs(step, r, c, p):
nonlocal answer
if step == N:
answer += p
return
for i, (dr, dc) in enumerate(directions):
if probs[i] == 0: # 이동할 가능성 없는 경우 제외
continue
nr, nc = r + dr, c + dc
if (nr, nc) not in visited:
visited.add((nr, nc)) # 진행방향의 확률을 누적해서 곱해 줌
dfs(step + 1, nr, nc, p * probs[i])
visited.remove((nr, nc))
dfs(0, 0, 0, 1.0)
print(answer)
solve()✏️ 5. SQL 없어진 기록 찾기
-- 5. SQL(Lv.3): 없어진 기록 찾기
-- https://school.programmers.co.kr/learn/courses/30/lessons/59042
SELECT
ANIMAL_ID,
AO.NAME
FROM
ANIMAL_OUTS AO
LEFT JOIN
ANIMAL_INS AI USING (ANIMAL_ID)
WHERE
AI.DATETIME IS NULL
ORDER BY
ANIMAL_ID ASC;