SejongClass

09_회차_D-22

9 min read

✅ 09 회차 모의고사 D-22일

🚨 강의영상링크

🚀 1차 코딩테스트 대비

  1. 백준 17413 (단어 뒤집기 2)
  2. 백준 1024 (수열의 합)
  3. 백준 1269 (대칭 차집합)
  4. 백준 2847 (게임을 만든 동준이)
  5. SQL 입양 시각 구하기(1)

👨‍🏫 COLAB

1차 풀이

⭐ 1. 백준 17413 (단어 뒤집기 2)

# 1. 알고(구현): 백준 17413 (단어 뒤집기 2) - https://www.acmicpc.net/problem/17413
import sys
 
from io import StringIO
sys.stdin = StringIO('''<problem>17413<is hardest>problem ever<end>''')
 
input = sys.stdin.readline
 
def solve():
    s = input().rstrip()
 
    final_result = []
    word = []
    in_tag = False
 
    for c in s:
 
        if c == '<':
            if word:
                final_result.append("".join(reversed(word)))
                word.clear()
 
            in_tag = True
            final_result.append(c)
 
        elif c == '>':
            final_result.append(c)
            in_tag = False
 
        elif in_tag:
            final_result.append(c)
 
        else:
            # 태그 안쪽이 아닐 때
            if c == ' ':
                if word:
                    final_result.append("".join(reversed(word)))
                    word.clear()
                final_result.append(' ')
            else:
                word.append(c)
 
    if word:
        final_result.append("".join(reversed(word)))
 
    print(''.join(final_result))
 
solve()

⭐ 2. 백준 1024 (수열의 합)

# 2. 알고(수학): 백준 1024 (수열의 합) - https://www.acmicpc.net/problem/1024
import sys
 
from io import StringIO
sys.stdin = StringIO('''18 4''')
 
input = sys.stdin.readline
 
def solve():
    N, L = map(int, input().split())
 
    #  sigma (a + n-1) 시작 a(start) 부터 길이 n(lenth) 의 합
    #  (n**2 + (2*a - 1) * n ) // 2
 
    ans_start = -1
    ans_len = 0
 
    for l in range(L, 101):
        numer = 2*N - l**2 + l
        denom = 2*l
 
        if numer % denom == 0:
            start = numer // denom
            if start >= 0:
                ans_start = start
                ans_len = l
                break
 
    if ans_start == -1:
        print(ans_start)
    else:
        print(*range(ans_start, ans_start + ans_len))
 
solve()

⭐ 3. 백준 1269 (대칭 차집합)

# 3. 3. 알고(Set): 백준 1269 (대칭 차집합) - https://www.acmicpc.net/problem/1269
import sys
 
from io import StringIO
sys.stdin = StringIO('''3 5
1 2 4
2 3 4 5 6''')
 
input = sys.stdin.readline
 
def solve():
 
    input()
    set1 = set(map(int, input().split()))
    set2 = set(map(int, input().split()))
    print(len(set1.symmetric_difference(set2)))
    # = set1 ^ set2
 
solve()

⭐ 4. 백준 2847 (게임을 만든 동준이)

# 4. 알고(그리디): 백준 2847 (게임을 만든 동준이) - https://www.acmicpc.net/problem/2847
import sys
 
from io import StringIO
sys.stdin = StringIO('''4
5
3
7
5''')
 
input = sys.stdin.readline
 
def solve():
 
    N = int(input())
    scores = [int(input()) for _ in range(N)]
 
    cutting = 0
    base = scores[-1]
 
    for i in range(N-2, -1, -1):
        target = scores[i]
        max_level = base - 1
        if target > max_level:
            cutting += target - max_level
        base = min(target, max_level)
 
    print(cutting)
 
solve()

✏️ 5. SQL 입양 시각 구하기(1)

-- 5. SQL(Lv.2): 입양 시각 구하기(1) 
-- https://school.programmers.co.kr/learn/courses/30/lessons/59412
SELECT 
    HOUR(DATETIME) AS HOUR,
    COUNT(*) AS COUNT
