그냥 코딩하는 사람의 블로그

문제 설명

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

• 첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

• 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

풀이 과정

• 어떻게 구현하는지 모르겠어서.. next_permutation 알고리즘을 찾아 봄

1. 현재 순열을 오른쪽 -> 왼쪽으로 검사하면서 a[i] > a[i-1]인 i점을 찾음.
   • 여기서, i-1번이 바꾸게 될 타겟임.
   • 만약 맨 왼쪽까지 그런 점이 없다면 마지막 순열인 것
2. 다시 현재 순열을 오른쪽 -> 왼쪽으로 검사하면서, 바꾸게 될 타겟보다 큰 값의 위치를 찾음.
   • a[j] > a[i-1]인 점 j를 찾음.
3. a[j]와 a[i-1]을 바꾸어 준다.
4. 마지막으로, i번째 이후의 순열들을 오름차순으로 정렬해주면 된다. (i번째 순열 포함)
   • 이 때, 사실상 i번째 이후의 순열들은 내림차순이므로 거꾸로 붙여주면 됨.
   • 스왑으로 구현하여도 됨. (i <-> 맨 오른쪽), (i-1 <-> 맨 오른쪽-1), ...

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())

sequence = list(map(int, sys.stdin.readline().rstrip().split()))

def next_permutation(sequence):
    i = len(sequence) - 1
    # sequence[i-1] < sequence[i]인 경우, sequence[i-1]이 바꾸게 될 타겟
    while i > 0 and sequence[i-1] > sequence[i]:
        i = i - 1

    if i == 0:
        return None

    swap_pos = i-1
    # 바꾸게 될 타겟보다 큰 값의 위치를 찾음
    j = len(sequence) - 1
    while j > 0 and sequence[swap_pos] >= sequence[j]:
        j = j - 1

    # 두 값을 서로 바꾸어 줌
    sequence[swap_pos], sequence[j] = sequence[j], sequence[swap_pos]

    k = len(sequence) - 1
    sequence = sequence[:i] + (sequence[i:])[::-1]        
    return sequence


p = next_permutation(sequence)
if p == None:
    print(-1)
else:
    print(*p)

현재 시간

let today = new Date()

년 / 월 / 일 따로 가져오기

let today = new Date()

let year = today.getFullYear();
let month = today.getMonth();
// 0 붙여서 => let month = ('0' + (today.getMonth() + 1)).slice(-2);
let day = today.getDate();
// 0 붙여서 => let day = ('0' + (today.getDate())).slice(-2);

let dateString = year + '-' + month + '-' + day;

console.log(dateString)

• 한자리수의 경우 앞에 0 넣어주어서 포매팅
• getMonth의 경우는 0부터 시작함에 유의 !!

Array.prototype.slice

• (begin, end) : 시작점 ~ 끝점까지 추출한 배열 리턴
• (begin) : 시작점 ~ 끝까지 추출한 배열 리턴
• begin이나 end에는 음수 인덱스가 올 수 있음(파이썬과 같음)
• end는 포함되지 않음

문제 설명

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

풀이 과정

1. Stack의 push / pop을 활용하여 문제 해결
   • 스택의 맨 위 요소와 현재 문자가 같은 경우 pop만 해줌.
     • (겹치지 않게 아치형 곡선을 그은 케이스)
   • 스택의 맨 위 요소와 현재 문자가 다른 경우 push
2. 1번 과정을 전체 문자에 대해서 진행하였을 때,
   • 스택이 빈 경우 -> 좋은 단어
   • 스택이 비지 않은 경우 -> 선들이 교차하는 경우로 볼 수 있음.
3. 좋은 단어의 개수 출력

소스 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())
strlist = [input().rstrip() for _ in range(n)]

answer = 0
for s in strlist:
    stack = []
    for c in s:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)

    if not stack:
        answer += 1

print(answer)

문제 설명

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.

풀이 과정

1. 전체적인 방식은 DFS로 진행
   • 현재 좌표에서 페스티벌까지 이동 가능한지 체크
   • 이동 가능하지 않다면 현재 좌표에서 이동 가능한 편의점으로 이동하도록 DFS 구성
2. DFS로 소스를 구성할 때 고려해야 할 점이 있음.
   • DFS 진행 이전에 현재 좌표를 visited를 저장하는건 맞지만, 이후에 visited에서 빼야 하는가에 대한 고민 필요.
   • 뺏을때는 시간 초과가 나오나, 빼지 않을 때는 시간 초과가 나오지 않음.
   • DFS 인자로 visited를 넘겨주니 굳이 빼지 않아도 될거 같음.
     • 1 -> 2 순으로 DFS 진행할 때, 애초에 2로 왔다는거 자체가 1로 이동하는 순간 페스티벌로 이동할수 없다는 거니까.

