✅ 22 회차 모의고사 D-09일
🚀 1차 코딩테스트 대비
- 백준 14888 (연산자 끼워넣기)
- 백준 4948 (베르트랑 공준)
- 백준 11279 (최대 힙)
- 백준 1339 (단어 수학)
- SQL 연도별 평균 미세먼지 농도 조회하기
1차 풀이
⭐ 1. 백준 14888 (연산자 끼워넣기)
# 1. 알고(구현): 백준 14888 (연산자 끼워넣기) - https://www.acmicpc.net/problem/14888
import sys
from io import StringIO
sys.stdin = StringIO('''6
1 2 3 4 5 6
2 1 1 1''')
input = sys.stdin.readline
def solve():
N = int(input())
nums = list(map(int, input().split()))
opers = list(map(int, input().split()))
# plus, minus, multi, div
min_val, max_val = float('inf'), -float('inf')
def dfs(num_idx, answer):
nonlocal min_val, max_val
if num_idx == N:
min_val = min(min_val, answer)
max_val = max(max_val, answer)
return
nxt_num = nums[num_idx]
for i in range(4):
oper = opers[i] # 남은 개수
if oper == 0:
continue
nxt_answer = answer
if i == 0:
nxt_answer += nxt_num
elif i == 1:
nxt_answer -= nxt_num
elif i == 2:
nxt_answer *= nxt_num
else:
nxt_answer = int(nxt_answer / nxt_num)
opers[i] -= 1
dfs(num_idx + 1, nxt_answer)
opers[i] += 1
dfs(1, nums[0])
print(max_val)
print(min_val)
solve()⭐ 2. 백준 4948 (베르트랑 공준)
# 2. 알고(수학): 백준 4948 (베르트랑 공준) - https://www.acmicpc.net/problem/4948
import sys
from math import isqrt
from io import StringIO
sys.stdin = StringIO('''1
10
13
100
1000
10000
100000
0''')
input = sys.stdin.readline
def solve():
MAX = 2*123_456
is_prime = [True] * (MAX + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, isqrt(MAX) + 1):
if not is_prime[i]:
continue
is_prime[i*i: MAX+1: i] = [False] * len(range(i*i, MAX+1, i))
prefix = [0] * (MAX + 1)
cnt = 0
for i in range(1, MAX + 1):
if is_prime[i] == True:
cnt += 1
prefix[i] = cnt
while True:
num = int(input())
if num == 0:
break
print(prefix[2*num] - prefix[num])
solve()⭐ 3. 백준 11279 (최대 힙)
# 3. 알고(Heap): 백준 11279 (최대 힙) - https://www.acmicpc.net/problem/11279
import sys
from heapq import heappush, heappop
from io import StringIO
sys.stdin = StringIO('''13
0
1
2
0
0
3
2
1
0
0
0
0
0''')
input = sys.stdin.readline
def solve():
N = int(input())
pq = []
answer = []
for _ in range(N):
cmd = int(input())
if cmd > 0:
heappush(pq, -cmd)
elif pq:
answer.append(str(-heappop(pq)))
else:
answer.append('0')
print("\n".join(answer))
solve()⭐ 4. 백준 1339 (단어 수학)
# 4. 알고(그리디): 백준 1339 (단어 수학) - https://www.acmicpc.net/problem/1339
import sys
from collections import defaultdict
from io import StringIO
sys.stdin = StringIO('''2
GCF
ACDEB''')
input = sys.stdin.readline
def solve():
N = int(input())
words = [reversed(input().rstrip()) for _ in range(N)]
weight_dict = defaultdict(int)
for word in words:
for i, char in enumerate(word):
weight_dict[char] += 10**i
weights = sorted(weight_dict.values(), reverse=True)
print(sum(digit * w for digit, w in zip(range(9, -1, -1), weights)))
solve()✏️ 5. SQL 연도별 평균 미세먼지 농도 조회하기
-- 5. SQL(Lv.2): 연도별 평균 미세먼지 농도 조회하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/284530
SELECT
YEAR(YM) AS `YEAR`,
ROUND(AVG(PM_VAL1), 2) AS `PM10`,
ROUND(AVG(PM_VAL2), 2) AS `PM2.5`
FROM
AIR_POLLUTION
WHERE
(LOCATION1, LOCATION2) = ('경기도', '수원')
GROUP BY
`YEAR`
ORDER BY
`YEAR` ASC🚀 2차 코딩테스트 대비
- 백준 17779 (게리맨더링 2)
- 백준 2565 (전깃줄)
- 백준 11657 (타임머신)
- 백준 17135 (캐슬 디펜스)
- SQL 조건에 맞는 사용자와 총 거래금액 조회하기
2차 풀이
⭐ 1. 백준 17779 (게리맨더링 2)
# 1. 알고(시뮬): 백준 17779 (게리맨더링 2) - https://www.acmicpc.net/problem/17779
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6''')
input = sys.stdin.readline
def solve():
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
total_pop = sum(sum(row) for row in board)
min_diff = float('inf')
for x, y in product(range(N-2), range(1, N - 1)):
for d1, d2 in product(range(1, y + 1), range(1, N - y)):
if x + d1 + d2 >= N:
continue
population = [0] * 5
left = y + 1
for r in range(x + d1):
if r >= x:
left -= 1
population[1] += sum(board[r][:left])
right = y + 1
for r in range(x + d2 + 1):
if r > x:
right += 1
population[2] += sum(board[r][right:])
left = y - d1
for r in range(x + d1, N):
population[3] += sum(board[r][:left])
if r < x + d1 + d2:
left += 1
right = y + d2
for r in range(x + d2 + 1, N):
population[4] += sum(board[r][right:])
if r <= x + d1 + d2:
right -= 1
population[0] = total_pop - sum(population) # 5번은 0에다가
current_diff = max(population) - min(population)
min_diff = min(current_diff, min_diff)
print(min_diff)
solve()⭐ 2. 백준 2565 (전깃줄)
# 2. 알고(DP): 백준 2565 (전깃줄) - https://www.acmicpc.net/problem/2565
import sys
from bisect import bisect_left
from io import StringIO
sys.stdin = StringIO('''8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6''')
input = sys.stdin.readline
def solve():
N = int(input())
lines = sorted(tuple(map(int, input().split())) for _ in range(N))
increse = [] # lis(Longest Increasing Subsequence)
for _, num in lines:
idx = bisect_left(increse, num)
if idx == len(increse):
increse.append(num)
else:
increse[idx] = num
print(N - len(increse))
solve()⭐ 3. 백준 11657 (타임머신)
# 3. 알고(그래프): 백준 11657 (타임머신) - https://www.acmicpc.net/problem/11657
import sys
from io import StringIO
sys.stdin = StringIO('''3 4
1 2 4
1 3 3
2 3 -1
3 1 -2''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
edges = [tuple(map(int, input().rsplit())) for _ in range(M)]
INF = float('inf')
min_dist = [INF] * (N + 1)
min_dist[1] = 0
for i in range(N):
for cur, nxt, time in edges:
cur_dist = min_dist[cur]
if cur_dist == INF: # 시작점 못옴
continue
nxt_dist = cur_dist + time
if nxt_dist >= min_dist[nxt]: # 거리 갱신 필요 없음
continue
if i == N - 1: # N-1 번째 거리 갱신 필요하면 무한 루프
return print(-1)
min_dist[nxt] = nxt_dist # 최단거리 갱신
print("\n".join(
str(d) if d != INF else '-1'
for d in min_dist[2:]
))
solve()⭐ 4. 백준 17135 (캐슬 디펜스)
# 4. 알고(백트래킹): 백준 17135 (캐슬 디펜스) - https://www.acmicpc.net/problem/17135
import sys
from collections import deque
from itertools import combinations, product
from heapq import heappush, heappop
from io import StringIO
sys.stdin = StringIO('''6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0''')
input = sys.stdin.readline
def solve():
N, M, D = map(int, input().split())
origin = deque(list(map(int, input().split())) for _ in range(N))
max_enemy = 0
for combi in combinations(range(M), 3):
enemys = deque(row[:] for row in origin)
del_enemy_cnt = 0
for _ in range(N):
target = set()
for ac in combi: # 궁수 좌표
priority = []
for er, ec in product(range(N), range(M)):
if enemys[er][ec] == 0:
continue
dist = abs(N-er) + abs(ac-ec)
if dist <= D:
heappush(priority, (dist, ec, er)) # col 우선
if priority:
_, tc, tr = heappop(priority) # 1 순위 지정
target.add((tr, tc)) # 타겟 저장
for dr, dc in target:
enemys[dr][dc] = 0
del_enemy_cnt += 1
enemys.pop()
enemys.appendleft([0]*M)
max_enemy = max(max_enemy, del_enemy_cnt)
print(max_enemy)
solve()✏️ 5. SQL 조건에 맞는 사용자와 총 거래금액 조회하기
-- 5. SQL(Lv.3): 조건에 맞는 사용자와 총 거래금액 조회하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/164668
WITH
DONE AS (
SELECT
WRITER_ID AS USER_ID,
SUM(PRICE) AS `TOTAL_SALES`
FROM
USED_GOODS_BOARD
WHERE
STATUS = 'DONE'
GROUP BY
WRITER_ID
HAVING
`TOTAL_SALES` >= 700000
)
SELECT
USER_ID,
NICKNAME,
TOTAL_SALES
FROM
DONE
JOIN
USED_GOODS_USER USING (USER_ID)
ORDER BY
TOTAL_SALES ASC;