아리의 개발 일상

Two Pointer 알고리즘 (투 포인터 알고리즘)개념투 포인터 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 효율적으로 목표(문제)를 해결하는 기법으로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾을 때 사용하면 시간 복잡도를 줄이는 매우 좋다.로직두 개의 포인터를 사용하여 배열을 탐색보통 하나를 왼쪽(배열 인덱스0)에서 시작, 다른 하나는  오른쪽에서 시작하여  특정 조건을 만족하는 경우를 찾는다.문제 유형에따라 오른쪽 시작 지점이 0부터 시작할 수도 있고 배열 인덱스의 최대치에서부터 시작할 수 있다.대표 유형두 수 의 합배열이 정렬된 상태에서 투 포인터를 사용하여 두 수의 합이 특정 값이 되는지 찾는 문제로직왼쪽 인덱스 left를 0으로, 오른쪽 인덱스 right를 배열의 끝으로 설정..

다익스트라 (Dijkstra) 알고리즘최단거리 구하는 알고리즘하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있다.가중치 방향 그래프 가 주어질때 사용가능하며 만약가장 짧은 경로를 찾을때 사용 가치가 없다면 bfs 사용해서 풀수 있다.알고리즘 개요출반노드설정최단거리 테이블 초기화방문하지 않는 노드중 최단거리 가장짧은거해당 노드를 거처가는 비용 계산후 테이블 갱신3,4, 과정 반복 이때 코드를 작성할때 우선순위 큐를 사용하는데 사용하는 이유는 우선순위 큐로 인해서 가장 짧은 경로를 가진 노드를 빠르게 찾을수 있어 시간 복잡도가 줄어들기 때문이다. 우선순위큐를 사용하지 않은 코드n,m=map(int,input().split()) #노드간선정보start=int(input()) # 시작노드graph = [..

[파이썬 알고리즘] 플로이드 워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘이란?모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 정점수만큼 반복하는 거와 같은 결과값을 가지지만시간복잡도가 O(n³) 이기에 정점의 수가 적을때에는 다이스트라 알고리즘보다 빠른 결과값을 받을 수 있다. 알고리즘 동작 과정비용 테이블 초기화:모든 정점 간의 최단 거리 정보를 담는 테이블을 생성합니다. 처음에는 무한대(inf)로 설정하여, 아직 연결되지 않은 상태를 나타냅니다.간선 정보 입력:간선 정보를 입력받아, 두 정점 사이의 거리를 그래프 테이블에 입력합니다. 간선 정보는 (a, b, c) 형식으로, a에서 b로 가는 거리가 c라는 뜻입니다.자기 자신으로 가는 거리는 0으로 설정:..