소스 코드

import sys

input = sys.stdin.readline

t = int(input().rstrip())

succeed = False

def get_manhattan_distance(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def dfs(visited, stations, current, festival):
    global succeed

    if get_manhattan_distance(current, festival) <= 1000:
        succeed = True
        return

    for i in range(len(stations)):
        if tuple(stations[i]) not in visited and (
            get_manhattan_distance(current, stations[i]) <= 1000
        ):
            visited.add(tuple(stations[i]))
            dfs(visited, stations, stations[i], festival)
            if succeed:
                return

for _ in range(t):
    n = int(input().rstrip())
    start = list(map(int, input().rstrip().split()))
    stations = []
    for __ in range(n):
        stations.append(list(map(int, input().rstrip().split())))
    festival = list(map(int, input().rstrip().split()))
    succeed = False
    dfs(set(), stations, start, festival)
    if succeed:
        print('happy')
    else:
        print('sad')

문제 설명

문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

풀이 과정

1. 빙산을 녹이는 과정 시뮬레이션
   • 기존 이차원 배열을 하나 복제해준다.
   • 이차원 배열의 각각의 요소들을 검사하면서, 요소가 0이 아니라면 상하좌우에 0의 개수만큼 빼준다. (음수가 되는 경우 0으로 맞춰줌)
   • 이 과정에서 0이 되는 것이 다른 요소에 영향을 주면 안되므로 복제된 배열에 값을 저장하고, 비교할때는 기존 배열을 사용한다.
2. BFS를 통해 빙산이 몇덩어리인지 확인한다.
   • 각각의 요소들을 검사하면서, 요소가 0이 아니라면 해당 [행][열]에서 시작해서 BFS를 진행하면서 모두 0으로 맞춰줌.
   • 이 때, 덩어리의 수를 한개 증가시킨다.
3. 덩어리의 수에 따라 출력해주면 된다. (0개일때, 2개 이상일때)

소스 코드

import sys
import copy
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]


