효팍이의 프로그래밍

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

백준 1068번 트리 백준 1068번 트리 설명 부모노드의 리스트, 지울 노드로 dfs를 호출한다. 지울 노드 값의 부모 리스트를 -2로 바꾸고 부모 리스트를 돌면서 지울노드가 있는지 찾는다. 있으면 지울 노드의 자식 노드들이 있다는 말이기 때문에 그 값을 지울 노드로 해서 dfs를 호출해서 그 값을 -2로 바꿔준다. 이렇게 하면 지울노드와 그 자식노드 모두다 그 위치에 부모노드 리스트에 -2가 박힌다. 그 다음 부모 노드 리스트 인덱스로 쭈욱 돌면서 그 값이 -2가 아니고, 인덱스가 부모리스트에 아에 없는 값이 있으면 count를 1 증가 시키고, count가 정답 인덱스가 부모 리스트에 없으면 그 인덱스를 부모로 가지는 자식이 없다는 말이기 때문에 그 인덱스는 리프노드임 코드 import sys fr..

백준 1005번 ACM Craft 백준 1005번 ACM Craft 설명 진입 차수 배열을 만들어서 해당 건물 전에 미리 지어야 할 건물이 있으면 해당 건물을 인덱스로해서 배열의 값을 1씩 증가시킨다. 각 건물마다 지을 때까지 걸리는 시간을 넣기위한 배열 dp를 만든다. 맨 처음에 진입 차수가 0인 건물을 큐에 다 집어 넣고, 그러면서 동시에 해당 건물의 dp 값도 해당 건물을 짓는데 걸리는 시간으로 다 바꿔준다(진입 차수가 0이니깐 그냥 그 해당 건물을 바로 지을 수 있음). 큐를 왼쪽부터 하나씩 빼면서 그 건물 다음으로 지을 수 있는 건물을 확인하면서 진입 차수를 1씩 빼준다. (다음 지을 수 있는 건물의 dp 값)과 (바로 전건물의 dp + 다음 지을 수 있는 건물 건설시간) 이 둘을 비교해서 더 ..

백준 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에서 답을 가져와서 사용함으로써 깊이 탐색의 시간을 줄인다..

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

백준 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) # 리프노드 집합..

백준 13549번 숨바꼭질3 백준 13549번 숨바꼭질3 bfs 다익스트라로 최소 거리를 계산함. 순간이동은 비용 0이라서 데크 appendleft()로 맨 앞에다 넣어줘야함. 코드 import sys import collections input = sys.stdin.readline N, K = map(int, input().split()) Q = collections.deque([(N, 0)]) visited = [False]*100001 while Q: loc, count = Q.popleft() if loc == K: print(count) break if not visited[loc]: visited[loc] = True if 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를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으..

문제 NxN 크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 출력 첫째 줄에 -1로만 채워진 종이의..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력1 2 출력1 1 입력2 10 출력2 3 코드 from sys import stdin from collections import defaultdict class Solution: dp = defaultdict(int) def makeOne(self, N: int)..

문제 정수 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..