SejongClass

19_회차_D-12

10 min read

✅ 19 회차 모의고사 D-12일

🚨 강의영상링크

🚀 1차 코딩테스트 대비

  1. 백준 3085 (사탕 게임)
  2. 백준 1016 (제곱 ㄴㄴ 수)
  3. 백준 2776 (암기왕)
  4. 백준 13904 (과제)
  5. SQL 조건에 부합하는 중고거래 상태 조회하기

👨‍🏫 COLAB

1차 풀이

⭐ 1. 백준 3085 (사탕 게임)

# 1. 알고(구현): 백준 3085 (사탕 게임) - https://www.acmicpc.net/problem/3085
import sys
from itertools import product
 
from io import StringIO
sys.stdin = StringIO('''3
CCP
CCP
PPC''')
 
input = sys.stdin.readline
 
def solve():
 
    N = int(input())
    board = [list(input().rstrip()) for _ in range(N)]
 
    def check(r, c):
        base = board[r][c]
 
        max_hori = 1
        stack, visited = [c], {c}
        while stack:
            cur_c = stack.pop()
            for dc in [-1, +1]:
                nc = cur_c + dc
                if 0 <= nc < N and nc not in visited:
                    if base == board[r][nc]:
                        stack.append(nc)
                        visited.add(nc)
                        max_hori += 1
 
        max_vert = 1
        stack, visited = [r], {r}
        while stack:
            cur_r = stack.pop()
            for dr in [-1, +1]:
                nr = cur_r + dr
                if 0 <= nr < N and nr not in visited:
                    if base == board[nr][c]:
                        stack.append(nr)
                        visited.add(nr)
                        max_vert += 1
 
        return max(max_hori, max_vert)
 
    answer = 0
    for r, c in product(range(N), repeat=2):
        answer = max(answer, check(r, c))
 
    for r, c in product(range(N), repeat=2):
        for dr, dc in [(0, +1), (+1, 0)]:
            nr, nc = r + dr, c + dc
            if nr < N and nc < N and board[r][c] != board[nr][nc]:
                board[r][c], board[nr][nc] = board[nr][nc], board[r][c]
                answer = max(answer, check(r, c), check(nr, nc))
                board[r][c], board[nr][nc] = board[nr][nc], board[r][c]
 
    print(answer)
 
solve()

⭐ 2. 백준 1016 (제곱 ㄴㄴ 수)

# 2. 알고(수학): 백준 1016 (제곱 ㄴㄴ 수) - https://www.acmicpc.net/problem/1016
import sys
from math import isqrt
 
from io import StringIO
sys.stdin = StringIO('''1 1000''')
 
input = sys.stdin.readline
 
def solve():
    MIN, MAX = map(int, input().split())
 
    trying = MAX-MIN + 1
    is_nono = [True] * trying
 
    for i in range(2, isqrt(MAX) + 1):
        nomer = i*i
        remain = MIN % nomer
        start = MIN if remain == 0 else MIN - remain + nomer
 
        for sqr_num in range(start, MAX + 1, nomer):
            is_nono[sqr_num - MIN] = False
 
    print(is_nono.count(True))
 
solve()

⭐ 3. 백준 2776 (암기왕)

# 3. 알고(Map): 백준 2776 (암기왕) - https://www.acmicpc.net/problem/2776
import sys
 
