본문 바로가기

코테 공부 🔥/보충 공부 🔠6

[알고리즘/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] 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree) 구간 합, 최소값, 최대값 등의 쿼리를 빠르게 처리하기 위해 사용되는 자료구조 이진 트리(binary tree)를 기반으로 하며, 각 노드는 해당 구간의 합, 최소값, 최대값 등의 값을 저장한다. 1. 구성 기본 배열을 이용하여 세그먼트 트리를 초기화, 배열의 각 요소가 세그먼트 트리의 각 리프 노드에 대응된다. 이진 트리의 성질을 이용하여, 각 노드가 나타내는 구간을 두 개의 서브트리로 나눈다. 각 노드에 대해, 해당 구간의 합, 최소값, 최대값 등의 값을 계산하여 저장한다. 각 쿼리에 대해, 세그먼트 트리를 탐색하여 필요한 값을 계산한다. 리프 노드 : 배열의 그 수 자체 다른 노드 : 왼쪽 자식과 오른쪽 자식의 합을 저장 2. 시간 복잡도 트리의 높이가 log.. 2023. 3. 24.
[알고리즘/Python] 분할 정복(Divide and Conquer) 1. 분할 정복(Divide and Conquer)이란? 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘 문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다. 대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식 문제를 작은 부분 문제들로 분할한다. 분할된 부분 문제들을 각각 재귀적으로 해결한다. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3. 시간 복잡도 시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다. 대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 .. 2023. 3. 24.
[알고리즘/Python] 이진 탐색(Binary Search) 너무 편향된 알고리즘 문제만 푼 나를 반성하며 이진 탐색에 대하여 정리해보려고 한다. 1. 이진 탐색이란? 검색 범위를 줄여나가며 특정 데이터를 검색하는 알고리즘 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 2. 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같으면 종료 (mid = key) 중간 값이 검색 값보다 크다면 중간 값 기준 오른쪽 구간을 대상으로 탐색 (mid < key) 중간 값이 검색 값보다 작으면 중간 값 기준 왼쪽 구.. 2023. 1. 28.
[Python] 파이썬 딕셔너리 값 정렬 (key, value) 딕셔너리를 자주 사용하지 않아서 그런지, 한번 사용할 때마다 방법이 가물가물했다. 블로그에 딱 정리해두고 내 머리에도 정리해두자! 👶 dict_ex = { 'b':5, 'c':4, 'B':1, 'a': 2 } 1. key를 기준으로 오름차순 정렬 딕셔너리에 .item() 을 해주면, 각 key, value가 들어있는 tuple 리스트로 변한다. dict_ex = { 'b':5, 'c':4, 'B':1, 'a': 2 } print(dict_ex.items()) sorted()에 인자로 위에서 구한 튜플(dict_ex.items())을 전달하여 주면 오름차순으로 정렬된다. sorted_dict = sorted(dict_ex.items()) print(sorted_dict) 참고로 items를 이용하지 않고,.. 2023. 1. 24.

티스토리툴바