SejongClass

24_회차_D-07

9 min read

✅ 24 회차 모의고사 D-07일

🚨 강의영상링크

🚀 1차 코딩테스트 대비

  1. 백준 16927 (배열 돌리기 2)
  2. 백준 2485 (가로수)
  3. 백준 1927 (최소 힙)
  4. 백준 1744 (수 묶기)
  5. SQL ROOT 아이템 구하기

👨‍🏫 COLAB

1차 풀이

⭐ 1. 백준 16927 (배열 돌리기 2)

# 1. 알고(구현): 백준 16927 (배열 돌리기 2) - https://www.acmicpc.net/problem/16927
import sys
from collections import deque
 
from io import StringIO
sys.stdin = StringIO('''5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28''')
 
input = sys.stdin.readline
 
def solve():
 
    N, M, R = map(int, input().split())
    directions = [(+1, 0), (0, +1), (-1, 0), (0, -1)]
 
    board = [list(map(int, input().split())) for _ in range(N)]
    layers = min(N, M) // 2
 
    for layer in range(layers):
        sr, er = layer, N-1 - layer
        sc, ec = layer, M-1 - layer
 
        r = c = layer
        visited = [(r, c)]
        values = deque([board[r][c]])
 
        d = 0
        cur_r, cur_c = r, c
 
        while True:
 
            dr, dc = directions[d]
            nr, nc = cur_r + dr, cur_c + dc
            in_range = sr <= nr <= er and sc <= nc <= ec
 
            if not in_range:
                d += 1
                dr, dc = directions[d]
                nr, nc = cur_r + dr, cur_c + dc
 
            if (nr, nc) == (r, c):
                break
 
            visited.append((nr, nc))
            values.append(board[nr][nc])
 
            cur_r, cur_c = nr, nc
 
        values.rotate(R)
        for i, (vr, vc) in enumerate(visited):
            board[vr][vc] = values[i]
 
    print("\n".join(" ".join(map(str, row)) for row in board))
 
solve()

⭐ 2. 백준 2485 (가로수)

# 2. 알고(수학): 백준 2485 (가로수) - https://www.acmicpc.net/problem/2485
import sys
from math import gcd
from functools import reduce
 
