분류 전체보기

Dynamic Programming(DP)동적 프로그래밍정의 : 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘. ex) 피보나치 수열1️⃣ 재귀로 풀 때💡 재귀로 푼 다면 메모리 사용이 많이 커지고 같은 값을 중복으로 구하는 연산이 포함되어 있을 수 있어서 비효율적이다.def fibo(n): if n 2️⃣ DP를 사용했을 때    -1- Top Down 방식( Memorization) : 재귀재귀를 사용하지만 배열에 값을 저장해두기때문에 한번 구한 값은 다시 구하지 않아도 된다.def fibo(n, memo): if n     -2- Bottom Up  방식: for문O(1) 의 시간복잡도로 최종 값을 구할 수 있다.def fibo(N): if n  이 처..

https://www.acmicpc.net/problem/3055✔ 유형 : BFS✔ 문제 풀이: 시간당 고슴도치의 위치와, 시간당 물의 위치를 매 주기마다 업데이트 하고, 물도착시간이 고슴도치의 도착시간보다 느릴 때 고슴도치가 이동 가능함을 이용해 문제를 해결한다. 최소한으로 도착했을 때의 시간을 알아야 하기 떄문에 BFS를 사용한다. 코드import sysfrom collections import dequeinput=sys.stdin.readline # input함수 바꾸기# 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'# 비버의 굴 = D# 귀여운 고슴도치 = S# 매 분기 도치는 4방향중 한칸 이동가능. 물은 매분마다 비어있는 곳으로 확장. 한변을 공유하는 곳이면..

https://www.acmicpc.net/problem/2665✔ 유형 : 다익스트라✔ 문제 풀이: 문제에서 구하고자 하는 것은 최단 거리가 아니라 검은 방을 최대한 적게 지나야 하는 것이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데,/ 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.문제에 흰 방에 대한 최소 기준이 없다. 이 문제의 목표는 1. 처음에서 끝으로 도달2. 검은 방을 적게 거침 다익스트라 : 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘. 다익스트라 알고리즘을 이용하여 최단거리 = 검은방으로 바꾼 횟수로 문제를 해결하면 된다. 코드import ..

https://www.acmicpc.net/problem/2294 ✔ 유형 : DP✔ 문제 풀이: 여러개의 하위 문제를 먼저 푼후 그 결과를 쌓아올려 주어진 문제를 해결한다. 메모- 처음에 DFS로 풀었는데, 메모리 초과나서 방법을 찾다가 DP를 공부하고 DP로 풀었다. 근데 이게 정답인듯!!! DP 풀이1. 테이블 정의    D[i] = K 로 만들기 위해 필요한 연산 횟수의 최소값 2. 점화식    D[15] = D[14] + 1  ( 1을 더한 이유는 D[15-1]에 1을 더하는 연산 한번을 더하면 D[15]이기 때문)    D[15] = D[9] + 1  ( 1을 더한 이유는 D[15-6]에 5를 더하는 연산 한번을 더하면 D[15]이기 때문)    D[15] = D[3] + 1  ( 1을 더한 ..

https://www.acmicpc.net/problem/2637✔ 유형 : 위상 정렬✔ 문제 풀이:  위상 정렬을 이용한 최단거리느낌? 뭐라고해야하지ㅜㅜ 백준 Test Case를 분석해봤을 떄, ⬇️코드import sysfrom collections import deque input = sys.stdin.readlineN = int(input())M = int(input())Graph = { i : {} for i in range(1, N+1)} # 이중 딕셔너리!need = [0 for _ in range(N+1)] # indegree 개수를 센 리스트indegree = [0 for _ in range(N+1)]for i in range(M): X, Y, K = map(int, input().s..

https://www.acmicpc.net/problem/1707 ✔ 유형 : DFS✔ 문제 풀이: 이분 그래프의 특징을 이용해 DFS로 탐색해 나가며 조건에 위배 될 경우 탐색을 종료시킨다.- 방문하지 않은 노드를 탐색하려고 할 때 현재 노드와 다른 색으로 visited 배열에 저장을하고- 방문 했던 노드를 탐색하려고 할 때는, 자신과 같고 이어져 있다면 이분 그래프가 아니므로 탐색을 종료한다.  ✨ 주의 할 점1. 재귀를 쓰면 시간 초과가 날 수 있다.2. 모든 그래프가 연결 되어 있다는 보장이 없기 때문에, 전체 노드를 for문으로 탐색해야한다.  import sysfrom collections import defaultdictinput=sys.stdin.readline # input함수 바꾸기sy..

