✅ 27 회차 모의고사 D-04일
🚀 1차 코딩테스트 대비
- 백준 1316 (그룹 단어 체커)
- 백준 1644 (소수의 연속합)
- 백준 2075 (N번째 큰 수)
- 백준 10162 (전자레인지)
- SQL 조건에 맞는 아이템들의 가격의 총합 구하기
1차 풀이
⭐ 1. 백준 1316 (그룹 단어 체커)
# 1. 알고(문자열): 백준 1316 (그룹 단어 체커) - https://www.acmicpc.net/problem/1316
import sys
from io import StringIO
sys.stdin = StringIO('''9
aaa
aaazbz
babb
aazz
azbz
aabbaa
abacc
aba
zzaz''')
input = sys.stdin.readline
def solve():
N = int(input())
count = 0
for _ in range(N):
string = input().rstrip()
visited = set()
base = None
for char in string:
if char == base:
continue
if char in visited:
break
visited.add(char)
base = char
else:
count += 1
print(count)
solve()⭐ 2. 백준 1644 (소수의 연속합)
# 2. 알고(수학): 백준 1644 (소수의 연속합) - https://www.acmicpc.net/problem/1644
import sys
from math import isqrt
from io import StringIO
sys.stdin = StringIO('''41''')
input = sys.stdin.readline
def solve():
N = int(input())
if N == 1:
return print(0)
prime = [True] * (N + 1)
prime[:2] = [False] * 2
for i in range(2, isqrt(N) + 1):
if not prime[i]:
continue
prime[i**2: N+1: i] = [False] * len(range(i**2, N+1, i))
primes = tuple(num for num, state in enumerate(prime) if state)
left = 0
sum_val = 0
count = 0
for p_val in primes:
sum_val += p_val
while sum_val > N:
sum_val -= primes[left]
left += 1
if sum_val == N:
count += 1
print(count)
solve()⭐ 3. 백준 2075 (N번째 큰 수)
# 3. 알고(Heap): 백준 2075 (N번째 큰 수) - https://www.acmicpc.net/problem/2075
import sys
from heapq import heapreplace, heapify
from io import StringIO
sys.stdin = StringIO('''5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49''')
input = sys.stdin.readline
def solve():
N = int(input())
pq = list(map(int, input().split())) # 한줄만 미리 받음
heapify(pq)
for _ in range(N-1): # 나머지 숫자들
for num in map(int, input().split()):
if num > pq[0]: # 제일 작은값 보다 클때만
heapreplace(pq, num)
print(pq[0])
solve()⭐ 4. 백준 10162 (전자레인지)
# 4. 알고(그리디): 백준 10162 (전자레인지) - https://www.acmicpc.net/problem/10162
import sys
from io import StringIO
sys.stdin = StringIO('''100''')
input = sys.stdin.readline
def solve():
N = int(input())
if N % 10 != 0:
return print(-1)
time = N
answer = []
for i in (300, 60, 10):
q, time = divmod(time, i)
answer.append(q)
print(*answer)
solve()✏️ 5. SQL 조건에 맞는 아이템들의 가격의 총합 구하기
SELECT
SUM(PRICE) AS TOTAL_PRICE
FROM
ITEM_INFO
WHERE
RARITY = 'LEGEND';🚀 2차 코딩테스트 대비
- 백준 14499 (주사위 굴리기)
- 백준 15990 (1, 2, 3 더하기 5)
- 백준 1043 (거짓말)
- 백준 1027 (고층 건물)
- SQL 특정 세대의 대장균 찾기
2차 풀이
⭐ 1. 백준 14499 (주사위 굴리기)
# 1. 알고(시뮬): 백준 14499 (주사위 굴리기) - https://www.acmicpc.net/problem/14499
import sys
from io import StringIO
sys.stdin = StringIO('''4 2 0 0 8
0 2
3 4
5 6
7 8
4 4 4 1 3 3 3 2''')
input = sys.stdin.readline
def solve():
N, M, r, c, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
cmds = map(lambda x: int(x) - 1, input().split())
directions = [(0, +1), (0, -1), (-1, 0), (+1, 0)]
dice = [0] * 6
def roll(d):
left, top, right, bottom, back, front = dice
if d == 0: # left, top, right, bottom, back, front
dice[:] = bottom, left, top, right, back, front
elif d == 1:
dice[:] = top, right, bottom, left, back, front
elif d == 2:
dice[:] = left, front, right, back, top, bottom
elif d == 3:
dice[:] = left, back, right, front, bottom, top
answer = []
for cmd in cmds:
dr, dc = directions[cmd]
nr, nc = r + dr, c + dc
in_range = 0 <= nr < N and 0 <= nc < M
if not in_range:
continue
r, c = nr, nc # 이동
roll(cmd)
answer.append(dice[1]) # 상단
val = board[r][c]
if val == 0:
board[r][c] = dice[3] # 바닥
else:
dice[3] = val
board[r][c] = 0
print("\n".join(map(str, answer)))
solve()⭐ 2. 백준 15990 (1, 2, 3 더하기 5)
# 2. 알고(DP): 백준 15990 (1, 2, 3 더하기 5) - https://www.acmicpc.net/problem/15990
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''3
4
7
10''')
input = sys.stdin.readline
def solve():
T = int(input())
nums = [int(input()) for _ in range(T)]
need = set(nums)
answers = {}
MAX = max(nums)
MOD = 1_000_000_009
dp = deque([
(1, 0, 0), # i-3 (*, *, .)
(0, 1, 0), # i-2 (*, ., *)
(1, 1, 1), # i-1 (., *, *)
]) # (1사용, 2사용, 3사용)
for i in range(3):
answers[i+1] = sum(dp[i]) # 1, 2, 3 정답 저장
for i in range(4, MAX + 1):
dp_i = (
(dp[-1][1] + dp[-1][2]) % MOD, # 1 사용
(dp[-2][0] + dp[-2][2]) % MOD, # 2 사용
(dp[-3][0] + dp[-3][1]) % MOD, # 3 사용
)
if i in need:
answers[i] = sum(dp_i) % MOD
dp.popleft()
dp.append(dp_i)
print("\n".join(str(answers[num]) for num in nums))
solve()⭐ 3. 백준 1043 (거짓말)
# 3. 알고(그래프): 백준 1043 (거짓말) - https://www.acmicpc.net/problem/1043
import sys
from io import StringIO
sys.stdin = StringIO('''10 9
4 1 2 3 4
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
parent = list(range(N + 1))
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
def union(ra, rb):
parent[max(ra, rb)] = min(ra, rb)
# 진실
T, *trues = map(int, input().split())
if T == 0:
return print(M)
if T > 1:
for i in range(T - 1):
ra, rb = find(trues[i]), find(trues[i+1])
if ra != rb:
union(ra, rb)
# 파티
captines = []
for _ in range(M):
P, *party = map(int, input().split())
if P > 1:
for i in range(P - 1):
ra, rb = find(party[i]), find(party[i+1])
if ra != rb:
union(ra, rb)
captines.append(party[0]) # 파티 대표자 1명 저장
t_root = find(trues[0]) # 진실 대표자
print(sum(t_root != find(cap) for cap in captines))
solve()⭐ 4. 백준 1027 (고층 건물)
# 4. 알고(기하): 백준 1027 (고층 건물) - https://www.acmicpc.net/problem/1027
import sys
from io import StringIO
sys.stdin = StringIO('''15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5''')
input = sys.stdin.readline
def solve():
N = int(input())
heights = map(int, input().split())
dots = tuple((x, y) for x, y in enumerate(heights, 1))
count = [0] * N
for i in range(N):
x1, y1 = dots[i]
max_slope = -float('inf')
for j in range(i+1, N):
x2, y2 = dots[j]
cur_slope = (y2 - y1) / (x2 - x1)
if cur_slope <= max_slope:
continue
max_slope = cur_slope
count[i] += 1
count[j] += 1 # 서로 볼 수 있음
print(max(count))
solve()✏️ 5. SQL 특정 세대의 대장균 찾기
WITH RECURSIVE
GEN AS (
SELECT
ID,
1 AS GENER
FROM ECOLI_DATA
WHERE PARENT_ID IS NULL
UNION ALL
SELECT
ED.ID,
GEN.GENER + 1 AS GENER
FROM GEN
JOIN ECOLI_DATA ED ON GEN.ID = ED.PARENT_ID
WHERE GEN.GENER < 3
)
SELECT ID
FROM GEN
WHERE GENER = 3
ORDER BY ID;