✅ 04 회차 모의고사 D-27일
🚀 1차 코딩테스트 대비
- 백준 2161 (카드1)
- 백준 2292 (벌집)
- 백준 17219 (비밀번호 찾기)
- 백준 11508 (2+1 세일)
- SQL 흉부외과 또는 일반외과 의사 목록 출력하기
1차 풀이
⭐ 1. 백준 2161 (카드1)
# 1. 알고(구현): 백준 2161 (카드1) - https://www.acmicpc.net/problem/2161
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''7''')
input = sys.stdin.readline
def solve():
N = int(input())
dq = deque(range(1, N + 1))
answer = []
while dq:
answer.append(dq.popleft())
dq.rotate(-1)
print(*answer)
solve()⭐ 2. 백준 2292 (벌집)
# 2. 알고(수학): 백준 2292 (벌집) - https://www.acmicpc.net/problem/2292
import sys
from io import StringIO
sys.stdin = StringIO('''13''')
input = sys.stdin.readline
def solve():
# ak = 1 + sigma(i,k-1)6i = 1 + 3k(k-1)
N = int(input())
layer = 1
while True:
max_num = 1 + 3*layer*(layer - 1)
if N <= max_num:
break
layer += 1
print(layer)
solve()⭐ 3. 백준 17219 (비밀번호 찾기)
# 3. 알고(Map): 백준 17219 (비밀번호 찾기) - https://www.acmicpc.net/problem/17219
import sys
from io import StringIO
sys.stdin = StringIO('''16 4
noj.am IU
acmicpc.net UAENA
startlink.io THEKINGOD
google.com ZEZE
nate.com VOICEMAIL
naver.com REDQUEEN
daum.net MODERNTIMES
utube.com BLACKOUT
zum.com LASTFANTASY
dreamwiz.com RAINDROP
hanyang.ac.kr SOMEDAY
dhlottery.co.kr BOO
duksoo.hs.kr HAVANA
hanyang-u.ms.kr OBLIVIATE
yd.es.kr LOVEATTACK
mcc.hanyang.ac.kr ADREAMER
startlink.io
acmicpc.net
noj.am
mcc.hanyang.ac.kr''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
passwords = dict()
for _ in range(N):
url, pswd = input().split()
passwords[url] = pswd
result = []
for _ in range(M):
url = input().rstrip()
result.append(passwords[url])
print("\n".join(result))
solve()⭐ 4. 백준 11508 (2+1 세일)
# 4. 알고(그리디): 백준 11508 (2+1 세일) - https://www.acmicpc.net/problem/11508
import sys
from io import StringIO
sys.stdin = StringIO('''6
6
4
5
5
5
5''')
input = sys.stdin.readline
def solve():
N = int(input())
prices = [int(input()) for _ in range(N)]
prices.sort(reverse=True)
print(sum(prices) - sum(prices[2::3]))
solve()✏️ 5. SQL 흉부외과 또는 일반외과 의사 목록 출력하기
--5. SQL(Lv.1): 흉부외과 또는 일반외과 의사 목록 출력하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/132203
SELECT
DR_NAME,
DR_ID,
MCDP_CD,
DATE_FORMAT(HIRE_YMD, '%Y-%m-%d') AS HIRE_YMD
FROM
DOCTOR
WHERE
MCDP_CD IN ('CS', 'GS')
ORDER BY
HIRE_YMD DESC,
DR_NAME ASC;🚀 2차 코딩테스트 대비
- 백준 16234 (인구 이동)
- 백준 1520 (내리막 길)
- 백준 11779 (최소비용 구하기 2)
- 백준 1062 (가르침)
- SQL 주문량이 많은 아이스크림들 조회하기
2차 풀이
⭐ 1. 백준 16234 (인구 이동)
# 1. 알고(시뮬): 백준 16234 (인구 이동) - https://www.acmicpc.net/problem/16234
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10''')
input = sys.stdin.readline
directions = [(+1, 0), (-1, 0), (0, -1), (0, +1)]
def solve():
N, L, R = map(int, input().split())
populations = [list(map(int, input().split())) for _ in range(N)]
# 지정한 r, c 기준 연합과 연합 총 인구 반환
def find_union(r, c):
union = set([(r, c)])
dq = deque([(r, c)])
total_p = populations[r][c]
while dq:
cur_r, cur_c = dq.popleft()
for dr, dc in directions:
nr, nc = cur_r + dr, cur_c + dc
if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in union:
cur_p = populations[cur_r][cur_c]
nxt_p = populations[nr][nc]
diff = abs(cur_p - nxt_p)
if L <= diff <= R:
union.add((nr, nc))
dq.append((nr, nc))
total_p += nxt_p
return union, total_p
# 연합을 찾고, 사람들들 이동 시킴
def is_people_moved():
visited_nations = set()
unions = []
for r in range(N):
for c in range(N):
if (r, c) not in visited_nations:
union_set, total_p = find_union(r, c)
visited_nations.update(union_set)
# 연합이 있으면 최소 2개
if len(union_set) > 1:
unions.append((union_set, total_p))
if unions:
for union, total_p in unions:
avg_p = total_p // len(union)
for r, c in union:
populations[r][c] = avg_p
return True
return False
count = 0
while True:
if is_people_moved():
count += 1
else:
break
print(count)
solve()⭐ 2. 백준 1520 (내리막 길)
# 2. 알고(DP): 백준 1520 (내리막 길) - https://www.acmicpc.net/problem/1520
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10''')
input = sys.stdin.readline
def solve():
M, N = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(M)]
visited = [[False] * N for _ in range(M)]
dp = [[0] * N for _ in range(M)]
directions = [(+1, 0), (-1, 0), (0, +1), (0, -1)]
pq = [(-board[0][0], 0, 0)] # 높이, 좌표
visited[0][0] = True
dp[0][0] = 1
while pq:
cur_h, r, c = heappop(pq)
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < M and 0 <= nc < N:
nxt_height = board[nr][nc]
if nxt_height < -cur_h:
if not visited[nr][nc]:
heappush(pq, (-nxt_height, nr, nc))
visited[nr][nc] = True
dp[nr][nc] += dp[r][c]
print(dp[M-1][N-1])
solve()⭐ 3. 백준 11779 (최소비용 구하기 2)
# 3. 알고(그래프): 백준 11779 (최소비용 구하기 2) - https://www.acmicpc.net/problem/11779
import sys
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5''')
input = sys.stdin.readline
def solve():
n, m = int(input()), int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, c = map(int, input().split())
graph[s].append((e, c))
start, end = map(int, input().split())
min_parent = [0] * (n + 1)
min_dist = [float('inf')] * (n + 1)
min_dist[start] = 0
pq = [(0, start)]
while pq:
cur_dist, cur = heappop(pq)
if cur == end:
break
if cur_dist > min_dist[cur]:
continue
for nxt, cost in graph[cur]:
nxt_dist = cur_dist + cost
if nxt_dist < min_dist[nxt]:
min_parent[nxt] = cur
min_dist[nxt] = nxt_dist
heappush(pq, (nxt_dist, nxt))
path = []
curr = end
while curr != 0:
path.append(curr)
curr = min_parent[curr]
path.reverse()
print(min_dist[end])
print(len(path))
print(*path)
solve()⭐ 4. 백준 1062 (가르침)
# 4. 알고(백트래킹): 백준 1062 (가르침) - https://www.acmicpc.net/problem/1062
import sys
from io import StringIO
sys.stdin = StringIO('''9 8
antabtica
antaxtica
antadtica
antaetica
antaftica
antagtica
antahtica
antajtica
antaktica''')
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
can_read_set = set('anta' + 'tica')
can_learn = K - len(can_read_set)
if K < len(can_read_set):
print(0)
return
# 차집합을 활용하여 필터링.
word_sets = [
set(input().rstrip()[4:-4]).difference(can_read_set)
for _ in range(N)
]
need_to_learn_set = set()
need_to_learn_set.update(*word_sets)
candidates = list(need_to_learn_set)
length_candi = len(candidates)
# 배워야 할게 배울수 있는 길이 보다 짧거나 같으면
if length_candi <= can_learn:
print(N)
return
max_val = 0
learned_set = set()
def dfs(idx, learn_count):
nonlocal max_val
# 충분히 학습한 후 조사.
if learn_count == can_learn:
readable = 0
for word in word_sets:
if word.issubset(learned_set):
readable += 1
if readable > max_val:
max_val = readable
return
# 남은 걸 다 배워도 목표를 채우지 못하는 경우 종료.
will_learn = length_candi - idx
if will_learn < (can_learn - learn_count):
return
if idx == length_candi: # 조사할 것이 없음.
return
# 학습
learn_char = candidates[idx]
learned_set.add(learn_char)
dfs(idx + 1, learn_count + 1)
learned_set.remove(learn_char)
# 학습 x
dfs(idx + 1, learn_count)
dfs(0, 0)
print(max_val)
solve()✏️ 5. SQL 주문량이 많은 아이스크림들 조회하기
-- 5. SQL(Lv.4): 주문량이 많은 아이스크림들 조회하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/133027
SELECT
F.FLAVOR
FROM
FIRST_HALF F
JOIN (
SELECT
FLAVOR,
SUM(TOTAL_ORDER) AS JULY_TOTAL
FROM
JULY
GROUP BY
FLAVOR
) J ON F.FLAVOR = J.FLAVOR
ORDER BY
(F.TOTAL_ORDER + J.JULY_TOTAL) DESC
LIMIT 3;