효팍이의 프로그래밍

백준 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..

백준 14503번 로봇 청소기 백준 14503번 로봇 청소기 코드 import sys from typing import List input = sys.stdin.readline class Solution: def vacuum_cleaner(self, N: int, M: int, r: int, c: int, d: int, board: List[List[int]]): """북, 동, 남, 서 순으로 d가 0, 1, 2, 3 이므로 이걸 인덱스로 해서 x, y 좌표를 만든다.""" x, y = (-1, 0, 1, 0), (0, 1, 0, -1) """빈칸이면 0, 벽이면 1, 청소했으면 2""" board[r][c] = 2 # 처음 값을 청소한 걸로 answer = 1 while True: check = Fa..

백준 11727번 2xn 타일링 2 백준 11727번 2xn 타일링 2 설명 타일로 채우는 경우의 수가 크게 3가지가 있다. n일 때 타일을 채우는 방법의 수를 f(n)이라고 하면, f(n-1)에서 2x1 타일 1개를 놓는 경우 f(n-2)에서 1x2 타일 2개를 놓는 경우 f(n-2)에서 2x2 타일 1개를 놓는 경우 f(n-2)에서 2x1 2개를 놓는 경우를 생각 할 수도 있지만, f(n-1)에서 2x1 타일 1개를 놓는 경우와 겹친다. 코드 import sys, collections input = sys.stdin.readline class Solution: def tiling(self, n: int): dp = collections.defaultdict(int) dp[1], dp[2] = 1, 3..

백준 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..

백준 1520번 내리막 길 백준 1520번 내리막 길 그냥 탐색으로 풀면 시간초과가 난다.. 그래서 dp 기법을 추가로 사용해야한다. 탐색해서 결과가 나오면 그걸 dp에 저장하고 다른 탐색 때 사용한다..흠.. 코드 import sys, heapq from typing import List input = sys.stdin.readline sys.setrecursionlimit(10**6) class Solution: def down_hill(self, M: int, N: int, graph: List[List[int]]): """dfs로 탐색을 하고 dp기법을 사용하여 배열에 각 칸마다의 결과 값을 저장해나가면서 이전에 갔었던 칸을 지나갈시에 dp에서 답을 가져와서 사용함으로써 깊이 탐색의 시간을 줄인다..

백준 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..

백준 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 # ..

백준 10830번 행렬 제곱 백준 10830번 행렬 제곱 divide and conquer로 제곱승, 제곱승x제곱승=4제곱승, 4제곱승x4제곱승=16제곱승 형태로 계산수를 줄인다. 곱한다음 1000으로 나눈 나머지나 1000으로 나눈 나머지 곱이나 같으므로, 받을 때, 곱할 때, 곱하고 나서 모두 1000으로 나눈 나머지로 바꿔준다. 안그럼 커짐. 행렬곱은 외워두는게 좋겠다.. 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline def multiply_matrix(arr1, arr2): answer = [] for idx1 in range(len(arr1)): row = [] for idx2 in range(len(arr2[0]))..

백준 1946번 신입 사원 백준 1946번 신입 사원 문제를 잘 읽어야한다. 성적의 순위를 입력 받으니깐 더 작은 값일수록 성적이 좋음. 서류랑 면접중 적어도 한개만 다른 지원자들보다 떨어지지 않으면 입사가능. 서류 성적 순위를 오름차순으로 정렬해서 서류성적이 가장 좋은 리스트의 첫번째 부분은 적어도 서류성적은 무조건 다른 지원자보다 좋으므로 답으로 가능. 그 뒤에 애들은 서류 성적이 전애들보다 무조건 안좋음. 그래서 면접 성적이 더 좋아야 입사 가능. 첫 친구의 면접 성적을 저장해두고 비교해가면서 만약 면접 성적이 더 좋으면(순위가 더 작으면) 서류 성적은 안좋지만 면접 성적은 좋으므로 답 가능임. 그 다음 면접 성적 비교 변수도 계속 지금까지의 가장 좋은 면접 성적 순위로 업데이트 해줘야함. 코드 i..

백준 12015번 가장 긴 증가하는 부분 수열 2 백준 12015번 가장 긴 증가하는 부분 수열 2 부분 수열의 길이만 찾으면 되므로, 수열 처음부터 증가하는 부분수열을 구해주면서 전 값보다 더 작은 값이 나와서 증가하는 부분수열이 멈추게 되면, 전까지의 증가하는 부분수열에서 현재의 수열 값의 위치를 찾아 정렬되게끔 리스트에서 값을 아에 교체해주면 길이는 결국 같게된다. 코드 import sys import bisect input = sys.stdin.readline N = int(input()) prog = list(map(int, input().split())) # N이 1이면 답 1 출력 if N == 1: print(1) exit(0) # answer 리스트에 수열 첫번째 값 넣고 두번째 부터 f..

백준 1967번 트리의 지름 백준 1967번 트리의 지름 루트에서 리프노드까지 탐색해서 최대 거리인 리프노드를 구하면 그 리프노드는 최대 거리에서의 한 점이 된다. 그 리프노드에서 다른 리프노드까지의 거리를 구하고 거기서 최대 값을 뽑아낸다. 루트 노드에서 간선이 한개밖에 없을때, 트리형태로 보면 루트노드가 리프노드처럼 보이므로 1번 최대 리프노드에서 루트까지의 거리도 고려해줘야함 코드 import sys import collections input = sys.stdin.readline graph = collections.defaultdict(list) n = int(input()) # n이 1일 때는 간선이 없으므로 0을 출력하고 종료 if n == 1: print(0) exit(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..

문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1

문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다. 벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력1 3 4 7 10 출력1 7 44 274 코드 from sys import stdin from collections import defaultdict class Solution: def sumOneTwo..

문제 선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 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종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 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가 주어진다. (..

문제 석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다! 아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y) 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다. 이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이..