어디까지 갈 수 있을까?

2. 플로이드 워셜 알고리즘 모든 노드 간 최단 거리를 구하는 알고리즘 출발노드에서 도착노드로 바로 가는 거리와 중간노드를 거쳐가는 거리 중 짧은 거리를 선택한다 2차원 배열을 생성해 중간노드를 갱신하는 횟수를 노드 갯수만큼 반복한다 시간복잡도는 O(N^3)이다 ① 테이블 초기화 ② 1번 노드를 거쳐 가는 경우 1번 노드와 관련된 노드, 출발노드와 도착노드가 같은 칸을 제외하고 확인해야한다. 1번 노드를 제외한 2번, 3번, 4번 노드에서 2개의 노드를 뽑는 경우를 고려해야 한다. 그러므로 고려해야할 칸은 모두 6 = 3P2 개다(주황색) D23=min(D23, D21+D13) D24=min(D24, D21+D14) D32=min(D32, D31+D12) D34=min(D34, D31+D14) D42=m..

알고리즘 문제를 접했을 때 '서로 다른 개체가 연결되어 있다' = '여러 개의 도시가 연결되어 있다'와 같은 내용이 나오면 그래프 알고리즘을 의심해보자 1. union-find(합집합 찾기, 서로소 집합) 차후 크루스칼 알고리즘과 위상 정렬에서 사이클이 발생했는지 판별할 때 사용한다 union-find 연산을 통해 최종 부모노드를 찾아가는 알고리즘이다 union(A, B)를 한다면 둘 중 부모노드의 값이 더 작은 노드로 합쳐진다 ① 그래프 생성 부모 노드 배열을 만들고 자기자신을 가리키는 것으로 초기화한다 union(4, 5) -> union(3, 4) -> union(2, 3) -> union(1, 2) 순으로 진행하기로 한다 ② union(4, 5) union(4, 5)가 진행되면 4와 5번 노드 중..

다익스트라 알고리즘 -한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 -일차원배열 사용 플로이드 워셜 알고리즘 -모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우 -중간노드 이용 -이차원 배열 사용 1. 다익스트라 알고리즘 특정한 노드에서 각 노드까지의 최단 거리를 구해주는 알고리즘 매번 '가장 비용이 적은 노드'를 선택하기 때문에 그리디 알고리즘으로 분류된다 우선순위 큐를 사용해 구현하면 시간 복잡도 O(ElogV)이 보장된다 거리를 우선순위로 큐에 삽입하기 때문에 거리가 짧은 노드부터 탐색하게 된다 다익스트라 알고리즘의 원리는 다음과 같다. 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. ..

전에 계산한 값들을 기반으로 현재 값을 구하면 된다 31, 32번 모두 비슷한 유형의 문제 dp문제는 그림을 그려 푸는 게 점화식 세우기 쉬운 듯 하다 31. 금광 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import sys input=sys.stdin.readline for _ in range(int(input().rstrip())): #n*m n, m=map(int, input().split()) arr=list(map(int, input().split())) d=[] i=0 d.append([0]*m) for _ in range(n): d.append(arr[i:i+m]) i+=m d.append([0] *..

큰 문제를 작은 문제로 나눠, 현재 계산된 수들을 바탕으로 앞으로의 값을 계산하는 프로그래밍이다 중복되는 연산을 피하기 위해 DP테이블에 계산해 놓은 값을 저장해놓는 (메모이제이션 = 캐싱) 기법 을 이용한다 시간복잡도는 O(logn)이다 탑다운 방식 재귀 함수 이용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 d=[0]*100 def fibo(x): if xd[i//5]+1: d[i] = d[i//5]+1 elif i%3==0 and d[i]>d[i//3]+1: d[i] = d[i//3] + 1 elif i%2==0 and d[i]>d[i//2]+1: d[i] = d[i//2] + 1 print(d[n]) cs 개미전사 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

27. 정렬된 배열에서 특정 수의 개수 구하기 12345678import sysfrom bisect import bisect_left, bisect_rightinput=sys.stdin.readline n, x=map(int, input().split())arr=list(map(int, input().split())) print(bisect_right(arr, x)-bisect_left(arr, x))cs 28. 고정점 찾기 12345678910111213141516171819202122import sysinput=sys.stdin.readline n=int(input().rstrip())arr=list(map(int, input().split())) start=0end=len(arr)-1check=0w..

1. 순차탐색 데이터를 앞에서부터 차례로 확인하는 방법 시간복잡도가 log(N) 1 2 3 4 5 6 7 8 9 10 11 12 import sys input=sys.stdin.readline print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요') a, find=input().split() print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.') arr=list(input().split()) for i in range(len(arr)): if arr[i]==find: print(i+1) break Colored by Color Scripter cs 2. 이진탐색 데이터를 반으로 쪼개며 탐색하는 방법 이미 정렬 돼 있는 데이터 안에서만..

23. 국영수 www.acmicpc.net/problem/10825 1 2 3 4 5 6 7 8 9 10 11 12 import sys input=sys.stdin.readline arr=[] for _ in range(int(input())): a, b, c, d=input().split() arr.append([a, int(b), int(c), int(d)]) arr.sort(key=lambda x:(-x[1], x[2], -x[3], x[0])) for i in arr: print(i[0]) Colored by Color Scripter cs 24. 안테나 www.acmicpc.net/problem/18310 1 2 3 4 5 6 7 import sys input=sys.stdin.readline ..