기록되지 않은 것은 기억되지 않는다.

Algorithm | SQL 검색 결과

해당 글 27건

[Programmers | Level 3] 단어 변환 (Python)

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr from collections import deque def check(a, b): cnt = 0 for i, j in zip(a, b): if i != j: cnt += 1 if cnt == 1: return True def solution(begin, target, words): if target not in wor..

Algorithm | SQL/Programmers 2021. 5. 19. 14:54

[Programmers | Level 3] 네트워크 (Python)

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr from collections import deque def solution(n, computers): visited = [False] * n q = deque() cnt = 0 for i in range(n): if not visited[i]: q.append(i) visited[i] = True cnt += 1 while q: v = q.popleft(..

Algorithm | SQL/Programmers 2021. 5. 19. 13:53

[Python] 이진 탐색 (Binary Search)

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 정렬된 데이터에서 원하는 데이터를 빠르게 찾을 수 있다는 장점이 있다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용한다. 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색이다. 한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근하는 것을 고려해보면 좋다. 구현하는 방법에는 두가지가 있다. 1. 재귀 함수로 구현 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(ar..

Algorithm | SQL/개념 2021. 5. 17. 23:34

[BOJ 1238] 파티 (Python)

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 이용하여 최단거리로 X번 마을을 반환점으로 하여 왕복했을 때 가장 많은 시간을 소비하는 학생을 구하는 문제. N이 1000이기 때문에 N^3인 플로이드워셜은 사용할 수 없을 것이라 판단하였다. heapq를 이용한 다익스트라 알고리즘을 N번 돌려서 모든 출발점으로부터 X까지의 최단 경로를 구하였고, X번 마을에서 다른 마을들까지의 최단거리 테이블을..

Algorithm | SQL/BOJ 2021. 5. 15. 22:49

[Python] 최소 스패닝 트리(MST), 크루스칼 알고리즘 (Kruskal Algorithm)

신장 트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 N개의 노드로 만드는 스패닝 트리는 N-1개의 노드로 구성되어 있다. 유니온 파인드 알고리즘을 활용하여 사이클을 검사할 수 있고, 이를 활용하여 스패닝 트리를 만들 수 있다. 이중 최소한의 비용으로 구성된 스패닝 트리를 최소 스패닝 트리 (MST) 라고 한다. 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼, 프림 알고리즘이 있는데 크루스칼 알고리즘을 다뤄보겠다. 크루스칼 알고리즘 (Kruskal Algorithm) 핵심 원리 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다. 다만 사이클을 발생시키는 간선은 제외하고 연결한다. [1] 간선 비용에 따라 오름차순으로 정렬 [2..

Algorithm | SQL/개념 2021. 5. 15. 21:58

[Programmers | Level 3] 가장 먼 노드 (Python)

import heapq import sys input = sys.stdin.readline INF = int(1e9) def solution(n, edge): start = 1 graph = [[] for _ in range(n + 1)] distance = [INF] * (n + 1) for i in edge: graph[i[0]].append((i[1], 1)) graph[i[1]].append((i[0], 1)) q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist ..

Algorithm | SQL/Programmers 2021. 5. 15. 20:27

[Python] 유니온 파인드 알고리즘 (Union Find Algorithm)

노드들을 합치고(union), 부모를 찾아(find) 서로소 집합(disjoint set)을 찾아내는 알고리즘 트리 구조를 활용한다. find 연산은 부모 노드를 찾을 때까지 재귀적으로 호출한다. union 연산은 두 원소의 부모 노드를 찾고 번호가 큰 노드가 번호가 작은 노드의 부모를 가리키도록 한다. 이를 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 한다. # 특정 원소가 속한 집합을 찾기 def find(x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: return find(parent[x]) return x # 두 원소가 속한 집합을 합치기 def union(a, b): a = find(a) b = find(b) if a..

Algorithm | SQL/개념 2021. 5. 15. 19:47

[Python] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘 노드의 개수가 N개일 때 시간복잡도는 O(N^3) 각 단계에서 해당 노드를 거쳐가는 경우를 고려한다. 핵심 점화식 Dab : a를 거쳐 b로 가는 최단 거리 Dab = min(Dab, Dak + Dkb) 점화식을 이용하므로 DP라고 볼 수 있고 원리는 다소 어렵지만 코드는 아주 간단하다. 암기해서 사용하자. INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자..

Algorithm | SQL/개념 2021. 5. 15. 19:03