SejongClass

11_회차_D-20

9 min read

✅ 11 회차 모의고사 D-20일

🚨 강의영상링크

🚀 1차 코딩테스트 대비

  1. 백준 10825 (국영수)
  2. 백준 11051 (이항 계수 2)
  3. 백준 20291 (파일 정리)
  4. 백준 1141 (접두사)
  5. SQL 상위 n개 레코드

👨‍🏫 COLAB

1차 풀이

⭐ 1. 백준 10825 (국영수)

# 1. 알고(구현): 백준 10825 (국영수) - https://www.acmicpc.net/problem/10825
import sys
 
from io import StringIO
sys.stdin = StringIO('''12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taewhan 50 60 90''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    scores = []
 
    for _ in range(N):
        name, kor, eng, mat = input().split()
        scores.append((name, int(kor), int(eng), int(mat)))
 
    scores.sort(key=lambda x: (-x[1], x[2], -x[3], x[0]))
    print("\n".join(name for name, *_ in scores))
 
solve()

⭐ 2. 백준 11051 (이항 계수 2)

# 2. 알고(수학): 백준 11051 (이항 계수 2) - https://www.acmicpc.net/problem/11051
import sys
 
from io import StringIO
sys.stdin = StringIO('''5 2''')
 
input = sys.stdin.readline
 
def solve():
    N, K = map(int, input().split())
    MODE = 10_007  # comb(N, K)
 
    # (n, k) = (n-1, n-k) + (n-1, k)   n(row), k(col)
    dp = [[0] * (N + 1) for _ in range(N+1)]
    for i in range(0, N + 1):
        dp[i][0] = 1
        dp[i][i] = 1
 
    for n in range(2, N + 1):
        for k in range(0, n):
            dp[n][k] = (dp[n-1][n-k] + dp[n-1][k]) % MODE
 
    print(dp[N][K])
 
solve()

⭐ 3. 백준 20291 (파일 정리)

# 3. 알고(Map): 백준 20291 (파일 정리) - https://www.acmicpc.net/problem/20291
import sys
 
from io import StringIO
sys.stdin = StringIO('''8
sbrus.txt
spc.spc
acm.icpc
korea.icpc
sample.txt
hello.world
sogang.spc
example.txt''')
 
input = sys.stdin.readline
 
def solve():
 
    N = int(input())
 
    count = dict()
    for _ in range(N):
        _, tag = input().rstrip().split(".")
        count[tag] = count.get(tag, 0) + 1
 
    result = map(lambda x: f"{x[0]} {x[1]}", sorted(count.items()))
    print("\n".join(result))
 
solve()

⭐ 4. 백준 1141 (접두사)

# 4. 알고(그리디): 백준 1141 (접두사) - https://www.acmicpc.net/problem/1141
import sys
 
from io import StringIO
sys.stdin = StringIO('''6
hello
hi
h
run
rerun
running''')
 
input = sys.stdin.readline
 
def solve():
 
    N = int(input())
 
    words = list(set(input().rstrip() for _ in range(N)))
    words.sort(key=len)
 
    count = 0
    length = len(words)
 
    for i in range(length):
        is_prefix = False
        for j in range(i + 1, length):
            if words[j].startswith(words[i]):
                is_prefix = True
                break
        if not is_prefix:
            count += 1
 
    print(count)
 
solve()

✏️ 5. SQL 상위 n개 레코드

-- 5. SQL(Lv.1): 상위 n개 레코드 
-- https://school.programmers.co.kr/learn/courses/30/lessons/59405
SELECT 
    NAME 
FROM 
    ANIMAL_INS
ORDER BY
    DATETIME
LIMIT 1;

🚀 2차 코딩테스트 대비

  1. 백준 15685 (드래곤 커브)
  2. 백준 2225 (합분해)
  3. 백준 1717 (집합의 표현)
  4. 백준 15659 (연산자 끼워넣기 (3))
  5. SQL 서울에 위치한 식당 목록 출력하기

👨‍🏫 COLAB

2차 풀이

⭐ 1. 백준 15685 (드래곤 커브)

# 1. 알고(시뮬): 백준 15685 (드래곤 커브) - https://www.acmicpc.net/problem/15685
import sys
 
from io import StringIO
sys.stdin = StringIO('''3
3 3 0 1
4 2 1 3
4 2 2 1''')
 
input = sys.stdin.readline
 
def solve():
 
    N = int(input())
 
    dirs = [(+1, 0), (0, -1), (-1, 0), (0, +1)]
    dots = set()
 
    # 한 점을 기준으로 시계방향 으로 점을 회전
    for _ in range(N):
        x, y, d, gen = map(int, input().split())
        dx, dy = dirs[d]
 
        line = [(x, y), (x + dx, y + dy)]
 
        while gen > 0:
            ex, ey = line[-1]
            center_z = complex(ex, ey)
            new_line = []
 
            # 끝점과 가까운 점들부터 회전
            for i in range(len(line)-2, -1, -1):
                rx, ry = line[i]
                target_z = complex(rx, ry)
 
                z = (target_z - center_z) * 1j + center_z
                new_line.append((round(z.real), round(z.imag)))
 
            line.extend(new_line)
            gen -= 1
 
        dots.update(line)
 
    count = 0
    for x, y in dots:
        # 아래, 오른쪽, 대각선 점 존재 체크 (set이라 인덱스 걱정 없음)
        if (x, y + 1) in dots \
                and (x + 1, y) in dots \
                and (x + 1, y + 1) in dots:
            count += 1
 
    print(count)
 
solve()

⭐ 2. 백준 2225 (합분해)

# 2. 알고(DP): 백준 2225 (합분해) - https://www.acmicpc.net/problem/2225
import sys
# from math import comb
 
from io import StringIO
sys.stdin = StringIO('''20 2''')
 
input = sys.stdin.readline
 
def solve():
 
    N, K = map(int, input().split())
    MODE = 1_000_000_000
 
    # dp[k][n] = sigma (t=0, n) dp[k-1][t]  정수 k 개의 합으로 N을 만드는 경우의 수
    # dp[k][n] = dp[k][n-1] + dp[k-1][n] => 간단 버전.
    dp = [[0] * (N + 1) for _ in range(K + 1)]
 
    for n in range(N + 1):
        dp[1][n] = 1
 
    for k in range(2, K + 1):
        for n in range(1, N + 1):
            dp[k][0] = 1   # 0 만 사용해서 0 만들 수 있음
            dp[k][n] = (dp[k][n-1] + dp[k-1][n]) % MODE
 
    print(dp[K][N])
 
    # print(comb(K + (N - 1), N))   1 N개 사이 칸막이를 고르는 경우의 수
solve()

⭐ 3. 백준 1717 (집합의 표현)

# 3. 알고(그래프): 백준 1717 (집합의 표현) - https://www.acmicpc.net/problem/1717
import sys
 
from io import StringIO
sys.stdin = StringIO('''7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1''')
 
input = sys.stdin.readline
 
def solve():
    n, m = map(int, input().split())
 
    parent = list(range(n + 1))         # 루트는 자기 자신을 참조
    size = [1] * (n + 1)                # 루트 노드에 연결된 그래프 크기
 
    def find_root(x):
        while parent[x] != x:               # 내 노드가 루트가 아니면
            parent[x] = parent[parent[x]]   # 내 부모값을 할아버지 노드로 변경
            x = parent[x]                   # 다시 탐색
        return x    # 최상위 루트 반환
 
    def union(a, b):
        root_a = find_root(a)
        root_b = find_root(b)
 
        if root_a != root_b:
 
            # 작은 집합을 큰 집합에 붙임 (b 가 작게 만듬)
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a
 
            parent[root_b] = root_a         # a(큰쪽)이 root
            size[root_a] += size[root_b]    # 작은 쪽 싸이즈는 더이상 안쓰임
 
    # 실행
    result = []
    for _ in range(m):
        cmd, a, b = map(int, input().split())
        if cmd == 0:
            union(a, b)
        else:
            result.append("YES" if find_root(a) == find_root(b) else "NO")
 
    print("\n".join(result))
 
solve()

⭐ 4. 백준 15659 (연산자 끼워넣기 (3))

# 4. 알고(백트래킹): 백준 15659 (연산자 끼워넣기 (3)) - https://www.acmicpc.net/problem/15659
import sys
 
from io import StringIO
sys.stdin = StringIO('''6
1 2 3 4 5 6
2 1 1 1''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    nums = list(map(int, input().split()))
    plus, minus, mul, div = map(int, input().split())
 
    eq = [nums[0]]
 
    min_val = float('inf')
    max_val = -float('inf')
 
    def calculate(eq):
        stack = [eq[0]]
 
        # 연산자와 숫자가 번갈아 나오므로 2칸씩 건너뜁
        for i in range(1, len(eq), 2):
            op = eq[i]
            nxt_num = eq[i + 1]
 
            if op == '+':
                stack.append(nxt_num)
            elif op == '-':
                stack.append(-nxt_num)  # 음수로 넣기
            elif op == '*':
                # 곱셈은 스택 맨 위 숫자와 즉시 계산
                stack[-1] = stack[-1] * nxt_num
            elif op == '//':
                # 나눗셈은 파이썬 // 대신 int(a / b) 사용 (C++14 기준)
                stack[-1] = int(stack[-1] / nxt_num)
 
        # 스택에 남은 숫자들을 모두 더함
        return sum(stack)
 
    def dfs(depth, plus, minus, mul, div):
        nonlocal min_val, max_val
 
        if depth == N:
            cal_val = calculate(eq)   # eval(가능)
            min_val = min(min_val, cal_val)
            max_val = max(max_val, cal_val)
            return
 
        next_num = nums[depth]
 
        # 남은 연산자 개수가 0보다 클 때만 해당 분기로 진입
        if plus:
            eq.extend(["+", next_num])
            dfs(depth + 1, plus - 1, minus, mul, div)
            del eq[-2:]  # 백트래킹: 추가했던 연산자와 숫자를 다시 빼줌
 
        if minus:
            eq.extend(["-", next_num])
            dfs(depth + 1, plus, minus - 1, mul, div)
            del eq[-2:]
 
        if mul:
            eq.extend(["*", next_num])
            dfs(depth + 1, plus, minus, mul - 1, div)
            del eq[-2:]
 
        if div:
            eq.extend(["//", next_num])
            dfs(depth + 1, plus, minus, mul, div - 1)
            del eq[-2:]
 
    dfs(1, plus, minus, mul, div)
 
    print(max_val)
    print(min_val)
 
solve()

✏️ 5. SQL 서울에 위치한 식당 목록 출력하기

WITH SEOUL AS (
    SELECT 
        REST_ID,
        REST_NAME,
        FOOD_TYPE,
        FAVORITES,
        ADDRESS
    FROM 
        REST_INFO
    WHERE
        ADDRESS LIKE '서울%'
)
SELECT
    S.REST_ID,
    S.REST_NAME,
    S.FOOD_TYPE,
    S.FAVORITES,
    S.ADDRESS,
    ROUND(AVG(R.REVIEW_SCORE), 2) AS SCORE
FROM SEOUL S
JOIN
    REST_REVIEW R USING(REST_ID)
GROUP BY
    S.REST_ID
ORDER BY
    SCORE DESC,
    FAVORITES DESC;

그래프 뷰