알고리즘4 [알고리즘/Python] 플로이드-워셜(Floyd-Warshall) 알고리즘 1. 플로이드-워셜(Floyd-Warshall) 알고리즘이란? 모든 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다. 2. 동작방식 모든 노드간의 최단거리를 구하는 것이므로 2차원 인접 행렬을 구성한다. 각 경로의 중간 노드를 선택하여, 거리를 더 짧게 줄이는 과정을 반복한다. 초기 그래프를 인접형렬로 나타내면 아래와 같다. INF는 해당 노드에서 특정노드까지 가는 길이 없음을 의미한다. 시작/끝 0 1 2 3 0 0 5 INF 1 1 INF 0 7 2 2 3 INF 0 INF 3 INF INF 6 0 1) 1번 노드를 중간 노드로 설정할 경우 ① 값이 변경될 경우 dist[0][2] = min(dist[0][2], dist[0][1] + dist[1][2]) = .. 2023. 4. 1. [알고리즘/Python] 분할 정복(Divide and Conquer) 1. 분할 정복(Divide and Conquer)이란? 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘 문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다. 대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식 문제를 작은 부분 문제들로 분할한다. 분할된 부분 문제들을 각각 재귀적으로 해결한다. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3. 시간 복잡도 시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다. 대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 .. 2023. 3. 24. [Data Structure/자료구조] CS 질문 정리 🙋♀️ 공부하는 과정에 있습니다. 틀린 부분에 대한 지적은 언제든 환영합니다. Q. Array (List)의 가장 큰 특징과 그로 인해 발생하는 장·단점을 설명해주세요.Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 것입니다. index는 0부터 시작하며, index를 이용하여 특정 요소를 찾고 조작할 수 있다는 것이 장점입니다. 데이터의 중간에 요소가 삭제되거나 삽입되는 경우, 그 뒤의 모든 요소를 당기거나 밀어줘야한다는 단점이 있습니다. Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에 적절하지 않습니다. Q-1. Array를 적용시키면 좋을 데이터의 구체적인 예와 좋은 이유, 사용하지 않으면 어떻게 되는지주식차트, 주식차트는 데이터의 중간에 요소가 삽입 삭제 되는 타입이 아닌.. 2023. 3. 16. [알고리즘/Python] 이진 탐색(Binary Search) 너무 편향된 알고리즘 문제만 푼 나를 반성하며 이진 탐색에 대하여 정리해보려고 한다. 1. 이진 탐색이란? 검색 범위를 줄여나가며 특정 데이터를 검색하는 알고리즘 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 2. 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같으면 종료 (mid = key) 중간 값이 검색 값보다 크다면 중간 값 기준 오른쪽 구간을 대상으로 탐색 (mid < key) 중간 값이 검색 값보다 작으면 중간 값 기준 왼쪽 구.. 2023. 1. 28. 이전 1 다음