from io import StringIO
sys.stdin = StringIO('''1
5
4 1 5 2 3
5
1 3 7 9 5''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    nums = set(input().split())
 
    M = int(input())
    answers = map(lambda x: '1' if x in nums else '0', input().split())
 
    print("\n".join(answers))
 
T = int(input())
for _ in range(T):
    solve()

⭐ 4. 백준 13904 (과제)

# 4. 알고(그리디): 백준 13904 (과제) - https://www.acmicpc.net/problem/13904
import sys
from bisect import bisect_left
 
from io import StringIO
sys.stdin = StringIO('''7
4 60
4 40
1 20
2 50
3 30
4 10
6 5''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    # 딕셔너리로 같은 날짜들을 뫃아두고 힙을 이용해 푸는 방식도 있음
    tasks = [tuple(map(int, input().split())) for _ in range(N)]
    tasks.sort()
 
    max_day = tasks[-1][0]
 
    score = 0
    for day in range(max_day, 0, -1):
        can_solve_idx = bisect_left(tasks, day, key=lambda x: x[0])
 
        solve_idx = -1
        max_value = 0
        for i in range(can_solve_idx, len(tasks)):
            if tasks[i][1] >= max_value:
                solve_idx = i
                max_value = tasks[i][1]
 
        if solve_idx != -1:
            score += max_value
            del tasks[solve_idx]
 
    print(score)
 
solve()

✏️ 5. SQL 조건에 부합하는 중고거래 상태 조회하기

--  5. SQL(Lv.2): 조건에 부합하는 중고거래 상태 조회하기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/164672
SELECT
    BOARD_ID,
    WRITER_ID,
    TITLE,
    PRICE,
    CASE
        WHEN STATUS = 'SALE' THEN '판매중'
        WHEN STATUS = 'RESERVED' THEN '예약중'
        WHEN STATUS = 'DONE' THEN '거래완료'
    END AS STATUS
FROM
    USED_GOODS_BOARD
WHERE
    CREATED_DATE = '2022-10-05'
ORDER BY
    BOARD_ID DESC;

🚀 2차 코딩테스트 대비

  1. 백준 23288 (주사위 굴리기 2)
  2. 백준 14002 (가장 긴 증가하는 부분 수열 4)
  3. 백준 5972 (택배 배송)
  4. 백준 3980 (선발 명단)
  5. SQL 그룹별 조건에 맞는 식당 목록 출력하기

👨‍🏫 COLAB

2차 풀이

⭐ 1. 백준 23288 (주사위 굴리기 2)

# 1. 알고(시뮬): 백준 23288 (주사위 굴리기 2) - https://www.acmicpc.net/problem/23288
import sys
from itertools import product
 
from io import StringIO
sys.stdin = StringIO('''4 5 1000
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5''')
 
input = sys.stdin.readline
 
def solve():
    N, M, K = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
 
    # 0 동, 1 남, 2 서, 3 북
    directions = [(0, +1), (+1, 0), (0, -1), (-1, 0)]
    dice = [1, 6, 3, 4, 5, 2]  # 위, 아래, 오른(동), 왼(서), 앞(남), 뒤(북)
 
    def roll(dir):
        top, botom, right, left, front, back = dice
        if dir == 0:            # 동 (오른)
            dice[:] = [left, right, top, botom, front, back]
 
        elif dir == 1:          # 남 (아래)
            dice[:] = [back, front, right, left, top, botom]
 
        elif dir == 2:          # 서 (왼)
            dice[:] = [right, left, botom, top, front, back]
 
        elif dir == 3:          # 북 (위)
            dice[:] = [front, back, right, left, botom, top]
 
    # 각 칸별 점수 미리 계산
    visited = [[False] * M for _ in range(N)]
    score_board = [[0] * M for _ in range(N)]
 
    def dfs(r, c):
        base = board[r][c]
        stack = [(r, c)]
        visited[r][c] = True
 
        for_score = [(r, c)]
        visit_sum = base
 
        while stack:
            cr, cc = stack.pop()
            for dr, dc in directions:
                nr, nc = cr + dr, cc + dc
                if not (0 <= nr < N and 0 <= nc < M):
                    continue
 
                if board[nr][nc] == base and not visited[nr][nc]:
                    visited[nr][nc] = True
                    visit_sum += board[nr][nc]
 
                    stack.append((nr, nc))
                    for_score.append((nr, nc))
 
        for row, col in for_score:  # 점수 갱신
            score_board[row][col] = visit_sum
 
    for r, c in product(range(N), range(M)):
        if not visited[r][c]:
            dfs(r, c)
 
    # 게임 시작.
    sqre_posi = [0, 0, 0]   # row, col, dirs
    score = 0
 
    while K > 0:
        r, c, dir = sqre_posi
 
        dr, dc = directions[dir]
        nr, nc = r + dr,  c + dc
        if not (0 <= nr < N and 0 <= nc < M):   # 넘어가면 반대 방향으로 전환
            dir = (dir + 2) % 4
            dr, dc = directions[dir]
            nr, nc = r + dr,  c + dc
 
        roll(dir)                       # 1. 이동 방향 정하고, 주사위 굴리기
        score += score_board[nr][nc]    # 2. 점수 획득
 
        A = dice[1]
        B = board[nr][nc]               # 3. 다음 방향 설정
        nxt_dir = (dir + 1) % 4 if A > B else (dir - 1) % 4 if A < B else dir
 
        sqre_posi = [nr, nc, nxt_dir]   # 주사위 정보 입력
        K -= 1                          # 다음턴
 
    print(score)
 
solve()

⭐ 2. 백준 14002 (가장 긴 증가하는 부분 수열 4)

# 2. 알고(DP): 백준 14002 (가장 긴 증가하는 부분 수열 4) - https://www.acmicpc.net/problem/14002
import sys
 
from io import StringIO
sys.stdin = StringIO('''6
10 20 10 30 20 50''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    nums = list(map(int, input().split()))
 
    # 가장 긴 증가하는 수열 길이
    dp = [1] * N
    prev = list(range(N))  # 이전 노드 인덱스
 
    for i in range(1, N):
        for j in range(i):
            if nums[j] < nums[i]:
                if dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j
 
    i = dp.index(max(dp))
    answer = [nums[i]]
 
    while prev[i] != i:
        i = prev[i]
        answer.append(nums[i])
 
    answer.reverse()
    print(len(answer))
    print(*answer)
 
solve()

⭐ 3. 백준 5972 (택배 배송)

# 3. 알고(그래프): 백준 5972 (택배 배송) - https://www.acmicpc.net/problem/5972
import sys
from heapq import heappush, heappop
 
from io import StringIO
sys.stdin = StringIO('''6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4''')
 
input = sys.stdin.readline
 
def solve():
    N, M = map(int, input().split())
 
    graph = [[] for _ in range(N + 1)]
 
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
 
    min_cost = [float('inf')] * (N + 1)
    min_cost[1] = 0
    pq = [(0, 1)]
 
    while pq:
        cur_cost, cur = heappop(pq)
        if cur == N:
            break
 
        if cur_cost > min_cost[cur]:
            continue
 
        for nxt, cost in graph[cur]:
            nxt_cost = cur_cost + cost
            if nxt_cost < min_cost[nxt]:
                min_cost[nxt] = nxt_cost
                heappush(pq, (nxt_cost, nxt))
                
    print(min_cost[N])
 
solve()

⭐ 4. 백준 3980 (선발 명단)

# 4. 알고(백트래킹): 백준 3980 (선발 명단) - https://www.acmicpc.net/problem/3980
import sys
 
from io import StringIO
sys.stdin = StringIO('''1
100 0 0 0 0 0 0 0 0 0 0
0 80 70 70 60 0 0 0 0 0 0
0 40 90 90 40 0 0 0 0 0 0
0 40 85 85 33 0 0 0 0 0 0
0 70 60 60 85 0 0 0 0 0 0
0 0 0 0 0 95 70 60 60 0 0
0 45 0 0 0 80 90 50 70 0 0
0 0 0 0 0 40 90 90 40 70 0
0 0 0 0 0 0 50 70 85 50 0
0 0 0 0 0 0 66 60 0 80 80
0 0 0 0 0 0 50 50 0 90 88''')
 
input = sys.stdin.readline
 
def solve():
    players = [tuple(map(int, input().split())) for _ in range(11)]
 
    max_sum = 0
 
    def dfs(confirm, ability_sum, bit_mask):
        nonlocal max_sum
 
        if confirm == 11:
            max_sum = max(max_sum, ability_sum)
            return
 
        for i, score in enumerate(players[confirm]):
            if score == 0 or bit_mask & (1 << i):
                continue
 
            dfs(confirm + 1, ability_sum + score, bit_mask | (1 << i))
 
    dfs(0, 0, 0)
    print(max_sum)
 
T = int(input())
for _ in range(T):
    solve()

✏️ 5. SQL 그룹별 조건에 맞는 식당 목록 출력하기

-- 5. SQL(Lv.4): 그룹별 조건에 맞는 식당 목록 출력하기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/131124
WITH
    BEST_RV AS (
        SELECT 
            MEMBER_ID,
            RANK() OVER (
                ORDER BY
                    COUNT(*) DESC
            ) AS RNK
        FROM 
            REST_REVIEW
        GROUP BY
            MEMBER_ID
    )
 
SELECT
    MEMBER_NAME,
    REVIEW_TEXT,
    DATE_FORMAT(REVIEW_DATE, '%Y-%m-%d') AS REVIEW_DATE
FROM BEST_RV
JOIN REST_REVIEW  USING (MEMBER_ID)
JOIN MEMBER_PROFILE USING (MEMBER_ID)
WHERE RNK = 1
ORDER BY
    REVIEW_DATE ASC,
    REVIEW_TEXT ASC;

그래프 뷰