효팍이의 프로그래밍

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

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

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

Python Code Snippet 리스트를 문자열로 바꾸면서 앞, 뒤에 문자열 추가하고 중간 중간에 들어갈 문자열도 직접 지정하기 iu = ["1", "2", "3"] print("", sep='') # 결과 : 리스트 2개 이상의 기준으로 정렬하기 iu = [[4,3],[2,1]] iu.sort(key=lambda x: (x[0], x[1])) print(iu) # [[2, 1], [4, 3]] 리스트에서 특정 단어 및 숫자의 인덱스가 여러개 있을 때 test_list = [1, 3, 4, 3, 6, 7] print("Original list : " + str(test_list)) res_list = list(filter(lambda x: test_list[x] == 3, range(len(test_..

문제 다음 소스는 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를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으..

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

문제 선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 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에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. ..

문제 링크 코드 def solution(record): answer = [] myDict = {} # 어차피 바뀐 아이디로 출력해야되니깐 dict에 싸그리 업데이트해서 넣음 for r in record: tmp = r.split() if len(tmp) == 3: action, id, nick = tmp[0], tmp[1], tmp[2] else: action, id = tmp[0], tmp[1] if action == "Enter" or action == "Change": myDict[id] = nick # 다시 for문 돌려 꺼내면서 Enter, Leave만 찾아 print for r in record: tmp = r.split() if len(tmp) == 3: action, id, nick = t..

문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 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..