FROM 
    ANIMAL_OUTS
WHERE
    HOUR(DATETIME) BETWEEN 9 AND 19
GROUP BY
    HOUR
ORDER BY
    HOUR;

🚀 2차 코딩테스트 대비

  1. 백준 17143 (낚시왕)
  2. 백준 9251 (LCS)
  3. 백준 1504 (특정한 최단 경로)
  4. 백준 15686 (치킨 배달)
  5. SQL 특정 기간동안 대여 가능한 자동차들의 대여료 구하기

👨‍🏫 COLAB

2차 풀이

⭐ 1. 백준 17143 (낚시왕)

# 1. 알고(시뮬): 백준 17143 (낚시왕) - https://www.acmicpc.net/problem/17143
import sys
from itertools import product
 
from io import StringIO
sys.stdin = StringIO('''4 6 8
4 1 3 3 8
1 3 5 2 9
2 4 8 4 1
4 5 0 1 4
3 3 1 2 7
1 5 8 4 3
3 6 2 1 2
2 2 2 3 5''')
 
input = sys.stdin.readline
 
# 위치, 방향, 속도, 거리, 양의방향, 음의 방향 -> 위치, 방향 리턴.
def get_next_pos(p, d, s, L, pos_dir, neg_dir):
    # d: 1 위, 2 아래, 3, 오른, 4 왼
 
    if L == 1:
        return p, d
 
    cycle = 2 * (L - 1)
    s %= cycle
    x = p - 1
 
    if d == neg_dir:
        x = (cycle - x) % cycle
    x = (x + s) % cycle
 
    if x < L:
        new_p = x + 1
    else:
        new_p = (cycle - x) + 1
 
    new_d = pos_dir if x < (L-1) else neg_dir
    return new_p, new_d
 
def solve():
    R, C, M = map(int, input().split())
 
    sharks = dict()
    for _ in range(M):
        r, c, s, d, z = map(int, input().split())
        sharks[(r, c)] = (s, d, z)
 
    total = 0
    for col in range(1, C+1):
 
        for row in range(1, R+1):  # 낚시
            if (row, col) in sharks:
                total += sharks[(row, col)][2]
                del sharks[(row, col)]
                break
 
        new_sharks = dict()         # 물고기 이동
        for (r, c), (s, d, z) in sharks.items():
 
            if d in (1, 2):  # 세로  아래(2)가 양의 방향
                nr, nd = get_next_pos(r, d, s, R, 2, 1)
                nc = c
 
            else:           # 가로 오른(3)가 양의 방향
                nc, nd = get_next_pos(c, d, s, C, 3, 4)
                nr = r
 
            # 잡아먹기
            if (nr, nc) not in new_sharks or new_sharks[(nr, nc)][2] < z:
                new_sharks[(nr, nc)] = (s, nd, z) # 덮어 씀
        
        sharks = new_sharks
 
    print(total)
 
solve()

⭐ 2. 백준 9251 (LCS)

# 2. 알고(DP): 백준 9251 (LCS) - https://www.acmicpc.net/problem/9251
import sys
 
from io import StringIO
sys.stdin = StringIO('''ACAYKP
CAPCAK''')
 
input = sys.stdin.readline
 
def solve():
 
    A = input().rstrip()
    B = input().rstrip()
 
    n, m = len(A), len(B)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    # dp[i][j] A의 앞에서부터 i번째 글짜와, B의 앞에서부터 j번째 글짜까지의 최장 공통 부분 수열의 값을 저장.
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
    print(dp[n][m])
 
solve()

⭐ 3. 백준 1504 (특정한 최단 경로)

# 3. 알고(그래프): 백준 1504 (특정한 최단 경로) - https://www.acmicpc.net/problem/1504
import sys
from heapq import heappop, heappush
 
from io import StringIO
sys.stdin = StringIO('''4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3''')
 
input = sys.stdin.readline
 
def solve():
 
    N, E = map(int, input().split())
 
    graph = [[] for _ in range(N + 1)]
    for _ in range(E):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
 
    def dijkstra(start):
 
        dist = [float('inf')] * (N + 1)
        dist[start] = 0
        pq = [(0, start)]
 
        while pq:
            cur_dist, cur = heappop(pq)
            if cur_dist > dist[cur]:
                continue
            for nxt, cost in graph[cur]:
                new_dist = cur_dist + cost
                if new_dist < dist[nxt]:
                    dist[nxt] = new_dist
                    heappush(pq, (new_dist, nxt))
 
        return dist
 
    v1, v2 = map(int, input().split())
 
    start = dijkstra(1)
    # 1 -> v1, 1-> v2
 
    # v1 -> v2, v1-> N
    first = dijkstra(v1)
 
    # v2 -> v1, V2 -> N
    second = dijkstra(v2)
 
    # 1-> v1 -> v2 -> N
    # 1-> v2 -> v1 -> N
    path1 = start[v1] + first[v2] + second[N]
    path2 = start[v2] + second[v1] + first[N]
 
    ans = min(path1, path2)
    print(ans if ans < float('inf') else -1)
 
solve()

⭐ 4. 백준 15686 (치킨 배달)

# 4. 알고(백트래킹): 백준 15686 (치킨 배달) - https://www.acmicpc.net/problem/15686
import sys
from itertools import product, combinations
 
from io import StringIO
sys.stdin = StringIO('''5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2''')
 
input = sys.stdin.readline
 
def solve():
 
    N, M = map(int, input().split())
    board = [tuple(map(int, input().split())) for _ in range(N)]
 
    houses = list()
    chickens = list()
 
    for r, c in product(range(N), repeat=2):
        val = board[r][c]
        if val == 1:
            houses.append((r, c))
        elif val == 2:
            chickens.append((r, c))
 
    min_city_dist = float('inf')
    for picked_chickens in combinations(chickens, M):
 
        city_dist_sum = 0
        for hr, hc in houses:               # 한 집을 골라서
            min_val = float('inf')          # 한집의 치킨거리
            for pr, pc in picked_chickens:  # 각 치킨 거리 계산
 
                dist = abs(hr-pr) + abs(hc-pc)
                min_val = min(min_val, dist)
 
            city_dist_sum += min_val
 
            if city_dist_sum > min_city_dist:   # 도시 치킨 거리 값이 최소값보다 커지면 조사 중지
                break
 
        min_city_dist = min(min_city_dist, city_dist_sum)
 
    print(min_city_dist)
 
solve()

✏️ 5. SQL 특정 기간동안 대여 가능한 자동차들의 대여료 구하기

-- 5. SQL(Lv.4): 특정 기간동안 대여 가능한 자동차들의 대여료 구하기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/157339
WITH PBL AS (
    SELECT
        C.CAR_ID,
        C.CAR_TYPE,
        C.DAILY_FEE
    FROM CAR_RENTAL_COMPANY_CAR C
    WHERE C.CAR_TYPE IN ('세단', 'SUV')
      AND NOT EXISTS (
          SELECT 1
          FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY H
          WHERE H.CAR_ID = C.CAR_ID
            AND H.START_DATE <= '2022-11-30'
            AND H.END_DATE   >= '2022-11-01'
      )
),
DT AS (
    SELECT
        CAR_TYPE,
        DISCOUNT_RATE
    FROM CAR_RENTAL_COMPANY_DISCOUNT_PLAN
    WHERE DURATION_TYPE = '30일 이상'
),
F AS (
    SELECT
        PBL.CAR_ID,
        PBL.CAR_TYPE,
        ROUND(PBL.DAILY_FEE * 30 * (100 - DT.DISCOUNT_RATE) / 100) AS FEE
    FROM PBL
    JOIN DT USING (CAR_TYPE)
)
SELECT
    CAR_ID,
    CAR_TYPE,
    FEE
FROM F
WHERE FEE >= 500000
  AND FEE < 2000000
ORDER BY
    FEE DESC,
    CAR_TYPE ASC,
    CAR_ID DESC;

그래프 뷰