이호진

1. 다익스트라 알고리즘 다익스트라 알고리즘은 가장 기본적인 최단경로 알고리즘이다. 값들을 비교하면서 최단경로를 갱신한다. 시간복잡도는 O(N^2)이다. def dijkstra(start): q=[] heapq.heappush(q,(0,start)) distance[start]=0 while q: dist,now=heapq.heappop(q) if distance[now]

플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구할 때 이용한다 3차원 리스트를 이용하기 때문에 노드의 개수가 많을 땐 사용하기 힘들다. 점화식으로는 Dab=min(Dab,Dak+Dkb)로 나타 낼 수 있다. -> 동적 프로그래밍 import sys input = sys.stdin.readline n = int(input()) m = int(input()) INF = int(1e9) graph = [[INF] * (n + 1) for i in range(n + 1)] #이차원 리스트로 graph를 선언한다. for i in range(1, n + 1): for j in range(1, n + 1): if i == j: graph[i][j] = 0 #자기 ..

최단 경로 알고리즘 최단 경로 알고리즘이란 1. 한 지점에서 다른 한 지점으로 갈 때 2. 한 지점에서 다른 모든 지점으로 갈 때 3. 모든 지점에서 다른 모든 지점까지 갈 때 를 구하는 알고리즘이다. 최단 경로 알고리즘에는 다익스트라 알고리즘, 플로이드-워셜 알고리즘이 있는데 이번 글은 다익스트라 알고리즘에 관한 내용이다. 다익스트라 알고리즘 다익스트라 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택한다는 점에서 그리디 알고리즘으로 분류될 수 있다. 1. 출발노드를 설정한다 2. 최단거리 테이블을 초기화한다. -> 다른노드는 무한, 자기자신은 0 3. 방문하지 않은 노드 중 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 코드로 살펴보면 import heapq # ..

다익스트라 알고리즘은 최단 경로 알고리즘 중 하나이다. 최단 경로 알고리즘에서 '음의 간선'이 없을 때 제대로 동작한다. 다익스트라 알고리즘의 원리는 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 3과 4의 과정을 반복한다. 다익스트라 알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. import sys input = sys.stdin.readline INF=int(1e9) n,m=map(int,input().split(..

크루스칼 알고리즘이란 신장 트리 중에서 최소비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 중 가장 대표적인 알고리즘이다. 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 2-1. 사이클을 발생시키면 최소 신장 트리에 포함하지 않는다. 2-2. 사이클을 발생시키지 않으면 최소 신장 트리에 포함한다. 3. 모든 간선에 대하여 2를 반복한다. 코드로 나타내면 #크루스칼 알고리즘 v,e = map(int,input().split()) parent=[0]*(v+1) for i in range(v+1): parent[i]=i def find_parent(parent,a): if parent[a] != a: parent[a]=fin..

이 문제는 NxM의 얼음틀에서 0끼리 뭉쳐 있는 부분의 개수를 구하는 문제다. 예를들어 00110 00011 11111 00000 이 주어지면 0끼리만 뭉쳐있는 부분이 세군데이므로 3을 출력한다. DFS를 이용하여 0인 부분을 방문하고 1로 바꾼다. 그리고 재귀함수를 이용해 DFS를 상하좌우로 반복한 후, True를 반환한다. 그리고 main문에서 dfs가 True인 개수를 세면 1. (0,0)이 0이었기 때문에 dfs함수에 의해 1로 바뀌고 상하좌우의 0도 1로 바뀐다. 그리고 True를 반환하여 main문에서 count한다. 2. 1의 과정을 통해 0끼리 뭉쳐있는 부분은 이미 1로 바뀌었고 총 세군데를 방문하여 3이 출력된다. 코드로 나타내면 n,m=map(int,input().split()) 3 3..

BFS는 너비 우선 탐색을 뜻한다. DFS가 깊이 우선 탐색을 했던것과 다르게 BFS는 가까운 노드부터 탐색한다. 다르게 말해, 시작 노드로부터 거리가 같은 노드들이 한번에 탐색된다. 또, DFS는 스택과 재귀함수를 이용했지만 BFS에서는 큐를 이용한다. 동작 순서는 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다. 그리고 큐에서 노드를 꺼내고 방문하지 않은 인접 노드를 모두 큐에 삽입한다. 이를 반복한다. 예제를 풀어보면 graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] 그래프 입력이 들어올 때 from collections import deque def bfs(graph,start,visited): queue = deque([start])..

DFS란 깊이 우선 탐색을 말한다. 탐색 시작 노드를 스택에 삽입하고 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 스택에 넣고 방문처리 스택에 넣고 방문처리 이 반복을 재귀함수를 이용하여 진행한다. 예제를 풀어보면, graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] 이렇게 나타낸 그래프가 있을 때 (통상적으로 1부터 시작하므로 0번을 비워놓는다.) def dfs(graph,v,visited): visited[v]=True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visi..

이 문제는 문자와 숫자가 섞여있는 문자열을 받아서 문자는 문자끼리 모으고 숫자는 다 더해서 정렬 후 출력하는 문제다. 예를들어 CBA32ZXY12 라는 문자열을 입력받으면 ABCXYZ8을 출력한다. 입력받은 문자열을 for문을 이용하여 하나씩 문자는 문자끼리 append하고 숫자는 숫자끼리 value라는 값에 더해준다. 그리고 문자를 오름차순 정렬 후 문자와 숫자를 더하고 출력한다. data = input() CBA32ZXY12 result=[] value = 0 for x in data: if x.isalpha(): result.append(x) else: value += int(x) result.sort() if value != 0: result.append(str(value)) print(''.jo..

이 문제는 정수 n을 입력받아서 n시 59분 59초까지 숫자 3이 나오는 횟수를 카운팅하는 문제이다. 단순히, n 59 59를 문자열로 늘어놓고 이중에 3이 있는지 if '3' in str~ 로 검사하여 카운팅할 수 있다. 코드로 나타내면, h=int(input()) 5 count=0 for i in range(h+1): for j in range(60): for k in range(60): if '3' in str(i)+str(j)+str(k): count+=1 print(count) 11475 완전탐색 - 시각