본문 바로가기

코딩테스트46

DP(재귀를 활용) 백준 9184 import sys def DFS(a,b,c) : if a 20 : return DFS(20,20,20) if dp[a][b][c] : return dp[a][b][c] elif a < b and b < c : dp[a][b][c] = DFS(a, b, c-1) + DFS(a, b-1, c-1) - DFS(a, b-1, c) else : dp[a][b][c] = DFS(a-1, b, c) + DFS(a-1, b-1, c) + DFS(a-1, b, c-1) - DFS(a-1, b-1, c-1) return dp[a][b][c] dp = [[[0 for _ in range(21)] for _ in range (21)] for _ in range (21)] while True: a,b,c= ma.. 2024. 2. 9.
백트래킹 백준 14888 import sys inputN = int(sys.stdin.readline()) N = list(map(int,sys.stdin.readline().split())) M = list(map(int,sys.stdin.readline().split())) plus = M[0] minus = M[1] multiple = M[2] divide = M[3] minnum = int(1e9) maxnum = -int(1e9) def DFS(plus,minus,multiple,divide,sum,depth) : global minnum global maxnum if depth == inputN : minnum = min(minnum,sum) maxnum = max(maxnum,sum) return i.. 2024. 2. 7.
DFS/BFS를 활용한 TSP 문제의 해결 **DFS/BFS를 푸는 방법 무조건, TREE부터 그리고 그 TREE의 특징을 이해하자. EX) 한번 간 경로만 구하면 된다. EX) 밑의 TSP는 DEPTH가 N이고(N-1) 그때 다음에 갈 곳이 START일때만 종료된다. 즉, BACKTRACKING의 조건 OR 가지치기의 조건을 잘 생각하자 백준 10971 TSP 문제를 도전하였으나, 실패 하였다. 일단 코드를 작성하고 , 그 흐름을 작성하겠다. import sys N = int(sys.stdin.readline()) forloop = 0 costlist = [list(map(int,sys.stdin.readline().split())) for _ in range(N) ] visited = [0] * (N) m = float('inf') def D.. 2024. 2. 4.
DFS/BFS의 선택 차이 - 최단 경로 풀기 백준 2178 자연스럽게 DFS로 풀려헀으나 , 해당 문제는 DFS로는 풀 수 없는 문제였다 . import sys import copy N,M = map(int,sys.stdin.readline().split()) graph = []*(N) for i in range(N) : graph.append(list(map(int,sys.stdin.readline().strip()))) # path = [ [False]*M for _ in range(N) ] def DFS(x,y,cnt) : if x= N or y= M : return if (x == N-1) and (y == M-1) : cnt = cnt + 1 return if copygraph[x][y] == 1 : copygraph[x][y] = 0 c.. 2024. 1. 30.
DFS/BFS - 인접한 노드들 중 조건에 맞고 모인 노드들의 수 찾기 백준 2468 이전에 풀었던 아이스크림 만들기 문제처럼, 코드를 작성하였다. import sys N = int(sys.stdin.readline()) height = [] x = 0 while x = N or y = N: return False if (cango[x][y] == False) and (height[x][y] > rain) : cango[x][y] = True #그 점은 지나.. 2024. 1. 28.
DFS /BFS - 순환 그래프 수 찾기 백준 11724 DFS로 풀어보았다. import sys sys.setrecursionlimit(10**9) N,M =map(int,sys.stdin.readline().split()) graph = [[] for _ in range(N+1)] path = [False] * (N+1) x= 0 while x < M : a,b = map(int,sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) x = x+1 def DFS(start_node) : path[start_node] = True for i in graph[start_node] : if path[i] == False : path[start_node] = True DFS(i) c.. 2024. 1. 25.
DFS와 BFS - 특정 점에서 모든 경로를 찾을 때 백준 1260번을 기준으로 풀어보겠다 from collections import deque import sys N,M,V = map(int,sys.stdin.readline().split()) graph = [[0]*(N+1) for _ in range(N+1)] for i in range(M) : x, y= map(int,sys.stdin.readline().split()) graph[x][y] = 1 graph[y][x] = 1 공통으로써, 1~5이지만 편의를 위해 0부터 GRAPH의 연결을 표시했다. 그 이후, 각 노드간의 연결점을 그래프로 표현하였다. visited = [True] * (N+1) 지나감을 알려주는 방법, 1차원 배열을 이런식으로 표현할 수 있음에 주의하자 DFS 준비 사항 : 1... 2024. 1. 23.
DFS와 BFS - 특정 연결을 찾을 때 코딩 테스트에서 가장 자주 활용되는 개념으로, 이 개념을 이렇게 빨리 접할 줄은 몰랐다. 그러나 개념 상에서 TREE를 사용하는 것이고 파이썬에선 주로 재귀의 형태로 이를 호출하기 때문에, 이 문제가 재귀 문제에 포함 되어 있어 이렇게 빨리 DFS와 BFS를 접하게 되었다. DFS란, 깊이 우선 탐색이라고 한다. 모든 노드를 탐색하는 것을 기반으로 한다 . 그 순서는 1. 내 자식을 왼쪽부터 검사한다. 2. 내 자식의 자식이 있다면 , 그 자식의 자식( 손자)를 검사한다 . 3. 내 자식의 자식을 모두 검사했거나 없다면, 다음 오른쪽 자식을 검사한다. BFS란, BEST가 아니었다..! 너비 우선 탐색으로 그 순서는 1. 내 자식을 왼쪽 부터 검사한다 . 2. 그 다음 (같은 LEVEL의 ) 자식을 오른.. 2024. 1. 22.
재귀 재귀함수란, 항시 배웠던 내용이다 . 일단 표헌식을 표헌할때 T(n) = a(나누어지는 갯수) x T(n/b(분할 크기))+해당 level에서 추가적으로 하는 일 로 표현한다. 재귀식의 모습은 def pivot() { ... .... .. return pivot() }꼴이다. 주로 . 재귀함수를 사용하면 몇번의 level을 거치지 않을때 사용하는 것으로 해보자. 사용하면 안되는 경우도 있는데, 그 크기가 유사한 여러가지로 분할되거나, 갯수가 마치 현재 크기만큼 많을때 사용해선 안된다고 배웠다. 간단한 예제 import sys def fib (n) : if n == 0 : return 0 if n == 1 : return 1 return fib(n-1) + fib(n-2) N = int(sys.stdin... 2024. 1. 21.
Stack, Queue, Deque Stack은 LIFO QUEUE는 FIFO 기억하자! 백준 28278번 해당 코드. sys.stdin을 사용하는것이 굉장히 중요하다. 기억할점 pop은 변수로 받아서 사용해야 한다. (print(answerlist.pop))시 이상한 수가 나온다 . 파이썬은 stack이나 queue가 따로 없다. 파이썬의 pop은 가장 마지막 애를 제거한다 (LIFO) 즉, STACK이다파이썬의 POP(0)는, 가장 처음 애를 제거한다 (FIFO)즉, QUEUE이다. 백준 4949번. import sys #LIFO STACK ! while True : a = sys.stdin.readline().rstrip() stack = [] if a == "." : break for i in a : if i == '[' or i .. 2024. 1. 11.

티스토리툴바