코생코사

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이 문제는 diff와 level을 비교해서 level = diff일 경우로 나눠서 진행합니다. level (time_cur + time_prev) * (diff - level) + time_cur 만큼의 시간 소요level >= diff인 경우 time_cur 만큼의 시간 소요 이 때 limit 시간 안에 해결할 수 있는 level을 찾으면 되는데요.저는 처음에 반복문으로 1부터 max(diff)까지 순차적으로 확..

https://www.acmicpc.net/problem/1629 분할 정복을 이용한 문제A=4, B=16일 때 4**16= (4^8) * (4^8)     = (4^4) * (4^4)          = (4^2) * (4^2)              = (4^1) * (4^1) 만약 B가 홀수라면A=4, B=17일 때 4**17= (4^8) * (4^8) * 4 B가 홀수일 때와 짝수일 때를 나눠서 분할 정복을 해주면 된다 + 나머지 계산C를 이용해 나머지 계산을 할 때나머지 연산 분배 법칙을 이용한다a / n을 한 몫을 q1, 나머지를 r1b / n을 한 몫을 q2, 나머지를 r2 라고 했을 때 a = (q1 * n) + r1b = (q2 * n) + r2 (a × b)= ( (q1 ​× n) + ..

https://www.acmicpc.net/problem/9251 참고: https://osnim.tistory.com/entry/%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4-LCSLongest-Common-Subsequence-%ED%8C%8C%EC%9D%B4%EC%8D%AC 최장 공통 부분수열, LCS(Longest Common Subsequence) (파이썬)LCS (Longest Common Subsequence)이란? 2개 이상의 문자열에서에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미합니다. LCS은 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나osnim.tistory.comD..

1. 현재 노드를 스택에 삽입 (visited는 빈 리스트)2. 스택에서 노드를 꺼낸다.3. 꺼낸 노드가 방문되지 않았다면 인접 노드를 전부 스택에 넣는다2, 3 반복 def dfs(start_node, graph): st = [start_node] visited = [] while st: v = st.pop() # 방문하지 않았다면 if v not in visited: # 방문 처리 visited.append(v) print(v, end=' ') # 스택에 넣는다(graph가 오름차순으로 정렬되어 있고, 오름차순으로 방문) st.extend(gr..

https://www.acmicpc.net/problem/1309 DP를 사용 맨 위의 두 칸을 세 가지 경우로 나눈다- 공백: 두 칸에 아무도 없음- 좌: 왼쪽 칸에 사자 있음- 우: 오른쪽 칸에 사자 있음 만약 n이 1이라면위처럼 세 가지 경우가 있습니다  n이 2인 경우를 보겠습니다 그런데 아래 칸(파란색)의 경우의 수는n=1일 때의 경우의 수와 같습니다  즉 맨 위의 두 칸이 공백이면 n-1의 모든 경우의 수가 올 수 있고,왼쪽만 있으면 n-1의 경우의 수 중 공백과 오른쪽이 채워져 있는 경우가 올 수 있고,오른쪽만 있으면 n-1의 경우의 수 중 공백과 왼쪽이 채워져 있는 경우가 올 수 있습니다. dp 점화식으로 풀게 된다면# 0번 째는 공백(사자 없음), 1번 째는 왼쪽에 사자, 2번 째는 오른..

https://www.acmicpc.net/problem/5639 입력, 재귀를 위한 limit 제한import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**9) 1. 트리 만들어서 postorder 하기2. 트리 없이 리스트로 postorder 하기 3. 인덱스를 이용해서 postorder하기   1. 트리 만들어서 postorder 하기 트리 클래스 생성class Node: def __init__(self, node): self.node = node self.left = None self.right = None # 추가 함수 def plus(self, res): # res: 들어오는 값 ..

전위 순회(preorder): A -> B -> C중위 순회(inorder): B -> A -> C후위 순회(postorder): B -> C -> A  https://www.acmicpc.net/problem/1991 재귀 함수를 이용  입력 및 트리 만들기import sysinput = sys.stdin.readlinen = int(input())tree = {}for _ in range(n): a, b, c = input().split() tree[a] = [b,c] # 0번 인덱스는 왼쪽 1번 인덱스는 오른쪽 print(tree){'A': ['B', 'C'], 'B': ['D', '.'], 'C': ['E', 'F'], 'E': ['.', '.'], 'F': ['.', 'G'], ..

https://www.acmicpc.net/problem/11725 각 노드마다 연결되어있는 노드를 저장하는 이차원 리스트를 만든다각 노드가 방문 여부를 저장하는 리스트를 만든다부모 노드를 저장하기 위한 parents라는 리스트를 만든다 -> DFS import sysinput= sys.stdin.readlinedef dfs(node): st = [node] while st: v = st.pop() for n in graph[v]: if visited[n] == False: parents[n] = v visited[n] = True st.append(n)n = i..

https://www.acmicpc.net/problem/1504 방법은노드 1 -> 노드 v1 -> 노드 v2 -> 노드 n노드 1 -> 노드 v2 -> 노드 v1 -> 노드 n두 가지 중 최소 경로를 구하고, 만약 INF 보다 크거나 같다면 -1을 출력하면 되는 문제였습니다.  일단 이 문제를 플로이드 워셜로 푸려고 했습니다(이유는.. 800 ** 3을 1억번보다 더 적게 나온다고 잘못 계산해서..)import sysinput = sys.stdin.readlineINF = int(1e9)n, e = map(int, input().split())graph = [[INF]*(n+1) for _ in range(n+1)]for i in range(1, n+1): graph[i][i] = 0 fo..

https://www.acmicpc.net/problem/1956 저는 노드가 400개이기 때문에400 ^ 3이 1억번보다 적어 플로이드 워셜 알고리즘을 사용해야겠다고 생각했습니다 import sysinput = sys.stdin.readlineINF = int(1e9)v, e = map(int, input().split())graph = [[INF]*(v+1) for _ in range(v+1)]for i in range(1, v+1): graph[i][i] = 0 for _ in range(e): a, b, c = map(int, input().split()) graph[a][b] = c # 단방향 for k in range(1, v+1): for i in range(..