교대최소제곱법

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 [백준 알고리즘]..

기본적으로 순열, 조합 문제는 DFS 재귀함수를 이용해서 해결 순열 조합 모두 "없으면 넣고 dfs()" 구조는 똑같지만 조합의 경우 start를 고려해줘야 하는 차이가 있었음 -> s에 넣고 빼고를 반복하면서 모든 경우의 수를 돌린다 + 왜 백트래킹 문제인가? s의 개수가 M이상이 되면 그 다음 경우의 수는 파악할 필요가 없기 때문에 백트래킹 문제인 것 순열 # 15649번 n,m = list(map(int,input().split())) s = [] def dfs(): if len(s)==m: print(' '.join(map(str,s))) return for i in range(1,n+1): if i not in s: s.append(i) dfs() s.pop() dfs() 조합 # 15650번 ..

readme.md를 만들고 안만들고의 차이로 오류가 발생 참고자료 https://shortcuts.tistory.com/8 [총정리] 깃허브(Github) 파일 업로드, 파일 올리기 (git bash) 요약 //저장소 생성 및 연결 $ git init $ git remote add origin [원격저장소 주소] $ git branch -m master main //파일 업로드 $ git pull (또는 git pull origin [브랜치 이름]) $ git add . $ git commit -m "commit message" $ git push ( shortcuts.tistory.com readme 오류 발생 시 강제로 밀어넣기 git push -u origin +main https://doozi31..

분할정복 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 대표적으로 퀵소트, 머지소트 등이 있고 고속 푸리에 변환 문제 FFT 가 대표적 FFT? n차 다항식 두개를 곱할 때 시간을 줄이는 방법 O(n) → O(n log n) 다이나믹 프로그래밍 최적화 문제에 주로 사용 최적해 구조의 특징을 찾는다 재귀적으로 정의한다 바텀업 방식으로 접근한다 최적해를 구성한다 한 번 계산한 결과를 메모리 공간에 메모 리스트를 만들어서 값을 저장해놓고 계산하기전에 리스트를 체크하는 방식 *시간이 오래걸릴거 같으면 DP로 생각해보자 동적 프로그래밍은 시간-메모리 트레이드오프 관계를 가진다 그럼 다이나믹 프로그래밍을 언제 쓸 수 있을까? 최적 부분 구조 optimal substructure → 이는 그리디방..