https://www.acmicpc.net/problem/11725 ✔ 유형 : DFS✔ 문제 풀이: 해당 노드와 연결된 노드들의 부모는 해당 노드라는 점을 이용해 배열에 자신의 부모 노드 번호를 저장한다. 백준의 테스트 케이스를 예시로 들어 설명하자면, 위와 같은 방법으로 계속 DFS를 돌리면 아래와 같이 부모 리스트가 채워진다.  ⬇️문제import sysinput=sys.stdin.readline # input함수 바꾸기sys.setrecursionlimit(10**5)# input N = int(input())Graph = {i: [] for i in range(1, N+1)}for i in range(N-1): u, v = map(int, input().split()) Grap..

https://www.acmicpc.net/problem/1197✔ 유형 : 최소 신장 트리, 크루스칼 알고리즘, union find✔ 문제 풀이: union find 알고리즘을 이용하여 거리가 최소인 간선과 정점을 선택하여 V-1개의 간선을 가진 부분 그래프를 만든다.  ⬇️코드 import sysinput=sys.stdin.readline # input함수 바꾸기# union find algorithmdef find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x]def union(parent,a,b): a = find_parent(par..

https://www.acmicpc.net/problem/5639✔ 유형 : 재귀✔ 문제 풀이: 이진 검색 트리의 특징과 전위 순회를 했을 때의 배열의 규칙을 찾아 범위를 줄여나가 탐색하며 오른쪽 서브트리와 왼쪽 서브트리를 구분해서 문제를 푼다.  해당 노드보다 큰 원소가 나올 때까지 탐색한다.큰 원소가 나오면 오른쪽 서브트리를 의미하고 큰 원소의 인덱스부터 오른쪽 서브트리.해당 노드 인덱스 + 1 부터 큰 원소의 인덱스 -1 까지는 왼쪽 서브트리임을 알 수 있다.  이제부터 위의 규칙을 이용해 재귀를 돌린다. 재귀를 계속 돌리면 결국 리프 노드까지 탐색이 완료되고, 같은 방법으로 왼,오 노드를 구분하여후위 순회의 순서대로 print를 해주면 된다.  ⬇️ 코드import sysinput=sys.stdi..

다익스트라다익스트라 알고리즘: 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘* 음수인 가중치를 가진 간선이 있다면 사용할 수 없다. 구현1. 자기 자신과의 거리는 0이므로 ① 번 인덱스의 값은 0으로 둔다.2. ①번 정점에서는 ②, ③ ,④ 번 정점으로만 갈 수 있는데, 최단거리 테이블에 3,2,5를 일단 써놓는다. (확정은 아님!)최단 거리 테이블을 d라고 했을 때, d[2]~d[6] 까지 최솟값을 찾아서 최단거리를 확정한다. 3. ③ 번 정점의 거리를 확정한 후 , 최단거리 테이블을 갱신한다.① 번 정점에서의 간선은 이미 확인 했기 때문에 ③ 번 정점에서 뻗어나가는 간선만 본다.①②③ 4. 가장 가까운 정점을 찾기 위해 d[2],d[4],~d[6] 확인. 5. 확정된 ④에서의 ..

신장 트리1. 모든 정점을 포함한 서브 그래프2. 트리의 성질 : 무방향이면서 사이틀이 없는 그래프3. 주어진 그래프의 정점이 V개일 때, 신장 트리는 V-1개4. 주어진 그래프가 연결 그래프일때만 신장 트리가 존재 최소 신장 트리주어진 방향성이 없는 그래프의 부분 그래프(Subgraph) 들 중에서 모든 정점을 포함하는 트리 부분 그래프 : 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프① 가운데 정점이 연결 되지 않음②,③ 사이클 존재 → 신장 트리가 아님④ 원래 그래프에 없던 간선 증가 → 부분 그래프 X 크루스칼 알고리즘1. 간선을 크기의 오름차순으로 정렬. 제일 낮은 비용의 간선을 선택한다.2. 현재 선택한 간선이 정점 u,v 를 연결하는 간선이라 할 때 만약 u와 v가 같은..

위상 정렬Topological Sort 정의 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬✨ 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다.           DAG(Directed Acyclic Graph) 구현 1. 제일 앞에 오려면 자신보다 앞에 있는 정점이 하나도 없어야 한다.= 자신에게 들어오는 정점이 없어야 한다.( indegree = 0 )  2. A를 위상정렬에 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다.→ A와 A에서 뻗어 나가는 간선을 모두 지운다.  3. 그래프에서 제일 앞에 위치 할 수 있는 정점. → 자신에게 들어오는 간선이 없는 정점 = C, G 4. 정점 C에서 뻗어나가는 간선 삭제. 제일 앞에 위치할 수 있는 ..