SejongClass

08_회차_D-23

8 min read

✅ 08 회차 모의고사 D-23일

🚨 강의영상링크

🚀 1차 코딩테스트 대비

  1. 백준 20006 (랭킹전 대기열)
  2. 백준 17087 (숨바꼭질 6)
  3. 백준 13414 (수강신청)
  4. 백준 16953 (A → B)
  5. SQL 자동차 평균 대여 기간 구하기

👨‍🏫 COLAB

1차 풀이

⭐ 1. 백준 20006 (랭킹전 대기열)

# 1. 알고(구현): 백준 20006 (랭킹전 대기열) - https://www.acmicpc.net/problem/20006
import sys
 
from io import StringIO
sys.stdin = StringIO('''10 5
10 a
15 b
20 c
25 d
30 e
17 f
18 g
26 h
24 i
28 j''')
 
input = sys.stdin.readline
 
def solve():
 
    p, m = map(int, input().split())
    rooms = []
 
    for _ in range(p):
        level, nick = input().split()
        level = int(level)
        for room in rooms:
            if len(room) < m:
                base_level = room[0][0]
                if base_level-10 <= level <= base_level+10:
                    room.append((level, nick))
                    break
        else:
            rooms.append([(level, nick)])
 
    for room in rooms:
        print('Started!' if len(room) == m else 'Waiting!')
        room.sort(key=lambda x: (x[1]))
        print("\n".join(map(lambda x: f"{x[0]} {x[1]}", room)))
 
solve()

⭐ 2. 백준 17087 (숨바꼭질 6)

# 2. 알고(수학): 백준 17087 (숨바꼭질 6) - https://www.acmicpc.net/problem/17087
import sys
from math import gcd
from io import StringIO
sys.stdin = StringIO('''3 81
33 105 57''')
 
input = sys.stdin.readline
 
def solve():
    N, S = map(int, input().split())
    nums = map(lambda x: abs(int(x) - S), input().split())
    print(gcd(*nums))
 
solve()

⭐ 3. 백준 13414 (수강신청)

# 3. 알고(Map): 백준 13414 (수강신청) - https://www.acmicpc.net/problem/13414
import sys
from itertools import islice
 
from io import StringIO
sys.stdin = StringIO('''3 8
20103324
20133221
20133221
20093778
20140101
01234567
20093778
20103325''')
 
input = sys.stdin.readline
 
def solve():
    K, L = map(int, input().split())
 
    student_ids = dict()
 
    for order in range(L):
        student_ids[input().rstrip()] = order
 
    students = sorted(student_ids.items(), key=lambda x: x[1])
    print("\n".join(stu_id for stu_id, _ in islice(students, K)))
 
solve()

⭐ 4. 백준 16953 (A → B)

# 4. 알고(그리디): 백준 16953 (A -> B) - https://www.acmicpc.net/problem/16953
import sys
from collections import deque
 
from io import StringIO
sys.stdin = StringIO('''100 40021''')
 
input = sys.stdin.readline
 
def solve():
 
    A, B = map(int, input().split())
 
    dq = deque([(A, 1)])  # 숫자, 깊이
    answer = -1
 
    while dq:
        cur, depth = dq.popleft()
        depth += 1
 
        nxt_mul = cur * 2
        nxt_add = int(str(cur) + '1')
 
        if nxt_mul == B or nxt_add == B:
            answer = depth
            break
 
        if nxt_mul < B:
            dq.append((nxt_mul, depth))
 
        if nxt_add < B:
            dq.append((nxt_add, depth))
 
    print(answer)
 
solve()

✏️ 5. SQL 자동차 평균 대여 기간 구하기

-- 5. SQL(Lv.2): 자동차 평균 대여 기간 구하기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/157342
SELECT
    CAR_ID,
    ROUND(AVG(DATEDIFF(END_DATE, START_DATE) + 1 ) , 1) AS AVERAGE_DURATION
