✅ 25 회차 모의고사 D-06일
🚀 1차 코딩테스트 대비
- 백준 1475 (방 번호)
- 백준 1735 (분수 합)
- 백준 12015 (가장 긴 증가하는 부분 수열 2)
- 백준 1080 (행렬)
- SQL 월별 잡은 물고기 수 구하기
1차 풀이
⭐ 1. 백준 1475 (방 번호)
# 1. 알고(구현): 백준 1475 (방 번호) - https://www.acmicpc.net/problem/1475
import sys
from collections import Counter
from io import StringIO
sys.stdin = StringIO('''12635''')
input = sys.stdin.readline
def solve():
num = input().rstrip()
count = Counter(num)
need = count['6'] + count['9']
count['6'] = count['9'] = (need + 1) // 2
print(max(count.values()))
solve()⭐ 2. 백준 1735 (분수 합)
# 2. 알고(수학): 백준 1735 (분수 합) - https://www.acmicpc.net/problem/1735
import sys
from math import gcd
from io import StringIO
sys.stdin = StringIO('''2 7
3 5''')
input = sys.stdin.readline
def solve():
a, b = map(int, input().split())
c, d = map(int, input().split())
B = b*d
A = a*d + b*c
AB_gcd = gcd(A,B)
A, B = A // AB_gcd, B // AB_gcd
print(A, B)
solve()⭐ 3. 백준 12015 (가장 긴 증가하는 부분 수열 2)
# 3. 알고(탐색): 백준 12015 (가장 긴 증가하는 부분 수열 2) - https://www.acmicpc.net/problem/12015
import sys
from bisect import bisect_left
from io import StringIO
sys.stdin = StringIO('''6
10 20 10 30 20 50''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = map(int, input().split())
arr = []
for num in nums:
idx = bisect_left(arr, num)
if idx == len(arr):
arr.append(num)
else:
arr[idx] = num
print(len(arr))
solve()⭐ 4. 백준 1080 (행렬)
# 4. 알고(그리디): 백준 1080 (행렬) - https://www.acmicpc.net/problem/1080
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''3 4
0000
0010
0000
1001
1011
1001''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
A = [list(input().rstrip()) for _ in range(N)]
B = [list(input().rstrip()) for _ in range(N)]
cnt = 0
if N < 3 or M < 3:
return print(0 if A == B else -1)
for r in range(N-2):
for c in range(M-2):
if A[r][c] == B[r][c]:
continue
for i, j in product(range(r, r + 3), range(c, c + 3)):
A[i][j] = '1' if A[i][j] == '0' else '0'
cnt += 1
if A[r][M-2:] != B[r][M-2:]: # 오른쪽 끝 2개
return print(-1)
# 아래쪽 외곽
for r, c in product(range(N-2, N), range(M)):
if A[r][c] != B[r][c]:
return print(-1)
print(cnt)
solve()✏️ 5. SQL 월별 잡은 물고기 수 구하기
-- 5. SQL(Lv.2): 월별 잡은 물고기 수 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/293260
SELECT
COUNT(*) AS FISH_COUNT,
MONTH(TIME) AS `MONTH`
FROM
FISH_INFO
GROUP BY
`MONTH`
ORDER BY
`MONTH` ASC;🚀 2차 코딩테스트 대비
- 백준 23290 (마법사 상어와 복제)
- 백준 14003 (가장 긴 증가하는 부분 수열 5)
- 백준 1865 (웜홀)
- 백준 1941 (소문난 칠공주)
- SQL 오랜 기간 보호한 동물(1)
2차 풀이
⭐ 1. 백준 23290 (마법사 상어와 복제)
# 1. 알고(시뮬): 백준 23290 (마법사 상어와 복제) - https://www.acmicpc.net/problem/23290
import sys
from collections import defaultdict, deque
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''5 26
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2''')
input = sys.stdin.readline
def solve():
directions = [
(0, -1), (-1, -1), (-1, 0), (-1, +1), # ←, ↖, ↑, ↗,
(0, +1), (+1, +1), (+1, 0), (+1, -1) # →, ↘, ↓, ↙
]
shark_dirs = [(-1, 0), (0, -1), (+1, 0), (0, +1)]
board = defaultdict(list)
M, S = map(int, input().split())
for _ in range(M):
fx, fy, d = map(int, (input().split()))
board[(fx, fy)].append(d - 1)
sr, sc = map(int, input().split())
smells_dq = deque()
while S > 0:
move_board = defaultdict(list)
# 물고기 이동
for (fr, fc), fish_dirs in board.items():
for d in fish_dirs:
for step in range(8):
nd = (d - step) % 8
dr, dc = directions[nd]
nr, nc = nxt = fr + dr, fc + dc
in_range = 1 <= nr <= 4 and 1 <= nc <= 4
if not in_range or nxt == (sr, sc):
continue
if any(nxt in smells for smells in smells_dq):
continue
move_board[nxt].append(nd) # 이동해서 넣어줌
break
else: # 이동 불가능 할때 그대로 넣어줌
move_board[(fr, fc)].append(d)
candi = []
# 상어 경로 조사
def dfs(history, move, fish_cnt, stemp):
if move == 3:
heappush(candi, (-fish_cnt, int(stemp), history))
return
cur_sr, cur_sc = history[-1]
for d_idx in range(4):
dr, dc = shark_dirs[d_idx]
nr, nc = nxt = cur_sr + dr, cur_sc + dc
in_range = 1 <= nr <= 4 and 1 <= nc <= 4
if not in_range:
continue
nxt_fish_cnt = fish_cnt
if nxt not in history[1:]: # 이미 지나온 곳이 아니면
nxt_fish_cnt += len(move_board[nxt])
dfs(history+[nxt], move+1, nxt_fish_cnt, stemp+str(d_idx))
dfs([(sr, sc)], 0, 0, '')
# 사냥
smells = set()
_, _, hist = heappop(candi)
for h_r_c in hist[1:]:
if move_board[h_r_c]: # 경로에 물고기 있으면
smells.add(h_r_c) # 냄새 정보 추가
move_board[h_r_c].clear() # 이동경로 물고기 삭제
sr, sc = hist[-1] # 상어 이동
# 지난 냄새 관리
smells_dq.append(smells)
if len(smells_dq) > 2:
smells_dq.popleft()
# 물고기 복제
for copy_rc, copy_d in board.items():
if copy_d: # 물고기 있으면
move_board[copy_rc].extend(copy_d)
board = move_board
S -= 1 # 다음 턴
print(sum(len(fishs) for fishs in board.values()))
solve()⭐ 2. 백준 14003 (가장 긴 증가하는 부분 수열 5)
# 2. 알고(DP): 백준 14003 (가장 긴 증가하는 부분 수열 5) - https://www.acmicpc.net/problem/14003
import sys
from bisect import bisect_left
from io import StringIO
sys.stdin = StringIO('''6
10 20 10 30 20 50''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = tuple(map(int, input().split()))
for_prev = [-1] * N
for_length = []
for i, num in enumerate(nums):
idx = bisect_left(for_length, num)
if idx == len(for_length):
for_length.append(num)
else:
for_length[idx] = num
for_prev[i] = idx
max_len = len(for_length)
answer = []
find_idx = max_len - 1
for i in range(N-1, -1, -1):
if for_prev[i] == find_idx:
answer.append(nums[i])
find_idx -= 1
answer.reverse()
print(max_len)
print(*answer)
solve()⭐ 3. 백준 1865 (웜홀)
# 3. 알고(그래프): 백준 1865 (웜홀) - https://www.acmicpc.net/problem/1865
import sys
from io import StringIO
sys.stdin = StringIO('''2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8''')
input = sys.stdin.readline
def solve(out):
N, M, W = map(int, input().split())
edges = []
for _ in range(M):
S, E, T = map(int, input().split())
edges.append((S-1, E-1, T))
edges.append((E-1, S-1, T))
for _ in range(W):
S, E, T = map(int, input().split())
edges.append((S-1, E-1, -T))
min_dist = [0] * N # 거리정보는 없어도 됨, 음수 싸이클 만 탐지
for trying in range(N): # 벨만-포드
updated = False
for cur, nxt, time in edges:
nxt_time = min_dist[cur] + time
if nxt_time >= min_dist[nxt]:
continue
if trying == N - 1:
return out.append('YES')
min_dist[nxt] = nxt_time
updated = True
if not updated:
break
out.append('NO')
out = []
T = int(input())
for _ in range(T):
solve(out)
print("\n".join(out))⭐ 4. 백준 1941 (소문난 칠공주)
# 4. 알고(백트래킹): 백준 1941 (소문난 칠공주) - https://www.acmicpc.net/problem/1941
import sys
from itertools import combinations, product
from io import StringIO
sys.stdin = StringIO('''YYYYY
SYSYS
YYYYY
YSYYS
YYYYY''')
input = sys.stdin.readline
def solve():
board = [input().rstrip() for _ in range(5)]
directions = [(0, +1), (0, -1), (+1, 0), (-1, 0)]
S, Y = [], [] # S 4 명 이상
for r, c in product(range(5), repeat=2):
if board[r][c] == 'Y':
Y.append((r, c))
else:
S.append((r, c))
if len(S) < 4:
return print(0)
count = 0
for s_member in range(4, min(7, len(S)) + 1):
for s_combi in combinations(S, s_member):
for y_combi in combinations(Y, 7-s_member):
seven = set(s_combi + y_combi)
cur = next(iter(seven))
stack = [cur]
visited = {cur}
while stack:
r, c = stack.pop()
for dr, dc in directions:
nxt = r + dr, c + dc
if nxt not in seven or nxt in visited:
continue
visited.add(nxt)
stack.append(nxt)
if len(visited) == 7:
count += 1
print(count)
solve()✏️ 5. SQL 오랜 기간 보호한 동물(1)
-- 5. SQL(Lv.3): 오랜 기간 보호한 동물(1)
-- https://school.programmers.co.kr/learn/courses/30/lessons/59044
SELECT
NAME,
DATETIME
FROM
ANIMAL_INS
WHERE
ANIMAL_ID NOT IN (
SELECT ANIMAL_ID
FROM ANIMAL_OUTS
)
ORDER BY
DATETIME ASC
LIMIT 3;