교대최소제곱법

최초 코드 from copy import deepcopy from collections import deque dr = [1, 0, -1, 0] dc = [0, 1, 0, -1] N, M = map(int, input().split()) graph =[] for _ in range(N): graph.append(list(map(int, input().split()))) zero_ls = [] virus_ls = [] for row in range(N): for col in range(M): if graph[row][col] == 0: zero_ls.append((row, col)) elif graph[row][col] == 2: virus_ls.append((row, col)) def count(visi..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이방법 DP를 활용한다 시간복잡도 O(N^2) : N dp를 구하고 dp의 크기 역순으로 index 접근 bisect 라이브러리의 bisect_left 함수를 활용 시간복잡도 O(N logN) : N < 10^6 타겟 수열의 원소는 알 수 없다 가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬 최근 들어, 알고리즘에 재미를 붙였다..

위상정렬이랑 DP를 활용하여 푸는 문제였다 위상정렬로 순서를 정하고 dp를 하는 것보다 위상정렬을 하면서 dp를 계산해나가면 되는 문제 25. 위상 정렬(Topology Sort) 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 ... blog.naver.com 위상정렬은 우선순위가 있는 작업들의 순서를 정렬할 때 사용되는 알고리즘이다 DAG Directed Acyclic Graph 유향 비순환 그래프에서만 사용 가능하다 (사이클일 경우 사용 불가) 왜죠? 순환 그래프의 경우 모두 연결되어 있어서 사이클 내에서는 시작점을 찾을 수 없기 때문이다 시간복잡도는 O(V+E) 매우 빠른 편 https://www.a..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 튜플은 리스트와 달리 불변성인 특성을 이용하여 빠르게 iteration을 돌 수 있다. 특히 이번 같은 경우 간선의 수가 많고 iteration을 많이 돌아야 하는 빡빡한 문제였기 때문에 튜플을 사용해야한다!! 시간 초과가 나거나 값을 바꾸지 않아도 되는 문제라면 튜플을 이용해보자! // 튜플 사용 = pass for _ in range(M): a, b, c ..

1197번: 최소 스패닝 트리 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 트리의 정의 트리란 사이클이 없이 모든 정점이 연결되어있는 그래프다. 왼쪽 자식이 어쩌구, 오른쪽 자식이 어쩌구 이딴 얘기는 트리의 정의에 포함되지 않는다 루트가 있어야 한다는 조건 이런것도 없다. 트리는 그저 사이클이 없이 모든 정점이 연결되어있는 그래프이므로, 하나의 노드에 자식 노드가 여러개일 수 있다. *이진트리와 헷갈리지 말자! 스패닝 트리 = 신장 트리 그래프의 부분 그래프를..

지수 법칙 A^m+n = A^m x A^n 나머지 분배 법칙 (AxB)%C = (A%C) *(B%C) % C 예제 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할 정복 → 11 이면 5, 6으로 스플릿 → 6 이면 3, 3으로 스플릿해서 계산한다 ex) a = 10 , b = 11 , c = 12 10^11 % 12 = ((10^5)%12 x (10^5)%12 x 10)% 12 = (((10^2)%12 x (10^2)%12 x 10) %12 x ((10^2)%12 x (10^2)%12 x 10) %..

다익스트라로 풀었다가 시간초과가 났다 플로이드 워셜 알고리즘 ‘거쳐가는 정점’을 기준으로 최단 거리를 구하는 알고리즘 장점 벨만-포드와 같이 음수 가중치가 있어서 가능하다 (단, 똑같이 음수 사이클이 있으면 안됨) 방향, 무방향 그래프 모두 가능하다 모든 쌍의 최단 거리를 구할 수 있다 단점 시간복잡도가 O(n**3)이다… 심지어 중간 결과를 저장하려면 많은 양의 메모리를 필요로 한다. 플로이드 워셜 vs 다익스트라 플로이드 와셜은 모든 거리를 구해야할 때 다익스트라보다 효과적이다 다익스트라는 각 시작노드마다 한번씩 돌려야 하기 때문 + 같은 노선의 버스가 여러대 있기 때문 + 참고 플로이드 와셜의 시간복잡도 : O(V^3) 다익스트라의 시간복잡도 : O((V + E) log V) 예제 문제 https:..

백준 1967번 # 메모리 초과 tree = [[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N-1): s, e, d = map(int, input().split()) tree[s][e] = tree[e][s] = d # 메모리 초과 해결 tree = [[] for _ in range(N+1)] for _ in range(N-1): s, e, d = map(int, input().split()) tree[s].append([e, d]) tree[e].append([s, d]) 무의식적으로 graph를 그렸는데 n이 10000이라 메모리초과가 났다 참고자료 https://programmers-story.tistory.com/10 [백준 알고리즘]..