def minus(temp, matrix, x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < len(matrix) and 0 <= ny and ny < len(matrix[0]):
            if matrix[nx][ny] == 0:
                temp[x][y] -= 1

    if temp[x][y] < 0:
        temp[x][y] = 0

def bfs(matrix, x, y):
    queue = deque([[x, y]])
    matrix[x][y] = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < len(matrix) and 0 <= ny and ny < len(matrix[0]):
                if matrix[nx][ny] != 0:
                    matrix[nx][ny] = 0
                    queue.append([nx, ny])
year = 1
while True:
    # 빙산 녹는 과정 시뮬레이션
    temp = copy.deepcopy(matrix)
    for i in range(N):
        for j in range(M):
            if matrix[i][j] != 0:
                minus(temp, matrix, i, j)

    # matrix에 녹은 빙산 저장 
    matrix = copy.deepcopy(temp)

    # 녹은 빙산이 몇덩이인지 bfs로 검사
    total = 0
    for i in range(N):
        for j in range(M):
            if temp[i][j] != 0:
                total += 1
                bfs(temp, i, j)

    # 덩어리의 수에 따라 출력
    if total >= 2:
        print(year)
        break
    elif total == 0:
        print(0)
        break

    year += 1

문제 설명

Given two sorted arraysnums1andnums2of sizemandnrespectively, returnthe medianof the two sorted arrays.

The overall run time complexity should beO(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106<= nums1[i], nums2[i] <= 106

풀이 과정

• 두개 합쳐서 정렬해서 풀 수도 있지만 오래 걸림.

1. 따라서, 우선 두개의 리스트를 queue로 바꾼다.
2. 전체 개수가 홀수일때, 짝수일때 중간값의 위치가 다르다.
   • 홀수일 때 : (두개의 리스트의 길이의 합 // 2)
   • 짝수일 때 : (두개의 리스트의 길이의 합 // 2) - 1, (두개의 리스트의 길이의 합 // 2)
     • 두개를 뽑고 2로 나누어준 값이 중간값
3. 따라서 홀수일 때는 (두개의 리스트의 길이의 합 // 2) - 1개만큼 뽑아주고, 짝수일 때는 (두개의 리스트의 길이의 합 // 2) - 2개만큼 뽑아준다.
   • 이 다음에 홀수일때는 한개 뽑고, 짝수일때는 두개 뽑아서 중간값 구해주면 됨.
4. 뽑아줄 때는 두개의 큐의 가장 왼쪽에서 값을 비교하며 하나씩 뽑아준다.
   • 한쪽이 큰 경우 다른쪽에서 뽑아줌.
   • 이 때, 한쪽 큐가 비는 경우 다른쪽 큐에서만 뽑아주면 된다.

소스 코드

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        from collections import deque

        q1 = deque(nums1)
        q2 = deque(nums2)

        total_length = len(nums1) + len(nums2)
        even = False

        def next_pop(q1, q2):
            temp = 0
            if q1 and q2:
                if q1[0] > q2[0]:
                    temp = q2.popleft()
                else:
                    temp = q1.popleft()
            elif q1:
                temp = q1.popleft()
            elif q2:
                temp = q2.popleft()
            return temp


        if total_length % 2 == 0:
            even = True
            median_idx = total_length // 2 
        else:
            median_idx = total_length // 2 + 1

        for i in range(median_idx-1):
            next_pop(q1, q2)

        answer = 0
        if even:
            answer = next_pop(q1, q2) + next_pop(q1, q2)
            answer = answer / 2
        else:
            answer = next_pop(q1, q2)

        answer = answer * 1.0

        return answer

문제 설명

You are given twonon-emptylinked lists representing two non-negative integers. The digits are stored inreverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range[1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

풀이 과정

1. 먼저 입력받은 두개의 Linked-List를 따라 이동하면서 더해야 하는 수 a,b를 구한다.
   • idx를 10씩 곱해주면서 val * idx를 더해주면 된다.
2. a, b를 구해주었다면, 합계를 구한 다음 문자열로 바꾸고 뒤집는다.
3. 뒤집은 수 숫자 한자리씩 Linked-List를 구성하여 주면 된다.
   • 한자리씩 노드를 만들어서, 맨 마지막 노드에 붙여주면 된다.
   • 헤드 노드를 따로 만들어주어야 함 => 리턴할 때 사용
4. Linked-List의 헤드 노드를 리턴해주면 된다.

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a = 0
        idx = 1
        temp = l1
        while temp:
            a += temp.val * idx
            idx *= 10
            temp = temp.next

        b = 0
        idx = 1
        temp = l2
        while temp:
            b += temp.val * idx
            idx *= 10
            temp = temp.next

        print(a, b)
        c = str(a + b)[::-1]

        head = None
        last = None
        for i in c:
            node = ListNode(val=int(i))
            if head is None:
                head = node

            if last is not None:
                last.next = node
                last = node
            else:
                last = node

        return head

문제 설명

문제

평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.

'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.

이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나씩 놓여있는 채로 시작한다. 어떤 사람의 차례가 오면, 그 사람은 현재 존재하는 게임말 중 아무거나 하나를 골라 그 말이 놓여있던 노드의 부모 노드로 옮긴다. 이 과정에서 한 노드에 여러 개의 게임말이 놓이게 될 수도 있다. 이렇게 옮긴 후에 만약 그 게임말이 루트 노드에 도착했다면 그 게임말을 즉시 제거한다. 모든 과정을 마치면 다음 사람에게 차례를 넘긴다. 이런 식으로 계속 진행하다가 게임말이 게임판에 존재하지 않아 고를 수 없는 사람이 지게 된다.

성원이를 얕본 형석이는 쿨하게 이 게임의 선을 성원이에게 줘버렸다. 따라서 성원이가 먼저 시작하고 형석이가 나중에 시작한다. 그동안 형석이와 대결을 하면 매번 지기만 했던 성원이는 마음속에 분노가 가득 쌓였다. 이번 대결에서는 반드시 이겨서 형석이의 코를 꺾어주고 싶다. 그래서 게임을 시작하기 전에 게임판의 모양만 보고 이 게임을 이길 수 있을지 미리 알아보고 싶어졌다. 성원이가 이 게임을 이길 수 있을지 없을지를 알려주는 프로그램을 만들어 성원이를 도와주자.

입력

첫째 줄에 트리의 정점 개수 N(2 ≤ N ≤ 500,000)이 주어진다.

둘째 줄부터 N-1줄에 걸쳐 트리의 간선 정보가 주어진다. 줄마다 두개의 자연수 a, b(1 ≤ a, b ≤ N, a ≠ b)가 주어지는데, 이는 a와 b 사이에 간선이 존재한다는 뜻이다.

출력

성원이가 최선을 다했을 때 이 게임을 이길 수 있으면 Yes, 아니면 No를 출력한다.

풀이 과정

0. 루트 노드들의 깊이 합계를 구함.
   • 마지막에 아무것도 없을때 선택하는 사람이 패배이고, 성원이가 먼저 시작하므로
   • 합계를 2로 나누었을때 나누어 떨어지면 패배,
   • 나누어 떨어지지 않으면 승리
1. 1번 노드에서부터 bfs 진행
   • queue에는 [다음 노드, 단계] 형식으로 저장
   • 루트 노드인 경우, 해당 노드의 단계를 합계에 더해줌.
2. 루트 노드의 깊이 합계를 2로 나누었을때 나누어 떨어지면 패배, 나누어 떨어지지 않으면 승리를 출력한다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input().rstrip())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().rstrip().split())
    tree[a].append(b)
    tree[b].append(a)

leap_depth = []
queue = deque([[1,0]])
visited = [False] * (N+1)
visited[1] = True
total_leaf_depth = 0
while queue:
    node, depth = queue.popleft()
    if len(tree[node]) == 1 and visited[tree[node][0]]:
        total_leaf_depth += depth
        continue

    for t in tree[node]:
        if not visited[t]:
            queue.append([t, depth+1])
            visited[t] = True


if total_leaf_depth % 2 == 1:
    print('Yes')
else:
    print('No')

문제 설명

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

풀이 과정

1. 입력받은 간선들을 순차적으로 방문하면서 각각의 간선들의 두 정점을 Union 해준다.
   • 이 때, 두 정점이 같은 그룹에 있는 경우 싸이클이 형성됨 => 트리가 아니란 걸 알 수 있음.
   • 맨 마지막에 처리하기 위해 두 정점중 하나의 정점을 따로 저장
2. (1)번에서 따로 저장해둔 정점이 어떤 그룹에 속해있는지 저장
   • 해당 그룹은 사이클이 형성된 그룹이므로 방문하지 않아야 함.
3. 전체 정점에 대해서, 방문하지 않은 그룹이면서 사이클이 형성되지 않은 그룹이라면
   • 해당 그룹 방문처리 / 정답 개수 하나 증가
4. 그룹 개수에 따라 다르게 print

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        if p1 > p2:
            parent[p1] = p2
        else:
            parent[p2] = p1

case = 0
while True:
    n, m = map(int, input().rstrip().split())
    if n == 0 and m == 0:
        break
    parent = [i for i in range(n+1)]
    cycle = []
    for _ in range(m):
        a, b = map(int, input().rstrip().split())
        p1 = find(parent, a)
        p2 = find(parent, b)
        if p1 != p2:
            union(parent, a, b)
        else:
            # cycle이 발생한 케이스이므로 따로 저장
            cycle.append(a)
    # 갱신
    for i in range(n+1):
        find(parent, i)

    # cycle이 있는 그룹들 저장
    group = set()
    for cycle_vertex in cycle:
        group.add(parent[cycle_vertex])

    answer = 0
    for i in range(1, n+1):
        if parent[i] in group:
            continue
        answer += 1
        group.add(parent[i])

    case += 1
    if answer == 0:
        print("Case %d: No trees."%(case))
    elif answer == 1:
        print("Case %d: There is one tree."%(case))
    else:
        print("Case %d: A forest of %d trees."%(case, answer))

문제 설명

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai(1 ≤ Ai≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

출력

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

풀이 과정

1. 전체 시험장에 먼저 총감독관을 배치한다.
   • 각 시험장의 응시자의 수에서 총감독관이 감시할 수 있는 응시자의 수를 빼준다.
   • 빼주면서, 감독관의 수를 하나 증가시킨다.
2. 다음으로, 각 시험장에 부감독관을 배치한다.
   • 시험장에 필요한 부감독관의 수는 다음과 같다.
     • round(각 시험장의 잔여 인원 수 / 부감독관이 감시할 수 있는 인원 수)
   • 나머지가 있으면 1 증가하는 방식으로 구현함.
   • 감독관의 수를 필요한 부감독관의 수만큼 늘려준다.
3. 전체 감독관의 수를 출력해주면 된다.

풀이 과정

import sys

input = sys.stdin.readline
N = int(input().rstrip())
exam = list(map(int, input().rstrip().split()))
B, C = map(int, input().rstrip().split())

answer = 0

for i in range(len(exam)):
    exam[i] -= B
    answer += 1

for i in range(len(exam)):
    if exam[i] <= 0:
        continue
    answer += (exam[i] // C)
    if exam[i] % C != 0:
        answer += 1

print(answer)