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

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서가능한 한 최대의총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한정수상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

풀이 과정

1. 범위를 0 ~ 예산요청의 최댓값으로 잡고 이분 탐색 진행
   • 중간값을 기준으로 예산 배정이 성공적으로 이루어지면 최댓값을 구해야 하므로 예산을 더 늘려보아야 한다. 따라서 저장 후 오른쪽 구간 (중간값+1 ~ )
   • 중간값을 기준으로 예산 배정이 성공적으로 이루어지지 않았다면 예산을 줄여야 하므로 왼쪽 구간 ( ~ 중간값-1)
2. 예산 배정 과정
   • 배정된 예산 > 예산요청 => 예산 요청
   • 배정된 예산 < 예산요청 => 배정된 예산
   • if문 작성에 유의

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
lists = list(map(int, input().rstrip().split()))
M = int(input().rstrip())

left = 0
right = max(lists)
answer = 0
while left <= right:
    mid = (left + right) // 2
    total = M
    succeed = True
    for k in lists:
        if (total < mid and k >= mid) or (
            total < k and k < mid ):
            succeed = False
        if succeed:
            if k < mid: # 현재 값보다 리스트 요소가 작으면 k만큼 빼줌
                total -= k
            else: # 현재 값보다 리스트 요소가 크면 현재 값만큼 빼줌
                total -= mid
        else:
            break

    if succeed:
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)    

문제 설명

문제

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

풀이 과정

• 문제지 분류에는 Union-Find로 나와 있는데, BFS로 푸는게 더 쉬울거 같아서 BFS로 풀이함.

1. 현재 기준 방문하지 않았으면서 비용이 가장 짧은 학생을 선택한 후, 연결된 모든 학생들을 BFS로 탐색
   • BFS로 탐색하면서 방문 처리 모두 해두어야 함.
2. 진행하다가 비용의 합계가 k보다 크다면 "Oh no" 출력
3. 모든 학생들이 방문 처리 되었다면 비용의 합계 출력

소스 코드

import sys
from collections import deque

input = sys.stdin.readline
N, M, k = map(int, input().rstrip().split())

costs = [0] + list(map(int, input().rstrip().split()))
visited = [False] * len(costs)

graph = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

def get_min_cost(costs, visited):
    cost = int(10e9)
    idx = -1
    for i in range(1, len(costs)):
        if not visited[i] and cost > costs[i]:
            cost = costs[i]
            idx = i

    return (cost, idx)
total = 0
while True:
    cost, idx = get_min_cost(costs, visited)
    if idx == -1:
        print(total)
        sys.exit(0)

    total += cost

    if total > k:
        print("Oh no")
        sys.exit(0)

    queue = deque([idx])
    visited[idx] = True
    while queue:
        node = queue.popleft()
        for g in graph[node]:
            if not visited[g]:
                queue.append(g)
                visited[g] = True

문제 설명

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn= 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1+ T2
• 5 = T1+ T1+ T2
• 6 = T2+ T2or 6 = T3
• 10 = T1+ T2+ T3or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

풀이 과정

1. 미리 삼각수를 1000까지 구해둔다. (입력 범위가 3~1000)이므로
2. 삼각수의 개수가 많지 않으므로 3중 반복문으로 모든 경우의 수를 구해준다.
   • i + j + k가 입력받은 값인지 검사
   • 그나마 조금이라도 효율성 높이기 위해 i, j, k 각각이 입력받은 값보다 크면 continue
3. i + j + k가 입력받은 값이 된다면 1, 되지 않는다면 0 출력

소스 코드

import sys

start = 1
add = 2
Triangle = []
while True:
    Triangle.append(start)
    start += add
    add += 1
    if start >= 1000:
        break

def check(a, Triangle):
    for i in Triangle:
        if i >= a: continue
        for j in Triangle:
            if j >= a: continue
            for k in Triangle:
                if k >= a: continue
                if i + j + k == a:
                    return True

    return False


count = int(sys.stdin.readline().rstrip())
for i in range(count):
    n = int(sys.stdin.readline().rstrip())
    if check(n, Triangle):
        print(1)
    else:
        print(0)

문제 설명

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

한 학기에 들을 수 있는 과목 수에는 제한이 없다.
모든 과목은 매 학기 항상 개설된다.
모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

입력

