Algorithm

코딩테스트, 각종 연습문제의 단골개념인 BFS, DFS에 대해서 다뤄보자🏃‍♀️BFS, DFS 모두 정점(node)과 그 정점들을 연결하는 간선(edge)로 이루어진 그래프를 탐색할때 사용하는 방법이다. (그래프를 탐색한다는 것은 한 정점으로부터 시작해서 모든 정점

알고리즘 문제를 풀다보면 조합과 순열을 활용해서 푸는 문제가 정말정말정말 많이 나온다. 나도 문제 풀때마다 정리해둔 순열과 조합 코드를 보면서 문제에 맞게 고치는 방식으로 풀고 있는데, 그 코드를 세세하게 정리 해보려고 한다. (조합과 순열의 정의, 이론보단 코드에 집

탐색 관련 문제를 처음 접하게 되면 for문을 이용하여 모든 값을 다 확인하여 원하는 값을 찾아내는 정말 간단하지만 효율성은 0인 방법을 사용하게 된다.하지만 그 이후로 효율성의 중요성을 느끼고 찾게 되는 탐색 알고리즘이 바로 이진 탐색 (Binary Search) 알

LeetCode 문제를 풀다가 배열에서 최대 합을 가지는 연속된 부분배열을 구하는 문제를 풀게 되었는데 처음엔 Brute Force 방법으로 for문을 중첩하여 풀어보려다가 최대 부분합 문제에는 Kadane's Algorithm (카데인 알고리즘)을 사용한다는 글을 보고 알고리즘을 찾아보았고 이해하기 쉽게 정리해보자🏃‍♂️ 카데인 알고리즘 (Kadane...

Union-Find 알고리즘은 간단하게 말하면 서로소 집합 (서로 중복되지 않고 공통 원소가 없는 부분 집합)을 표현할 때 사용하는 알고리즘이다. 주로 크루스칼 알고리즘 (Kruskal Algorithm)과 함께 사용된다. Union-Find 알고리즘이란 위에서 말했던

크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고

하나의 정점을 출발점으로 지정하여 모든 정점까지의 최단 거리를 구하는 다익스트라 알고리즘,모든 정점들을 출발점으로 지정하여 모든 정점까지의 최단 거리를 구하는 플로이드 와샬 알고리즘이 최단 거리를 구할때 주로 쓰이는 알고리즘이다.오늘은 이 둘중에서 플로이드 와샬 알고리

일차원 배열이 주어졌을 때 연속된 구간의 합이 M이 되도록 하는 경우의 수를 구하는 문제가 주어진다면 가장 먼저 생각 하는 방법은 바로 이중 for문을 이용하는 방법이다.위와 같은 방법으로 이중 for문을 이용하면 시간 복잡도가 $O(N^2)$ 이므로 배열의 크기가 커

Bubble Sort (거품 정렬)란 서로 인접한 두 수를 비교하여 더 큰 수를 뒤로 보내서 전체 배열을 오름차순으로 정렬하는 정렬 알고리즘 중 가장 간단한 정렬 알고리즘이다.

Insertion Sort(삽입 정렬)란 배열의 두번째 값 부터 시작하여 그 왼쪽의 값들과 비교하여 삽입할 위치를 결정하는 정렬 알고리즘이다.