이숭간 공부기록

최단경로 알고리즘이란, 가장 짧은 경로를 찾는 알고리즘 다양한 문제상황 한지점에서 다른 한지점 한 지점에서 다른 모든지점 모든 지점에서 다른 모든지점 각 지점은 그래프에서 노드로 표현하고 지점간 연결된 도로는 간선으로 표현함 ex ) 마을과 마을을 있는 도로, 도시를 있는 통로 등등 1. 다익스트라 알고리즘 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘) 동작과정 출발노드를 설정 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0) 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단..

순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 하나씩 확인 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색 ( 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.) 단계마다 절반씩 줄어드는 알고리즘의 시간복잡도는 보통 로그N 내코드 _ 잘못됨 ( 완전탐색이므로 시간초과남 ) n,m = map(int, input().split()) input_list = list(map(int, input().split())) for i in range(max(input_list), 0, -1): count = 0 for j in input_list: count += max(0, j-i) if count >= m: print(i) break 내코드2 _ 이진탐색으로 다시..