from io import StringIO
sys.stdin = StringIO('''4
2
6
12
18''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    nums = [int(input()) for _ in range(N)]
    diffs = set(nums[i+1] - nums[i] for i in range(N-1))
 
    gcd_val = reduce(gcd, diffs)
    all_tree = len(range(nums[0], nums[-1] + 1, gcd_val))
 
    print(all_tree - N)
 
solve()

⭐ 3. 백준 1927 (최소 힙)

# 3. 알고(Heap): 백준 1927 (최소 힙) - https://www.acmicpc.net/problem/1927
import sys
from heapq import heappop, heappush
 
from io import StringIO
sys.stdin = StringIO('''9
0
12345678
1
2
0
0
0
0
32''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    out = []
    pq = []
 
    for _ in range(N):
        num = int(input())
 
        if not num:
            out.append(str(heappop(pq)) if pq else '0')
        else:
            heappush(pq, num)
 
    print("\n".join(out))
 
solve()

⭐ 4. 백준 1744 (수 묶기)

# 4. 알고(그리디): 백준 1744 (수 묶기) - https://www.acmicpc.net/problem/1744
import sys
 
from io import StringIO
sys.stdin = StringIO('''6
0
1
2
4
3
5''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    pos = []
    neg = []
    ones = 0
    zero = 0
 
    for _ in range(N):
        num = int(input())
        if num > 1:
            pos.append(num)
        elif num == 1:
            ones += 1
        elif num == 0:
            zero += 1
        else:
            neg.append(num)
 
    pos.sort(reverse=True)
    neg.sort()
 
    ans = 0
 
    for i in range(0, len(pos) - 1, 2):
        ans += pos[i] * pos[i+1]
 
    if len(pos) % 2 == 1:
        ans += pos[-1]
 
    for i in range(0, len(neg) - 1, 2):
        ans += neg[i] * neg[i+1]
 
    if len(neg) % 2 == 1 and zero == 0:
        ans += neg[-1]
 
    ans += ones
 
    print(ans)
 
solve()

✏️ 5. SQL ROOT 아이템 구하기

-- 5. SQL(Lv.2): ROOT 아이템 구하기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/273710
WITH
    RI AS (
        SELECT
            ITEM_ID
        FROM
            ITEM_TREE
        WHERE
            PARENT_ITEM_ID IS NULL
    )
SELECT
    ITEM_ID,
    ITEM_NAME
FROM RI
JOIN ITEM_INFO USING (ITEM_ID)
ORDER BY
    ITEM_ID ASC;

🚀 2차 코딩테스트 대비

  1. 백준 19236 (청소년 상어)
  2. 백준 2133 (타일 채우기)
  3. 백준 11725 (트리의 부모 찾기)
  4. 백준 17471 (게리맨더링)
  5. SQL 헤비 유저가 있는 장소

👨‍🏫 COLAB

2차 풀이

⭐ 1. 백준 19236 (청소년 상어)

# 1. 알고(시뮬): 백준 19236 (청소년 상어) - https://www.acmicpc.net/problem/19236
import sys
from copy import deepcopy
 
from io import StringIO
sys.stdin = StringIO('''12 6 14 5 4 5 6 7
15 1 11 7 3 7 7 5
10 3 8 3 16 6 1 1
5 8 2 7 13 6 9 2''')
 
input = sys.stdin.readline
 
def solve():
    directions = [
        (-1, 0), (-1, -1), (0, -1), (+1, -1),   # ↑, ↖, ←, ↙,
        (+1, 0), (+1, +1), (0, +1), (-1, +1)    # ↓, ↘, →, ↗
    ]
 
    N = 4
    origin_board = [[None] * N for _ in range(N)]
    origin_posi = [None] * (N * N)
 
    for r in range(N):
        row = list(map(int, input().split()))
        for c in range(N):
            num, d = (row[2*c]-1), (row[2*c+1]-1)
            origin_board[r][c] = [num, d]
            origin_posi[num] = (r, c)
 
    max_score = 0   # 정답
 
    def dfs(sr, sc, score, board, posi):
        nonlocal max_score
 
        # 상어 사냥
        fish_num, sd = board[sr][sc]
        score += (fish_num + 1)  # 1 인덱스 복원
        max_score = max(max_score, score)
 
        board[sr][sc] = [-1, sd]    # -1 : 사냥 후 물고기 없음, 물고기 방향 입력.
        posi[fish_num] = None
 
        # 사냥 후 물고기 이동
        for i in range(N * N):
            if posi[i] is None:
                continue
 
            r, c = posi[i]
            f_num, fd = board[r][c]
 
            for step in range(8):
                nd = (fd + step) % 8
                dr, dc = directions[nd]
 
                nr, nc = r + dr, c + dc
                in_range = 0 <= nr < N and 0 <= nc < N
 
                if not in_range or (nr, nc) == (sr, sc):    # 상어 있으면 못감
                    continue
 
                nxt_fish_num = board[nr][nc][0]       # -1 이면 빈칸
 
                board[r][c][1] = nd                   # 방향 정보 저장 후 교환
                board[r][c], board[nr][nc] = board[nr][nc], board[r][c]
 
                posi[f_num] = (nr, nc)
                if nxt_fish_num != -1:              # 빈칸이 아닌 경우
                    posi[nxt_fish_num] = (r, c)
 
                break
 
        # 상어이동
        dr, dc = directions[sd]
        for dist in range(1, N):
            nr, nc = sr + dr*dist, sc + dc*dist
            in_range = 0 <= nr < N and 0 <= nc < N
 
            if not in_range:        # 범위 벗어나면 종료
                break
 
            if board[nr][nc][0] == -1:  # 빈 공간이면 다음 칸 탐색
                continue
 
            dfs(nr, nc, score, deepcopy(board), deepcopy(posi))
 
    dfs(0, 0, 0, deepcopy(origin_board), deepcopy(origin_posi))
    print(max_score)
 
solve()

⭐ 2. 백준 2133 (타일 채우기)

# 2. 알고(DP): 백준 2133 (타일 채우기) - https://www.acmicpc.net/problem/2133
import sys
 
from io import StringIO
sys.stdin = StringIO('''2''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    if N % 2 != 0:
        return print(0) # 홀수 불가
 
    # dp[i] 3 * i 크기를 채우는 경우의 수
    dp = [0] * (N + 1) 
 
    dp[0] = 1   
 
    if N >= 2 :
        dp[2] = 3   # 2칸 채우는 방법은 3개
 
    for i in range(4, N + 1, 2):
        dp[i] = dp[i-2] * 3         # 맨 오른쪽에 2개 모양 고정 후 뒤 모양
 
        for j in range(i - 4, -1, -2):  # 맨 오른쪽에 4개 모양 고정 후 2개씩 
            dp[i] += dp[j] * 2
 
    print(dp[N])
 
solve()

⭐ 3. 백준 11725 (트리의 부모 찾기)

# 3. 알고(트리): 백준 11725 (트리의 부모 찾기) - https://www.acmicpc.net/problem/11725
import sys
 
from io import StringIO
sys.stdin = StringIO('''12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    graph = [[] for _ in range(N+1)]
 
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    parent = [0] * (N+1)    # 0 은 방문 안함
    parent[1] = -1          # -1 은 루트
 
    stack = [1]
    while stack:
        cur = stack.pop()
 
        for nxt in graph[cur]:
            if parent[nxt] != 0:
                continue
 
            parent[nxt] = cur
            stack.append(nxt)
 
    print("\n".join(map(str, parent[2:])))
 
solve()

⭐ 4. 백준 17471 (게리맨더링)

# 4. 알고(그래프): 백준 17471 (게리맨더링) - https://www.acmicpc.net/problem/17471
import sys
from itertools import combinations
 
from io import StringIO
sys.stdin = StringIO('''6
5 2 3 4 1 2
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    popul = tuple(map(int, input().split()))
    graph = [[] for _ in range(N)]
 
    for i in range(N):
        _, *nodes = map(int, input().split())
        for node in nodes:
            graph[i].append(node-1)
 
    def is_connected(node_set):
        start = next(iter(node_set))
        stack = [start]
        visited = {start}
 
        while stack:
            cur = stack.pop()
            for nxt in graph[cur]:
                if nxt not in node_set:
                    continue
 
                if nxt in visited:
                    continue
 
                visited.add(nxt)
                stack.append(nxt)
 
        return len(visited) == len(node_set)
 
    min_diff = INF = float('inf')
    other_nodes = set(range(1, N))     # 0 제외
 
    for size in range(N-1):            # 0 번 고정
        for extra in combinations(other_nodes, size):
            area_a = {0, *extra}
            area_b = other_nodes.difference(extra)
 
            if is_connected(area_a) and is_connected(area_b):
                sum_a = sum(popul[node] for node in area_a)
                sum_b = sum(popul[node] for node in area_b)
                min_diff = min(min_diff, abs(sum_a - sum_b))
 
                if min_diff == 0:
                    return print(0)
 
    print(min_diff if min_diff != INF else -1)
 
solve()

✏️ 5. SQL 헤비 유저가 있는 장소

-- 5. SQL(Lv.3): 헤비 유저가 있는 장소 
-- https://school.programmers.co.kr/learn/courses/30/lessons/77487
WITH 
    NOTBIG AS (
        SELECT *,
            COUNT(*) OVER(
	            PARTITION BY HOST_ID
            ) AS CNT
        FROM PLACES
    ) 
 
SELECT
    ID,
    NAME,
    HOST_ID
FROM NOTBIG
WHERE CNT >= 2
ORDER BY ID;

그래프 뷰