효팍이의 프로그래밍

백준 1010번 다리 놓기 백준 1010번 다리 놓기 설명 itertools 모듈의 combinations 함수는 너무 느려서 math모듈의 comb 함수를 활용했다. 코드 import sys from math import comb # 조합을 위한 math comb 모듈 input = sys.stdin.readline class Solution: def get_bridge(self, N: int, M: int): # mCn을 반환 return comb(M, N) for _ in range(int(input())): N, M = map(int, input().split()) print(Solution().get_bridge(N, M))

백준 4256번 트리 백준 4256번 트리 설명 전위 순회는 가운데, 왼쪽, 오른쪽으로 가기 때문에 첫번째 값이 가운데 노드이므로 이 노드를 중위 순회에 적용하여 중위 순회를 가운데 노드 기준으로 왼쪽, 오른쪽으로 나누는 분할 정복 형태로 문제를 풉니다. 이렇게 트리를 만들고, 후위 순회로 찍어줍니다. 코드 import sys from typing import List input = sys.stdin.readline # 트리 구조체 선언 class TreeNode: def __init__(self, x, left=None, right=None): self.x = x self.left = left self.right = right class Solution: def tree(self, preorder: L..

백준 13305번 주유소 백준 13305번 주유소 코드 import sys from typing import List input = sys.stdin.readline class Solution: def gas_station(self, N: int, road: List[int], price: List[int]): answer = 0 # 첫번째 주유가격을 저장 money = price[0] for i in range(N-1): # 이전 주유가격보다 더 싼게 나오면 money를 갱신 if price[i] < money: money = price[i] # 그때그때마다 money와 도로를 곱해서 계산해준다. answer += money * road[i] return answer N = int(input()) lo..

백준 1072번 게임 백준 1072번 게임 설명 퍼센트 구할 때 100을 먼저 곱하고 나눠야지 정확하다. 코드 import sys input = sys.stdin.readline class Solution: def game(self, x: int, y: int): # 처음 x, y 퍼센트 percent = int(y*100/x) # 범위 전체로 해서 이분 탐색 start, end = 1, 1000000000 while start < end: mid = (start + end) // 2 # x, y에 mid를 각각 더해서 퍼센트를 구하고, # 처음 x, y의 퍼센트와 비교한다. cur = int((y+mid)*100/(x+mid)) if cur percent else -1 X, Y = map(int, in..

백준 2343번 기타 레슨 백준 2343번 기타 레슨 코드 import sys, math from typing import List input = sys.stdin.readline class Solution: def guitar_lesson(self, N: int, M: int, lesson: List[int]): # 블루레이의 크기로 이분 탐색 # 레슨을 블루레이에 한개씩만 담는다고 했을 때 최소 값을 알 수 있음 # 레슨의 길이중 가장 큰 값이 블루레이의 최소 값이 된다. # 레슨을 싹다 담았을 때가 최대 값 start, end = max(lesson), sum(lesson) answer = sys.maxsize while start mid: count += 1 total = 0 total += le..

백준 10844번 쉬운 계단 수 백준 10844번 쉬운 계단 수 설명 단순히 점화식을 찾으려고 하면 너무 복잡해진다. 2차원 배열에서의 점화 관계를 사용한다. 위 행렬을 A라고 할 때, A[i][j]는 j로 끝나는 i자리수의 계단의 수이다. 1자리수는 1~9까지 올 수 있으므로 그대로 dp를 채울 수 있고, 2자리수 부터는 0은 전자리수의 1인 경우와 9는 전자리수의 8일 경우이고 나머지는 전자리수의 하나적고 많은 경우의 합이다. 즉 점화식을 dp 배열로 표현하게되면 밑의 코드라고 볼 수 있다. dp[i][0] = dp[i-1][1] dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] dp[i][9] = dp[i-1][8] 코드 import sys input = sys.stdin.rea..