첫 번째 줄에 과목의 수 N(1≤N≤1000)과 선수 조건의 수 M(0≤M≤500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A<B인 입력만 주어진다. (1≤A<B≤N)

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.

풀이 과정

1. 위상 정렬 알고리즘 사용
   • 진입 차수가 0인 노드들을 방문한다.
   • 진입 차수가 0인 노드에 연결된 간선을 제거해준다.
   • 간선 제거로 인해 진입차수가 0이 되는 노드들을 다음에 방문한다.
2. 위 알고리즘 과정이 선수과목과 같음.
   • 자바1 -> 자바2를 들어야 한다고 가정
   • 자바1의 진입 차수는 0이고, 자바2의 진입 차수는 1이므로 자바1 먼저 방문하고, 자바2를 방문하여야 함.
3. 큐에 노드 뿐만 아니라 학기도 같이 저장하여 준 다음, 방문 시 각 과목의 학기를 따로 저장

풀이 과정

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
semester = [0] * (N+1)
queue = deque()


for _ in range(M):
    src, dest = map(int, input().rstrip().split())
    graph[src].append(dest)
    indegree[dest] += 1

# 초기 진입차수가 0인 노드 등록 
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append([i, 1])

while queue:
    cur, sem = queue.popleft()
    semester[cur] = sem
    for n in graph[cur]:
        indegree[n] -= 1
        # 진입차수가 0이 되면 들을수 있는 과목이므로 넣어준다.
        if indegree[n] == 0:
            queue.append([n, sem+1])

print(*semester[1:])

풀이 과정

1. 위 그림을 보면 바깥쪽 삼각형을 채우고, 안쪽 삼각형을 채우는 구조로 볼 수 있다.
2. 삼각형을 채울 때는, 맨 위 시작점을 기준 3가지 과정을 거친다.
   1. 아래로 이동
   2. 우측으로 이동
   3. 왼쪽 위 대각선으로 이동
3. 시작점을 조정해 가면서 2번 과정을 거치면 된다.
   • 시작점의 경우 (0, 0), (2, 1), ... (2n, n)
4. 종료 조건은 모든 삼각형을 채운 경우이다.

소스 코드

def solution(n):
    lists = [[0] * i for i in range(1, n+1)]
    idx = 1
    i = 0
    while True:
        x = 2 * i
        y = i
        i += 1

        # 아래 내려가는 부분
        while x < n and lists[x][y] == 0:
            lists[x][y] = idx
            x += 1
            idx += 1
        x -= 1

        # 오른쪽 진행
        y += 1
        while y < x+1 and lists[x][y] == 0:
            lists[x][y] = idx
            y += 1
            idx += 1
        y -= 1

        # 대각선 왼쪽 위 진행
        x -= 1; y -= 1
        while lists[x][y] == 0:
            lists[x][y] = idx
            x -= 1
            y -= 1
            idx += 1

        # 전체 체크
        end = True
        for l in lists:
            for e in l:
                if e == 0:
                    end = False
                    break
            if not end:
                break

        if end:
            break

    answer = []

    # 정답 저장
    for l in lists:
        for e in l:
            answer.append(e)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

Given therootof a binary tree,determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keysless thanthe node's key.
• The right subtree of a node contains only nodes with keysgreater thanthe node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in the tree is in the range[1, 104].
• -231<= Node.val <= 231- 1

풀이 과정

1. 처음엔 부모 노드 기준으로 왼쪽, 오른쪽 노드의 값을 검사하는 방식으로만 진행
   • 트리의 깊이가 깊어지면 틀림.
   • 루트 노드 기준으로 .. 왼쪽 서브 트리의 모든 값은 루트 노드보다 작아야 되고, 오른쪽 서브 트리의 모든 값은 루트 노드보다 커야 함.
2. 따라서, 범위를 기준으로 Validate 진행
   • 초기 범위를 -2의 32승 ~ 2의 32승으로 두고
   • 현재 노드의 값이 범위 내에 들어있는지 검사(들어있지 않다면 False)
   • 현재 노드의 값이 범위 내에 들어있으면 자식 노드들 방문
     • 방문할 때, 범위 조절해주어야 함. 현재 범위가 (a ~ b)라면
     • 왼쪽 방문할 때는 (a ~ 현재 노드의 값)
     • 오른쪽 방문할 때는 (현재 노드의 값 ~ b)
3. 모든 노드들에 대해 조건 만족하는 경우 이진 트리이므로 True, 아니면 False 리턴

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        flag = False
        def validate(root, fr, to):
            if root == None:
                return True

            if fr < root.val and root.val < to:
                return validate(root.left, fr, root.val) and validate(root.right, root.val, to)
            else:
                return False

        return validate(root, -2**32, 2**32) 

문제 설명

3.Longest Substring Without Repeating Characters

Medium

Given a strings, find the length of the longest substring without repeating characters.

Example 1:
**Input:** s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:
Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 10^4
• consists of English letters, digits, symbols and spaces.

풀이 과정

1. 현재 중복을 검사할 set과 Substring을 담을 queue를 구성한다.
2. 문자열을 왼쪽에서부터 오른쪽으로 문자 하나씩 진행한다
   • 문자 하나씩 반복문을 진행한다.
   • 만약 문자가 set 안에 있는 경우는, 기존 길이가 answer보다 길다면 저장한 다음, 해당 문자까지 queue와 set에서 빼주고 set하고 queue의 맨 마지막에 해당 문자를 다시 넣어준다.
   • 만약 문자가 set 안에 있지 않은 경우는 그대로 queue와 set에 넣어주면 된다.
3. 길이 최댓값을 리턴

소스 코드

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        length = 1
        if len(s) == 0:
            return 0
        check = set([s[0]])
        queue = deque([s[0]])
        for i in range(1, len(s)):
            if s[i] not in check:
                length += 1
                check.add(s[i])
                queue.append(s[i])
            else:
                answer = max(length, answer)
                while queue:
                    p = queue.popleft()
                    check.remove(p)
                    if p == s[i]:
                        break
                queue.append(s[i])
                check.add(s[i])
                length = len(check)

        answer = max(length, answer)
        return answer

문제 설명

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

풀이 과정

1. 전위 순회는 루트를 먼저 순회하므로, 전위 순회한 순서대로 노드를 넣어서 이진 검색 트리를 만들면 문제와 똑같은 트리가 만들어 진다.
   • 현재 노드보다 작으면 왼쪽 자식 노드
   • 현재 노드보다 크면 오른쪽 자식 노드
   • 자식 노드가 None인 경우 거기다가 넣어준다.
2. 후위 순회의 경우 recursion으로 구현한다. (left -> right -> 루트)
3. 입력 종료 글자가 없으므로 try..except로 입력 종료

소스 코드

import sys

sys.setrecursionlimit(10**5)

class tree_node():
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element


def push_tree(tree, element):
    if tree.element == None: # 맨 위 루트노드는 초깃값 None
        tree.element = element
    else:
        temp = tree_node(element)
        while True:
            # 현재 트리의 요소보다 입력값이 크면 오른쪽
            if tree.element < element:
                if tree.right == None:
                    tree.right = temp
                    break
                else:
                    tree = tree.right
            # 작으면 왼쪽
            else:
                if tree.left == None:
                    tree.left = temp
                    break
                else:
                    tree = tree.left

def post_order(tree):
    if tree == None:
        return
    post_order(tree.left)
    post_order(tree.right)
    print(tree.element)

Tree = tree_node(None)
while True:
    try:
        p = int(input())
        push_tree(Tree, p)
    except:
        break

post_order(Tree)

풀이 과정

• row와 column의 범위가 작은 편이므로 combinations를 사용하여서 풀이

1. 모든 column의 조합들을 구한다. (1개 ~ column의 길이)
2. 각각의 column 조합에 대해 최소성과 유일성 검사
   • 최소성의 경우는, 각 column의 조합에 대해 다시 조합들을 구한 뒤, 조합들중 하나라도 후보키에 있는지 검사
   • 유일성의 경우는, 릴레이션에서 각 튜플들에 대해 column의 조합으로 데이터를 구성하여 하나씩 넣어본 다음, 중복되는 요소가 있다면 유일성 만족하지 않음.
3. 후보키의 개수를 리턴해주면 된다.

소스 코드

from itertools import combinations

# 유일성 만족 확인
def simulation(relation, columns):
    compare_set = set()
    for tup in relation:
        target = []
        for col in columns:
            target.append(tup[col])
        target = tuple(target)
        if target in compare_set:
            return False
        compare_set.add(target)
    return True

# 최소성 확인(자신보다 짧은 최소키가 있는지)
def check_in_set(candidate, case):
    case_len = len(case)

    for i in range(1, case_len+1):
        total_case = list(combinations(case, i))
        for case_ in total_case:
            if case_ in candidate:
                return False
    return True


def solution(relation):
    answer = 0
    col_len = len(relation[0])
    cols = [i for i in range(col_len)]
    candidate = set()
    for i in range(1, col_len+1):
        all_case = list(combinations(cols, i))
        for case in all_case:
            # 유일성과 최소성을 만족하는지 확인
            if check_in_set(candidate, case) and simulation(relation, case): 
                candidate.add(case)
                answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. "ICN"이 시작점이므로, ICN에서 시작하여 DFS를 진행하면서, DFS의 깊이가 ticket의 길이까지 진행되는지 체크
   • 이 때, 가능한 경로가 2개 이상인 경우 알파벳 순서가 앞서는 경로를 return 해주어야 한다.
   • 따라서, 시작하기 전에 tickets의 2번째 요소([i][2]) 기준으로 오름차순 정렬 해 준다.
2. DFS를 진행하면서 정답과 방문여부에 push/pop 해주고, DFS를 ticket의 길이만큼 깊게 진행하였다면 정답 리스트를 출력해주면 된다.

• DFS의 이론은 알겠는데 Recursion에서 정답을 어떻게 표시해 주어야 할지 공부가 더 필요함..

소스 코드

end_flag = False
answer = []

def dfs(tickets, visited, city):
    global end_flag, answer
    if len(visited) == len(tickets):
        answer.append(city)
        end_flag = True
        return

    for i in range(len(tickets)):
        if tickets[i][0] == city and i not in visited:
            visited.add(i)
            answer.append(tickets[i][0])
            dfs(tickets, visited, tickets[i][1])
            if end_flag:
                return
            answer.pop()
            visited.remove(i)


def solution(tickets):
    global answer
    tickets.sort(key=lambda x:x[1])
    dfs(tickets, set(), "ICN")

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges