👾

이진 탐색 💡 아이디어 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색해보자!! ⭐단, 배열 내 데이터는 이미 정렬되어 있어야 한다.⭐ 💡 알고리즘 설명 탐색하고자 하는 범위(start, end)를 정한다. start와 end 사이 mid를 정한다. mid의 데이터와 찾으려는 데이터를 비교한다. 1) 같을 경우 - 탐색을 종료한다. 2) 중간점의 데이터가 더 클 경우 - end를 (mid - 1)로 설정해 mid의 왼쪽을 탐색한다. 3) 중간점의 데이터가 더 작을 경우 - start를 (mid + 1)로 설정해 mid의 오른쪽을 탐색한다. start와 end 사이에 데이터가 존재하는 동안 2~3의 과정을 반복한다. 💡 소스 코드 다음은 array 내의 target의 인덱스를 찾아서 반환하는 함수이다...

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 또한 프로그램에서 데이터를 가공할 때 어떤 식으로든 정렬해서 사용하는 경우가 많기 때문에 정렬 알고리즘은 프로그램 작성 시 가장 많이 사용되는 알고리즘 중 하나이다. 선택 정렬(Selection Sort) 💡 아이디어 데이터가 무작위로 여러 개 있을 때, 그중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복해보자 => 매번 가장 작은 것을 선택한다 💡 소스코드 def sel_sort(array): for i in range(len(array)):..

목차 다익스트라 알고리즘 소개 알고리즘 동작 과정 알고리즘 구현(파이썬) 다익스트라(Dijkstra) 최단 경로 알고리즘 특정 정점에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 Single-Source Shortest Paths 문제에 사용될 수 있음 매 상황에서 가장 비용이 적은 노드 선택을 반복(그리디 알고리즘) 알고리즘 동작 과정 출발 정점 선택 최단 거리 테이블을 INF로 초기화 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점 선택 해당 정점을 거쳐 다른 정점으로 가는 비용을 계산하여 최단 거리 테이블 갱신 3~4번 과정 반복 알고리즘 구현 방문하지 않은 정점 중에 최단 거리가 가장 짧은 정점을 빠르게 찾기 위해 우선순위 큐 사용 import heapq import sys input..

목차 BFS의 개념 BFS의 장단점 BFS의 시간 복잡도 BFS의 구현 BFS(너비 우선 탐색)이란? BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄 BFS의 동작 과정 탐색 시작 정점을 큐에 삽입하고 방문 처리를 합니다. 큐에서 정점을 꺼낸 뒤에 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리를 합니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. BFS의 장단점 장점 시작 정점에서 목표 정점까지의 최단 길이 경로를 보장한다. 단점 경로가 매우 길 경우, 탐색 가지가 급격히 증가함에 따라 많은 기억 공..

목차 DFS의 개념 DFS의 장단점 DFS의 시간 복잡도 DFS의 구현 DFS(깊이 우선 탐색)이란? DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수를 이용함 DFS의 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 존재하면 그 노드를 스택에 넣고 방문 처리를 합니다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼냅니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. DFS의 장단점 장점 현재 경로 상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 답을 빨리..

목차 Greedy 알고리즘 개념 Greedy 알고리즘 예시 Greedy 알고리즘 다른 문제들 그리디(Greedy) 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법 즉, 전후 결정에 관계없이 당시 "가장 최고"라고 생각되는 것을 선택해서 최적의 해를 구하는 방법 대표적인 예시로 MST(최소신장트리) 알고리즘, 다익스트라(Dijkstra) 알고리즘, 거스름돈 문제가 있다 그리디 알고리즘 쉬운 예시 점원이 계산을 마치고 거스름돈을 돌려주는 상황을 생각해봅시다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 충분히 많이 존재한다고 가정합니다. 손님에게 N원을 거슬러 줘야 할 때, 최소 개의 동전으로 거스름 돈을 줄 방법을 구하세요. 단, 거슬러 줘야 할 돈 N은 항상..

목차 Spanning Tree 개념 MST(최소 신장 트리) 개념 Prim's Algorithm Kruskal's Algorithm Spanning Tree (신장 트리) 그래프 내의 모든 정점들을 포함하는 그래프의 부분집합(subgraph) Tree 최소한의 간선들로 그래프 내의 모든 정점을 포함 - 따라서 Spanning Tree는 cycle을 포함하지 않음 - 그래프 내의 정점의 수가 n개이면, Spanning Tree는 (n-1) 개의 간선을 가짐 한 그래프 내의 여러 개의 Spanning Tree가 있을 수 있음 MST (Minimum Spanning Tree, 최소 신장 트리) 가중치가 있는 그래프(weighted graph)에서 최소 가중치를 가진 Spanning Tree 즉, 한 그래프 내..