📌 개념 다지기 이분 탐색 탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다. 두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편이다. ✔️탐색하는 방법 배열이 정렬(sort
다이스트라(Dijkstra) : 하나의 점에서 출발했을 때 다른 모든 정점으로의 최단 경로(최소비용)를 구하는 알고리즘. 플로이드 와샬 : 모든 정점에서 모든 정점으로의 최단 경로(최소비용)를 구하고 싶을 때 사용한다.거쳐가는 정점을 기준으로 최단 거리를 구하는 것문
깊이 우선 탐색(DFS)으로 그래프를 탐색해보자.하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다.특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다.DFS는 탐색에서 깊은 것
너비 우선 탐색 (BFS)으로 그래프를 탐색해보자.하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다.특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다.BFS는 그래프에서 넓게
많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다.어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다.어떤 원소가 속한 집합을 대표하는 원소를 반환하는데, 이를 위해 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같
소수 찾기는 간단하게 구현하면 쉽지만, 시간 복잡도를 줄이기 위해서는 에라토스테네스의 체를 사용해야한다. 소수를 찾는 문제는 간단하지만 라이브코딩으로 출제될 수 있으므로 알아두면 좋다.참고 : 위키백과에라토스테네스의 체는 소수를 찾는데 사용된다.2부터 소수를 구하고자
알고리즘 공부를 하다보면 백트래킹이라는 개념이 나온다. 문제의 효율성을 높이기 위해서 백트래킹 기법을 사용하여 탐색을 진행해야한다. 왜 백트래킹을 사용하면 효율성을 높일 수 있는지 백트래킹 예제를 보며 공부해보고자 한다.모든 조합의 수를 살펴보는 것인데, 단 조건이 만