백준 1766번 문제집 백준 1766번 문제집 위상정렬을 사용한다.. 조건이 있는 문제의 번호들중 뒤쪽에 와야 되는 번호들에 차수를 계속해서 매긴뒤에, 아닌 번호들을 먼저 최소 힙에 다 넣고, 힙의 원소들을 빼면서 그 문제번호보다 뒤쪽에 와야하는 문제의 번호 차수를 1씩 차감하면서 0이되어야지 heap에 추가 시킨다. 차수가 0이 아니면 heap에 아직 현재 차감하고 있는 차수의 원소보다 더 빨리 풀어야하는 문제가 있기 때문에 최소 힙에 넣으면 안된다. 코드 import sys, collections, heapq from typing import List input = sys.stdin.readline class Solution: def workbook(self, N: int, M: int, check:..

백준 1167번 트리의 지름 백준 1167번 트리의 지름 아무점을 잡고 dfs로 가장 거리가 먼 정점을 찾는다. 이 정점을 기준으로 다시 dfs로 가장 먼 거리를 찾는다. 코드 from typing import List, Tuple import sys import collections input = sys.stdin.readline sys.setrecursionlimit(10**6) class Solution: def diameter(self, V: int, graph: List[List[Tuple]]): def dfs(u, count): visited[u] = True for v, w in graph[u]: if not visited[v]: vertex, weight = dfs(v, count+w) i..

백준 11779번 최소 비용 구하기 2 백준 11779번 최소 비용 구하기 2 경로와 비용을 defaultdict로 따로 만들어줬다. 두번째 코드는 왜 틀리는지 모르겠다..ㅠㅠ 코드 import sys import collections import heapq import copy from typing import List, Tuple input = sys.stdin.readline class Solution: def min_cost(self, start: int, end: int, g: List[List[Tuple]]): Q = [] heapq.heappush(Q, (0, start)) # 경로 저장 path = collections.defaultdict(list) # 비용 dist = [sys.maxs..

백준 2206번 벽 부수고 이동하기 백준 2206번 벽 부수고 이동하기 큐의 마지막 원소에 1(벽뚫기가능), 0(벽뚫기불가능)을 넣는다. visited에는 각 좌표마다 [0,0]을 만들고 인덱스가 0이면 벽이미 뚫어서 못뚫고, 인덱스가 1이면 벽을 뚫 수 있다. 인덱스가 어딘지에 따라서는 벽뚫을 수 있는 여부를 판단하고, 별개로 원소 값이 0이면 방문가능하고, 1이상이면 방문 불가로 판단해서 다시는 그곳을 방문하지 않는다. 방문한 곳의 개수를 visited에 계속 쌓아가면서 나중에 그걸 답으로 뱉는다. 코드 from typing import List import sys input = sys.stdin.readline import sys from collections import deque class So..

백준 1987번 알파벳 백준 1987번 알파벳 흠.. bfs에다가 set자료형으로 실행시간을 최대한 줄여서 풀어봤습니다.. 시간을 더 어떻게 줄일까요ㅠㅠ,, 코드 import collections from typing import List import sys input = sys.stdin.readline class Solution: def alphabet(self, R: int, C: int, board: List): """bfs를 탐색하기 위해 큐를 만드는데 set자료형으로 같은것을 없애야지 시간을 단축할 수 있음 예를 들면 IEHFALKC는 IEHF쪽에서 2가지의 경우로 A를 갈 수 있으므로 이런 경우 다 set으로 없애준다.""" # 큐에서 원소는 순서대로 x좌표, y좌표, 지금까지거쳐간 알파벳들..

백준 10799번 쇠막대기 백준 10499번 쇠막대기 코드 import sys input = sys.stdin.readline bar_razor = list(input().rstrip()) answer = 0 stack = [] for i in range(len(bar_razor)): # '('일 경우 계속 스택에 저장 if bar_razor[i] == '(': stack.append('(') else: #()라면 (를 pop하고 현재 스택에 들어있는 ( 수만큼 값을 더해준다. if bar_razor[i-1] == '(': stack.pop() answer += len(stack) else: stack.pop() #끄트머리 막대기 부분을 더해준다 answer += 1 print(answer)

백준 4949번 균형잡힌 세상 백준 4949번 균형잡힌 세상 re 모듈 sub 함수로 괄호를 빼고 다 없애준다. stack으로 괄호 짝이 맞는지 판별 코드 import sys input = sys.stdin.readline import re # 괄호들만 있는 문자열을 인자로 받아서 유효한 괄호인지 판단하는 함수 def is_valid(s): if len(s) == 0: return True stack = [] table = {')':'(', ']':'['} for char in s: if char not in table: stack.append(char) elif not stack or table[char] != stack.pop(): return False return len(stack) == 0 # ..

문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 ..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력1 2 출력1 2 입력2 9 출력2 55 코드 from sys import stdin from collections import defaultdict class Solution: def tiling(self, n: int): if n == 1: return 1 if n == 2: return 2 dp = defaultdict(int) dp[1], dp[2] = 1, 2..

문제 선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다. 야민정음이란, 비슷한 모양의 글자를 원래 문자 대신에 사용하는 것을 일컫는다. 예를 들어, ‘그대’는 ‘그머’로, ‘팔도비빔면’은 ‘괄도네넴댼’으로, ‘식용유’는 ‘식용윾’으로, ‘대호’는 ‘머호’로 바꿀 수 있다. 아무 문자나 치환할 수 있는 건 아니며 치환이 가능한 몇 개의 문자들이 정해져있다. 예를 들어보자. (a, b), (a, c), (b, d), (c, d)가 주어지는 경우, a를 d로 바꾸는 방법은 a-b-d, a-c-d로 2개가 있다. (a, b), (b, c), (a, c)가..

문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. ..

문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며,..

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 출력1 6 입력2 10 4790 1 5 10 50 100 500 1..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 예제 입력1 7 3 출력1 코드 class Solution: d..

문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다. 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자. 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다..

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 ..

문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (..

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력1 7 1 6 6 3 3 5 4 1 2 4 4 7 출력1 4 6 1 3 1 4 입력2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 출력2 1 1 2 3 3 4 4 5 5 6 6 코드 from sys import stdin import collections class Solution: def..

문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 M과 N, 그리고 K가 빈칸을 ..

문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 출력 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다. 예제 입력1 5 8 1 2 2 1 3 3 1 4 1 1 ..

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 개수를 출력한다..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄..

문제 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL 코드 """ fixme https://leetcode.com/problems/reverse-linked-list/ Q15. 역순 연결 리스트 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL """ class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def reverseListRecur(self, head: ListNode) -> ListNode: def re..

문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 : height = [0,1,0,2,1,0,1,3,2,1,2,1] 출력 : 6 입력 : height = [4,2,0,3,2,5] 출력 : 9 코드 from typing import List class Solution: def trapTwoPointer(self, height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while left < right: left_max, right_max = max(left_max, heig..