SejongClass

28_회차_D-03

9 min read

✅ 28 회차 모의고사 D-03일

🚨 강의영상링크

🚀 1차 코딩테스트 대비

  1. 백준 4673 (셀프 넘버)
  2. 백준 11653 (소인수분해)
  3. 백준 18870 (좌표 압축)
  4. 백준 1946 (신입 사원)
  5. SQL FrontEnd 개발자 찾기

👨‍🏫 COLAB

1차 풀이

⭐ 1. 백준 4673 (셀프 넘버)

# 1. 알고(구현): 백준 4673 (셀프 넘버) - https://www.acmicpc.net/problem/4673
import sys
 
from io import StringIO
sys.stdin = StringIO('''''')
 
input = sys.stdin.readline
 
def solve():
 
    N = 10_000
    is_selfnum = [True] * (N + 1)
    is_selfnum[0] = False
 
    for i in range(1, N+1):
        sum_digits = 0
 
        q = i
        while q != 0:
            q, r = divmod(q, 10)
            sum_digits += r
        
        gen = i + sum_digits
        if gen <= N:
            is_selfnum[gen] = False
 
    print("\n".join(str(n) for n in range(1, N + 1) if is_selfnum[n]))
 
solve()

⭐ 2. 백준 11653 (소인수분해)

# 2. 알고(수학): 백준 11653 (소인수분해) - https://www.acmicpc.net/problem/11653
import sys
from math import isqrt
 
from io import StringIO
sys.stdin = StringIO('''72''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    factors = []
 
    quot = N    # 2 부터 우선 나눔
    while quot % 2 == 0:
        factors.append(2)
        quot //= 2
 
    nomer = 3  # 홀수로 검사
 
    while nomer <= isqrt(quot):
        while quot % nomer == 0:
            factors.append(nomer)
            quot //= nomer
        nomer += 2
 
    if quot > 1:
        factors.append(quot)
 
    print("\n".join(map(str, factors)))
 
solve()

⭐ 3. 백준 18870 (좌표 압축)

# 3. 알고(정렬): 백준 18870 (좌표 압축) - https://www.acmicpc.net/problem/18870
import sys
 
from io import StringIO
sys.stdin = StringIO('''5
2 4 -10 4 -9''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    nums = list(map(int, input().split()))
    uniq = sorted(set(nums))
 
    rank = {num: r for r, num in enumerate(uniq)}
    print(*[rank[n] for n in nums])
    
solve()

⭐ 4. 백준 1946 (신입 사원)

# 4. 알고(그리디): 백준 1946 (신입 사원) - https://www.acmicpc.net/problem/1946
import sys
 
from io import StringIO
sys.stdin = StringIO('''2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
    ranks = [0] * (N + 1)
 
    for _ in range(N):
        paper, inter = map(int, input().split())
        ranks[paper] = inter
 
    inter_rank = ranks[1]
    deadline = inter_rank   # 1등의 인터뷰 점수가 초기 합격 인터뷰 컷
    count = 1
 
    for i in range(2, N + 1):  # 서류 2등 부터 조사
        inter_rank = ranks[i]
        if inter_rank > deadline:     # 등수가 합격 컷 보다 크면
            continue
 
        deadline = inter_rank       # 대드라인 갱신
        count += 1
 
        if deadline == 1:   # 인터뷰 1등 나오면 종료.
            break
 
    print(count)
 
T = int(input())
for _ in range(T):
    solve()

✏️ 5. SQL FrontEnd 개발자 찾기

-- 5. SQL(Lv.4): FrontEnd 개발자 찾기 -- https://school.programmers.co.kr/learn/courses/30/lessons/276035
WITH 
    SC AS (
        SELECT CODE
        FROM SKILLCODES    
        WHERE CATEGORY = 'Front End'
    )
SELECT DISTINCT
    DV.ID,
    DV.EMAIL,
    DV.FIRST_NAME,
    DV.LAST_NAME
FROM SC
JOIN DEVELOPERS DV ON (SC.CODE & DV.SKILL_CODE) > 0
ORDER BY ID;

🚀 2차 코딩테스트 대비

  1. 백준 19237 (어른 상어)
  2. 백준 1005 (ACM Craft)
  3. 백준 9370 (미확인 도착지)
  4. 백준 2661 (좋은수열)
  5. SQL 멸종위기의 대장균 찾기

👨‍🏫 COLAB

2차 풀이

⭐ 1. 백준 19237 (어른 상어)

# 1. 알고(시뮬): 백준 19237 (어른 상어) - https://www.acmicpc.net/problem/19237
 
import sys
from collections import defaultdict
 
from io import StringIO
sys.stdin = StringIO('''4 2 6
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
4 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3''')
 
input = sys.stdin.readline
 
def solve():
    N, M, K = map(int, input().split())
 
    # 상어 정보
    sharks = defaultdict(list)
    for r in range(N):
        board_r = map(int, input().split())
        for c, shark_i in enumerate(board_r):
            if shark_i == 0:
                continue
            sharks[(r, c)].append([shark_i-1, 0])  # 0 인덱스
 
    # 초기 방향 냄새 세팅
    dirs = tuple(map(int, input().split()))
    smells_dict = defaultdict(list)
    for cur, shark_list in sharks.items():
        shark, d = shark_list[0]                # 1 마리 보장
        shark_list[0][1] = dirs[shark] - 1      # 방향값 0 idx 저장.
        smells_dict[cur].append((shark, 0))          # 냄새 저장 0초
 
    # 방향 우선순위 세팅
    dir_dict = {}
    directions = [(-1, 0), (+1, 0), (0, -1), (0, +1)]
    for d in range(M):
        dir_dict[d] = [
            tuple(map(lambda x: int(x) - 1, input().split()))
            for _ in range(4)
        ]
 
    time = 1
    while time <= 1000:
        nxt_sharks = defaultdict(list)
 
        # 각 상어별 조사.
        for (r, c), shark_list in sharks.items():
            for shark, d in shark_list:
                no_smell, my_smell = [], []   # 내 냄새 있는 칸 저장
 
                # 우선순위로 탐색
                for nd in dir_dict[shark][d]:
                    dr, dc = directions[nd]
                    nr, nc = nxt = r + dr, c + dc
                    in_range = 0 <= nr < N and 0 <= nc < N
                    if not in_range:
                        continue
 
                    smell_list = [  # K 초 전 smell 정보
                        s for s, t in smells_dict[nxt]
                        if 0 < time - t <= K
                    ]
 
                    if not smell_list:
                        no_smell.append((nxt, nd))
                        break
 
                    # 냄새 있고, 냄새 있다면
                    elif shark in smell_list and not my_smell:
                        my_smell.append((nxt, nd))
 
                nxt, nd = no_smell[0] if no_smell else my_smell[0]
                nxt_sharks[nxt].append((shark, nd))
                smells_dict[nxt].append((shark, time))
 
        # 겹치는 상어 통일
        count = 0
        for cur, shark_list in nxt_sharks.items():
            if not shark_list:
                continue
 
            if len(shark_list) > 1:
                remain = min(shark_list, key=lambda x: x[0])
                shark_list.clear()
                shark_list.append(remain)
 
            count += 1
 
        if count == 1:
            return print(time)
 
        sharks = nxt_sharks
        time += 1
 
    print(-1)
 
solve()

⭐ 2. 백준 1005 (ACM Craft)

# 2. 알고(DP): 백준 1005 (ACM Craft) - https://www.acmicpc.net/problem/1005
import sys
from collections import deque
 
from io import StringIO
sys.stdin = StringIO('''2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
8''')
 
input = sys.stdin.readline
 
def solve():
    N, K = map(int, input().split())
    times = list(map(int, input().split()))
 
    graph = [[] for _ in range(N + 1)]   # 순방향
    indegree = [0] * (N + 1)
 
    for _ in range(K):
        u, v = map(int, input().split())
        graph[u].append(v)
        indegree[v] += 1
 
    W = int(input())
 
    # 위상정렬 + DP
    dp = [0] + list(times)  # 1-indexed
 
    queue = deque(i for i in range(1, N + 1) if indegree[i] == 0)
 
    while queue:
        cur = queue.popleft()
        for nxt in graph[cur]:
            dp[nxt] = max(dp[nxt], dp[cur] + times[nxt - 1])
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
 
    print(dp[W])
 
T = int(input())
for _ in range(T):
    solve()

⭐ 3. 백준 9370 (미확인 도착지)

# 3. 알고(그래프): 백준 9370 (미확인 도착지) - https://www.acmicpc.net/problem/9370
import sys
from heapq import heappush, heappop
 
from io import StringIO
sys.stdin = StringIO('''2
5 4 2
1 2 3
1 2 6
2 3 2
3 4 4
3 5 3
5
4
6 9 2
2 3 1
1 2 1
1 3 3
2 4 4
2 5 5
3 4 3
3 6 2
4 5 4
4 6 3
5 6 7
5
6''')
 
input = sys.stdin.readline
 
def solve():
    n, m, t = map(int, input().split())
    start, g, h = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
 
    for _ in range(m):
        a, b, w = map(int, input().split())
        double = w * 2
 
        if (a, b) == (g, h) or (a, b) == (h, g):
            double -= 1
 
        graph[a].append((b, double))
        graph[b].append((a, double))
 
    candidates = [int(input()) for _ in range(t)]
 
    INF = float('inf')
 
    # 다익스트라
    min_dist = [INF] * (n + 1)
    min_dist[start] = 0
    pq = [(0, start)]
 
    while pq:
        cur_dist, cur = heappop(pq)
 
        if cur_dist > min_dist[cur]:
            continue
 
        for nxt, cost in graph[cur]:
            nxt_dist = cur_dist + cost
            if nxt_dist >= min_dist[nxt]:
                continue
 
            min_dist[nxt] = nxt_dist
            heappush(pq, (nxt_dist, nxt))
 
    answer = []
    for candi in candidates:
        if min_dist[candi] != INF and min_dist[candi] % 2 == 1:
            answer.append(candi)
 
    answer.sort()
    print(*answer)
 
T = int(input())
for _ in range(T):
    solve()

⭐ 4. 백준 2661 (좋은수열)

# 4. 알고(백트래킹): 백준 2661 (좋은수열) - https://www.acmicpc.net/problem/2661
import sys
 
from io import StringIO
sys.stdin = StringIO('''7''')
 
input = sys.stdin.readline
 
def solve():
    N = int(input())
 
    def dfs(num):
 
        if len(num) == N:
            print(num)
            return True 
 
        for digit in ['1', '2' ,'3']:
            nxt = num + digit   # 문자열 병합
 
            for leng in range(1, len(nxt) // 2 + 1):
                if nxt[-leng:] == nxt[-2*leng:-leng]:
                    break       # 나쁜 수열
            else:
                if dfs(nxt):
                    return True # 종료 전파
    dfs("")    
 
solve()

✏️ 5. SQL 멸종위기의 대장균 찾기

-- 5. SQL(Lv.5): 멸종위기의 대장균 찾기 
-- https://school.programmers.co.kr/learn/courses/30/lessons/301651
WITH RECURSIVE
    GEN AS (
        SELECT
            ID, 
            PARENT_ID, 
            1 AS GENER
        FROM ECOLI_DATA
        WHERE PARENT_ID IS NULL
        
        UNION ALL
        
        SELECT
            E.ID,
            E.PARENT_ID,
            GEN.GENER + 1 AS GENER
        FROM GEN
        JOIN ECOLI_DATA E ON GEN.ID = E.PARENT_ID
    )
    
SELECT
    COUNT(*) AS COUNT,
    GENER AS GENERATION
FROM GEN
WHERE NOT EXISTS (
    SELECT 1
    FROM ECOLI_DATA ED
    WHERE GEN.ID = ED.PARENT_ID
)
GROUP BY GENERATION
ORDER BY GENERATION ASC;

그래프 뷰