목록Algorithm/Learning (17)
Cherry & Cherish
[Algo] 플로이드 워셜 문제풀이
플로이드 워셜 알고리즘 INF = int(1e9) #무한을 의미하는 값으로 10억을 설정 #노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) #2차원 리스트(그래프 표현)를 만들고, 모든 값으로 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] #자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 #각 간선에 대한 정보를 입력받아, 그 값으로 초기화 for _ in range(m): #A에서 B로 가는 비용은 C라고 설정 a, b, c = map(in..
[Algo] 다익스트라 문제 풀이
다익스트라 알고리즘 import heapq import sys input = sys.stdin.readline INF = int(1e9) #노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) #시작 노드 번호를 입력받기 start = int(input()) #각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n + 1)] #최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1) #모든 간선 정보를 입력받기 for _ in range(m): a, b, c = map(int, input().split()) #a번 노드에서 b번 노드로 가는 비용이 c라는 의미 ..
[Algo] 정렬 문제풀이 4
버블 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def bubble_sort(arr): end = len(arr) - 1 while end > 0: last_swap = 0 for i in range(end): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] last_swap = i end = last_swap count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 for i in range(len(count)): for j in range(count[i]): print(i, end=' ') 백준 1427 소트인사..
[Algo] 정렬 문제풀이 3
계수 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 for i in range(len(count)): for j in range(count[i]): print(i, end=' ') 프로그래머스 K번째 수 def solution(array, commands): answer = [] for a in range(len(commands)): i = commands[a][0] j = commands[a][1] k = commands[a][2] temp = array[i-1:j] temp.sort() answer.append(temp[..
[Algo] 정렬 문제풀이 2
퀵 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: return pivot = start left = start + 1 right = end while left right: array[right], array[pivot] = array[pivot], array[right] else : array[left], array[right] = array[right], array[left] quick_sort(array, start, right-1) quick_sort(array, right+1, end) quick_sort(array, 0, len(array)-1) print(..
[Algo] 정렬 문제풀이
선택정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) 백준 10816 숫자카드2 from bisect import bisect_left, bisect_right from sys import stdin n = stdin.readline().rstrip() card = list(map(int,stdin.readline().split()..
[Algo] 이분탐색 문제풀이
기본문제 def binary_search(array, target, start, end) : while start target : end = mid - 1 #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else : start = mid + 1 return None #n(원소의 개수)과 target(찾고자 하는 문자열)을 입력 받기 n, target = list(map(int, input().split())) #전체 원소 입력받기 array = list(map(int, input().split())) #이진 탐색 수행 결과 출력 result = binary_search(array, target, 0, n-1) if result == None: print("존재하지 않음") else :..
[Algo] bfs 연습
기본문제 from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: v = queue.popleft() print(v, end=' ') for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [False] * 9 bfs(graph, 1, visited) 미로탈출 from collections impor..