FROM 
    CAR_RENTAL_COMPANY_RENTAL_HISTORY
GROUP BY
    CAR_ID
HAVING 
    AVERAGE_DURATION >= 7
ORDER BY
    AVERAGE_DURATION DESC,
    CAR_ID DESC;

🚀 2차 코딩테스트 대비

  1. 백준 17140 (이차원 배열과 연산)
  2. 백준 11054 (가장 긴 바이토닉 부분 수열)
  3. 백준 1967 (트리의 지름)
  4. 백준 16197 (두 동전)
  5. SQL 식품분류별 가장 비싼 식품의 정보 조회하기

👨‍🏫 COLAB

2차 풀이

⭐ 1. 백준 17140 (이차원 배열과 연산)

# 1. 알고(시뮬): 백준 17140 (이차원 배열과 연산) - https://www.acmicpc.net/problem/17140
import sys
from collections import Counter
from itertools import islice
 
from io import StringIO
sys.stdin = StringIO('''1 2 4
1 2 1
2 1 3
3 3 3''')
 
input = sys.stdin.readline
 
def solve():
    r, c, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(3)]
 
    def R(board):
        max_row_len = 0
        results = []
 
        for row in board:
            count = Counter(row)
            count.pop(0, None)  # 0 제거
            sorted_lst = sorted(count.items(), key=lambda x: (x[1], x[0])) # 갯수 -> 숫자 순 정렬
 
            row_result = []
            for num, cnt in islice(sorted_lst, 50):
                row_result.extend([num, cnt])
 
            results.append(row_result)
            max_row_len = max(max_row_len, len(row_result))  # 결과값중 가장 긴 값 저장.
 
        new_board = [[0] * max_row_len for _ in range(len(board))]
 
        for i, result in enumerate(results):  # 배열 생성.
            new_board[i][:len(result)] = result
 
        return new_board
 
    def C(board):
        transposed = list(zip(*board))
        new_list = R(transposed)
        recovered = list(map(list, zip(*new_list)))  # 리스트 형태로 복원.
        return recovered
 
    check_board = board
 
    for i in range(101):
        row_len = len(check_board)
        col_len = len(check_board[0])
 
        if r <= row_len and c <= col_len and check_board[r-1][c-1] == k:
            print(i)
            break
 
        if row_len >= col_len:
            check_board = R(check_board)
        else:
            check_board = C(check_board)
 
    else:
        print(-1)
 
solve()

⭐ 2. 백준 11054 (가장 긴 바이토닉 부분 수열)

# 2. 알고(DP): 백준 11054 (가장 긴 바이토닉 부분 수열) - https://www.acmicpc.net/problem/11054
import sys
 
from io import StringIO
sys.stdin = StringIO('''10
1 5 2 1 4 3 4 5 2 1''')
 
input = sys.stdin.readline
 
def solve():
 
    n = int(input())
    nums = tuple(map(int, input().split()))
 
    # 자신을 포함해서 왼쪽에 나보다 작은 수의 개수
    dp_up = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp_up[i] = max(dp_up[i], dp_up[j] + 1)
 
    dp_down = [1] * n
    for i in range(n-1, -1, -1):
        for j in range(n-1, i, -1):
            if nums[j] < nums[i]:
                dp_down[i] = max(dp_down[i], dp_down[j] + 1)
 
    max_len = 0
    for i in range(n):
        max_len = max(max_len, dp_up[i] + dp_down[i] - 1)  # 자기 자신 제외
 
    print(max_len)
 
solve()

⭐ 3. 백준 1967 (트리의 지름)

# 3. 알고(트리): 백준 1967 (트리의 지름) - https://www.acmicpc.net/problem/1967
import sys
from collections import deque
from random import randint
 
from io import StringIO
sys.stdin = StringIO('''12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10''')
 
input = sys.stdin.readline
 
