본문 바로가기

Algorithm9

이진 탐색 🚩이진 탐색순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 🚩탐색 과정  🚩시간 복잡도시간 복잡도 O(logN) 🚩구현 코드# 재귀함수def binary_search(array, target, start, end): if start > end: # start가 end보다 크다면 탐색할 데이터가 없는 것 return None # 중간점 계산 mid = (start+end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == .. 2024. 10. 23.
플로이드 워셜 알고리즘 🚩플로이드 워셜모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산음의 가중치를 가지는 간선(엣지) 가능합이 음수 가중치를 가지는 사이클이 있어서는 안됨각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사노드의 개수 N일 때, 시간 복잡도는 O(N^3) 이므로 노드의 개수가 500개 이하일 때 사용 🚩플로이드 워셜 이해중간에 k 하나를 거쳐가는 게 왜 최단 경로를 구할 수 있는지 이해가 안 됐다.a -> k -> b 의 경로에서 a -> k 의 경로 또한 최단 경로로 최적화 되어 있을 것이니 중간 경로 k 하나만 추가 되어 보이지만 결국 a -> k도  a -> x -> k 처럼 최단 경로로 이루어져 있을 수 있을.. 2024. 10. 12.
다익스트라 알고리즘 🚩다익스트라 알고리즘특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작현실 세계의 도로는 음의 간선으로 표현되지 않음다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 🚩동작 과정출발 노드를 설정최단 거리 테이블을 초기화방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(Greedy)해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신위 과정에서 3번과 4번을 반복 🚩다익스트라 알고리즘 특징그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복단계를 거치며 한 번 처리된 노.. 2024. 10. 11.
삽입 정렬 삽입정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입데이터를 하나씩 확인하면서, 이 데이터는 어느 위치에 들어가는게 맞을 지 매번 계산해서 적절한 위치에 들어갈 수 있도록 해줌선택 정렬에 비해 구현 난이도가 높지만, 더 빠르게 동작앞쪽에 있는 원소들이 이미 정렬되어있다고 가정하고, 뒤 쪽에 있는 원소를 앞 쪽에 있는 원소의 위치 중에서 한 곳으로 들어가도록 만드는 방식으로 동작 처음 시작 시, 첫 번째 원소는 그 자체로 정렬되어 있다고 판단하고 두 번째 데이터가 어떤 위치로 들어갈지 판단.카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드를 기존 정렬된 카드 사이 올바른 자리를 찾아 삽입함으로써 정렬이 유지되도록 하는 것과 같음.  array = [7,5,9,0,3,1,6,2,4,8]fo.. 2023. 12. 18.

티스토리툴바