✅ 14 회차 모의고사 D-17일
🚀 1차 코딩테스트 대비
- 백준 20053 (최소, 최대 2)
- 백준 2740 (행렬 곱셈)
- 백준 4358 (생태학)
- 백준 14916 (거스름돈)
- SQL 재구매가 일어난 상품과 회원 리스트 구하기
1차 풀이
⭐ 1. 백준 20053 (최소, 최대 2)
# 1. 알고(구현): 백준 20053 (최소, 최대 2) - https://www.acmicpc.net/problem/20053
import sys
from io import StringIO
sys.stdin = StringIO('''3
5
20 28 22 25 21
5
30 21 17 25 29
5
20 10 35 30 7''')
input = sys.stdin.readline
def solve():
N = int(input())
min, max = +float('inf'), -float('inf')
for num in map(int, input().split()):
if num < min:
min = num
if num > max:
max = num
print(min, max)
T = int(input())
for _ in range(T):
solve()⭐ 2. 백준 2740 (행렬 곱셈)
# 2. 알고(수학): 백준 2740 (행렬 곱셈) - https://www.acmicpc.net/problem/2740
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''3 2
1 2
3 4
5 6
2 3
-1 -2 0
0 0 3''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(N)]
M, K = map(int, input().split())
B = [tuple(map(int, input().split())) for _ in range(M)]
C = [[0]*K for _ in range(N)]
for r, c in product(range(N), range(K)):
C[r][c] = sum(A[r][m]*B[m][c] for m in range(M))
for row in C:
print(*row)
solve()⭐ 3. 백준 4358 (생태학)
# 3. 알고(Map): 백준 4358 (생태학) - https://www.acmicpc.net/problem/4358
import sys
from collections import defaultdict
from io import StringIO
sys.stdin = StringIO('''Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow''')
input = sys.stdin.readline
def solve():
count = defaultdict(int)
total = 0
while True:
name = input().rstrip()
if not name:
break
count[name] += 1
total += 1
print("\n".join(
f"{key} {(count[key]*100 / total):.4f}"
for key in sorted(count)
))
solve()⭐ 4. 백준 14916 (거스름돈)
# 4. 알고(그리디): 백준 14916 (거스름돈) - https://www.acmicpc.net/problem/14916
import sys
from io import StringIO
sys.stdin = StringIO('''13''')
input = sys.stdin.readline
def solve():
n = int(input())
if n == 1 or n == 3: # 불가능
print(-1)
return
q, r = divmod(n, 5)
if r % 2 == 0:
print(q + (r // 2))
else:
print((q - 1) + (r + 5)//2) # 5원 하나 빼서, 2로 나눔
solve()✏️ 5. SQL 재구매가 일어난 상품과 회원 리스트 구하기
-- 5. SQL(Lv.2): 재구매가 일어난 상품과 회원 리스트 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/131536
SELECT
USER_ID,
PRODUCT_ID
FROM
ONLINE_SALE
GROUP BY
USER_ID, PRODUCT_ID
HAVING
COUNT(*) >=2
ORDER BY
USER_ID, PRODUCT_ID DESC;🚀 2차 코딩테스트 대비
- 백준 14500 (테트로미노)
- 백준 12852 (1로 만들기 2)
- 백준 1261 (알고스팟)
- 백준 18429 (근성장)
- SQL 년, 월, 성별 별 상품 구매 회원 수 구하기
2차 풀이
⭐ 1. 백준 14500 (테트로미노)
# 1. 알고(시뮬): 백준 14500 (테트로미노) - https://www.acmicpc.net/problem/14500
import sys
from itertools import combinations, product
from io import StringIO
sys.stdin = StringIO('''5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1''')
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
board = [tuple(map(int, input().split())) for _ in range(N)]
MAX_BOARD_VAL = max(map(max, board))
directions = [(0, +1), (0, -1), (-1, 0), (+1, 0)]
three_dir_combis = tuple(combinations(directions, 3))
visited = [[False] * M for _ in range(N)]
max_value = 0
def find_t_shape(r, c):
nonlocal max_value
start_val = board[r][c]
# T 유형 조사.
for combi in three_dir_combis:
temp_sum = start_val
for dr, dc in combi:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < M:
temp_sum += board[nr][nc]
else:
break
else: # 3개다 모두 누적된 결과
max_value = max(max_value, temp_sum)
# 4가지 조사 (T 제외)
def dfs(depth, total_sum, cur_r, cur_c):
nonlocal max_value
# 남은 것을 모두 최대 값으로 채워도 맥스 Value 보다 작으면
if total_sum + (4 - depth) * MAX_BOARD_VAL <= max_value:
return
if depth == 4:
max_value = max(max_value, total_sum)
return
for dr, dc in directions:
nr, nc = cur_r + dr, cur_c + dc
# 현재 위치 기준, 인덱스 체크하고, 방문한 노드인지 체크
if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc]:
visited[nr][nc] = True
dfs(depth + 1, total_sum + board[nr][nc], nr, nc)
visited[nr][nc] = False
# 가지치기를 위해 가능한 최대값 우선 탐색
for r, c in product(range(N), range(M)):
find_t_shape(r, c)
for r, c in product(range(N), range(M)):
if (r + c) % 2 == 0: # 바로 옆칸, 아래칸은 중복 조사 되어 제외.
visited[r][c] = True
dfs(1, board[r][c], r, c)
visited[r][c] = False
print(max_value)
solve()⭐ 2. 백준 12852 (1로 만들기 2)
# 2. 알고(DP): 백준 12852 (1로 만들기 2) - https://www.acmicpc.net/problem/12852
import sys
from io import StringIO
sys.stdin = StringIO('''10''')
input = sys.stdin.readline
def solve():
N = int(input())
# i를 만들 수 있는 최소 횟수
dp = [0] * (N + 1)
path = [0] * (N + 1) # 이전 값 (부모 추적)
for i in range(2, N + 1):
# 1 더하기
dp[i] = dp[i - 1] + 1
path[i] = i - 1
# 2 곱하기
if i % 2 == 0 and dp[i] > dp[i//2] + 1: # 이전방식보다 새 방식이 더 짧으면
dp[i] = dp[i//2] + 1
path[i] = i // 2
# 3 곱하기
if i % 3 == 0 and dp[i] > dp[i//3] + 1:
dp[i] = dp[i//3] + 1
path[i] = i // 3
history = list()
cur = N
while cur != 0:
history.append(cur)
cur = path[cur]
print(dp[N])
print(*history)
solve()⭐ 3. 백준 1261 (알고스팟)
# 3. 알고(그래프): 백준 1261 (알고스팟) - https://www.acmicpc.net/problem/1261
import sys
from collections import deque
from io import StringIO
sys.stdin = StringIO('''6 6
001111
010000
001111
110001
011010
100010''')
input = sys.stdin.readline
def solve():
M, N = map(int, input().split())
board = [input().rstrip() for _ in range(N)]
directions = [(0, -1), (0, +1), (-1, 0), (+1, 0)]
broken = [[-1] * M for _ in range(N)]
dq = deque([(0, 0)])
broken[0][0] = 0
while dq:
r, c = dq.popleft()
if r == N - 1 and c == M - 1:
print(broken[r][c])
return
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < M and broken[nr][nc] == -1:
nxt_val = board[nr][nc]
if nxt_val == '0': # 왼쪽에 넣어서 비용 최소값 보장
dq.appendleft((nr, nc))
broken[nr][nc] = broken[r][c]
else:
dq.append((nr, nc))
broken[nr][nc] = broken[r][c] + 1
solve()⭐ 4. 백준 18429 (근성장)
# 4. 알고(백트래킹): 백준 18429 (근성장) - https://www.acmicpc.net/problem/18429
import sys
from io import StringIO
sys.stdin = StringIO('''3 4
3 7 5''')
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
weight = sorted(map(int, input().split())) # 정렬을 통한 최적화
used_kit = [False] * N
count = 0
# 사용 갯수, 여분
def dfs(use_cnt, margin):
nonlocal count
if margin < 500: # 운동마치고, 감소된 결과 체크
return
if use_cnt == N:
count += 1
return
# 사용 가능한 키트
for i in range(N):
if not used_kit[i]:
used_kit[i] = True
dfs(use_cnt + 1, margin + weight[i] - K) # 운동 후 감소까지 완료.
used_kit[i] = False
dfs(0, 500)
print(count)
solve()✏️ 5. SQL 년, 월, 성별 별 상품 구매 회원 수 구하기
-- 5. SQL(Lv.4): 년, 월, 성별 별 상품 구매 회원 수 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/131532
WITH
YM AS (
SELECT DISTINCT
YEAR(SALES_DATE) AS YEAR,
MONTH(SALES_DATE) AS MONTH,
USER_ID
FROM ONLINE_SALE
)
SELECT
YM.YEAR,
YM.MONTH,
UI.GENDER,
COUNT(*) AS USERS
FROM YM
JOIN USER_INFO UI USING (USER_ID)
WHERE UI.GENDER IS NOT NULL
GROUP BY
YM.YEAR, YM.MONTH, UI.GENDER
ORDER BY
YM.YEAR, YM.MONTH, UI.GENDER;