def solve():
    n = int(input())
    tree = [[] for _ in range(n + 1)]
 
    for _ in range(n-1):
        a, b, c = map(int, input().split())
        tree[a].append((b, c))
        tree[b].append((a, c))
 
    def bfs(start):
 
        dists = [-1] * (n+1)
        dists[start] = 0
 
        dq = deque([start])  # 노드번호
        while dq:
            cur = dq.popleft()
 
            for nxt, cost in tree[cur]:
                if dists[nxt] == -1:
                    dists[nxt] = dists[cur] + cost
                    dq.append(nxt)
 
        return max((d, i) for i, d in enumerate(dists))
 
    _, max_node = bfs(randint(1, n))    # 무작위로 하나 넣고
    max_dist, _ = bfs(max_node)         # 제일 멀리 있는 노드에서 다시 탐색
 
    print(max_dist)
 
solve()

⭐ 4. 백준 16197 (두 동전)

# 4. 알고(백트래킹): 백준 16197 (두 동전) - https://www.acmicpc.net/problem/16197
import sys
from itertools import product
from collections import deque
 
from io import StringIO
sys.stdin = StringIO('''6 2
..
..
..
o#
o#
##''')
 
input = sys.stdin.readline
 
def solve():
    N, M = map(int, input().split())
 
    board = [['e'] * (M + 2)]
    for _ in range(N):
        board.append(['e'] + list(input().rstrip()) + ['e'])
    board.append(['e'] * (M + 2))
 
    cur_coins = []      # [r1, c1, r2, c2]
    for r, c in product(range(1, N+1), range(1, M + 1)):
        if board[r][c] == 'o':
            cur_coins.extend([r, c])
 
    directions = [(0, -1), (0, +1), (-1, 0), (+1, 0)]
 
    dq = deque([tuple(cur_coins + [0])])  # 거리 하나 추가.
    visited = set(tuple(cur_coins))
 
    while dq:
        r1, c1, r2, c2, dist = dq.popleft()
        
        if dist == 10: # 11번째 이동을 고려하기 시작할 때 종료.
            break
 
        dist += 1       # 단계 추가.
        for dr, dc in directions:
            nr1, nc1 = r1 + dr, c1 + dc
            nr2, nc2 = r2 + dr, c2 + dc
 
            nxt1 = board[nr1][nc1]
            nxt2 = board[nr2][nc2]
 
            drop1 = (nxt1 == 'e')
            drop2 = (nxt2 == 'e')
 
            if drop1 and drop2:   # 둘다 낭떨어지면 패스
                continue
 
            if drop1 or drop2:    # 하나만 낭 떨어지면 성공!
                print(dist)
                return
 
            if nxt1 == "#":       # 벽이면 다음 위치를 이전 위치로 복귀
                nr1, nc1 = r1, c1
            if nxt2 == "#":
                nr2, nc2 = r2, c2
 
            # 둘중 하나라도 이동할 수 있다면 (동전 겹치기 가능)
            if (nr1, nc1, nr2, nc2) not in visited:
                dq.append((nr1, nc1, nr2, nc2, dist))  # 다음 단계 추가.
                visited.add((nr1, nc1, nr2, nc2))
 
    print(-1)
 
solve()

✏️ 5. SQL 식품분류별 가장 비싼 식품의 정보 조회하기

-- 5. SQL(Lv.4): 식품분류별 가장 비싼 식품의 정보 조회하기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/131116
WITH RP AS (
    SELECT 
        CATEGORY,
        PRICE,
        PRODUCT_NAME,
        RANK() OVER (
            PARTITION BY
                CATEGORY
            ORDER BY
                PRICE DESC
            ) RANKING
    FROM 
        FOOD_PRODUCT
    WHERE
        CATEGORY IN ('과자', '국', '김치', '식용유')
)
SELECT
    CATEGORY,
    PRICE AS MAX_PRICE,
    PRODUCT_NAME
FROM 
    RP
WHERE
    RANKING = 1
ORDER BY
    MAX_PRICE DESC;

그래프 뷰