1. (개선된) 다익스트라 알고리즘 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 - 각 노드에 대한 현재까지의 최단 거리를 계속 갱신 import heapq import sys INF = int(1e9) # n: 노드의 개수 # m: 간선의 개수 # start: 시작 노드의 번호 # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 초기화 graph = [[] for i in range(n+1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # a, b, c: a번 노드에서 b번 노드로 가는 비용이 c for _ in range(m): graph[a].append((b,c)) def dijkstra(start): q = [] # ..

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 먼저 단어의 길이가 key, 해당 길이의 단어들의 리스트를 value로 갖는 word_dict를 생성합니다. 같은 방식으로 단어의 앞뒤를 뒤집은 reversed_word_dict도 생성합니다. matching_dict라는 딕셔너리를 만들어 key는 하나의 쿼리, value는 해당 쿼리에 매칭되는 단어의 개수를 저장합니다. 이후 queries를 하나씩 꺼내면서 현재의 쿼리가 ?로만 이루어져 있으면 해당 쿼리 길이의 단어들의 개수를 matching_dict에 저장합니다. 쿼리가 ?를 접미사로 가지면, 해당 쿼리 길이의 단어들을 array, tar..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net C개의 공유기를 설치할 수 있는 가장 인접한 공유기 사이의 최대 거리를 이진탐색으로 탐색합니다. 최소 거리 min_gap을 1로, 최대 거리 max_gap은 (집 좌표 중 가장 큰 값) - (집 좌표 중 가장 작은 값)으로 설정합니다. 이후 min_gap과 max_gap의 중간값인 mid_gap을 구하며 다음을 반복합니다. mid_gap일 때 설..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 28, p 368 반복문으로 구현한 이진 탐색 코드를 참고하여 풀이했습니다. 고정점을 찾기 위해 if, elif, else 조건만 바꿔주어, 고정값을 찾으면 고정값을 반환하고, 현재 인덱스보다 현재 값이 더 큰 경우 왼쪽으로 이동(end를 mid-1로 갱신), 현재 인덱스보다 현재 값이 더 작은 경우 오른쪽으로 이동(start를 mid+1로 갱신)시킵니다. https://codlingual.tistory.com/189 이진 탐색 이진 탐색의 시간 복잡도: O(logN) 정렬되지 않은 길이 N의 리스트에서 M개의 값을 이진 탐색으로 찾을 때 시간 복잡도: O((M+N)*logN) 길이 N의 리스트 정렬하기: O(N*logN) 정렬된 길이 N의 ..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 27, p 367 재귀함수로 구현한 이진 탐색 코드를 참고하여 풀이했습니다. 타겟 값이 있는 인덱스를 result라는 집합에 모두 추가하고 이 집합의 길이를 반환했습니다. 기존의 이진 탐색과 동일하지만, 중간값이 타겟과 같은 경우 현재 중간값을 result 집합에 추가해주었고, 왼쪽과 오른쪽 모두에 타겟이 더 있을 수 있으므로 end를 mid-1로 갱신한 탐색, start를 mid+1로 갱신한 탐색 모두를 진행하도록 했습니다. 타겟 원소가 하나도 없으면 -1을 출력하도록 했으므로 result의 길이가 0보다 크면 len(result)를, 그렇지 않으면 -1을 출력하도록 했습니다. https://codlingual.tistory.com/189 ..

이진 탐색의 시간 복잡도: O(logN) 정렬되지 않은 길이 N의 리스트에서 M개의 값을 이진 탐색으로 찾을 때 시간 복잡도: O((M+N)*logN) 길이 N의 리스트 정렬하기: O(N*logN) 정렬된 길이 N의 리스트에서 M번 이진 탐색하기: O(M*longN) 1. 재귀 함수로 구현한 이진 탐색 코드 # 이진 탐색 소스코드 구현(재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간접 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid]..