Algorithm

가장 단순하지만 강력한 문제 해결 방법이다.'탐욕법'이라고 불리기도 한다.현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다!다익스트라, 플로이드 워셜 알고리즘은 엄밀히 말하자면 그리디 알고리즘으로 분류

나의 생각을 컴퓨터의 소스코드로 바꾸는 과정이다.코딩 테스트를 풀기 위해서 소스코드를 작성하는 과정은 필수 -> 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.생각해낸 문제 해결 방법을 내가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답

백트래킹이란 무엇일까? 영어로 해석하면 '뒤로 추적한다?'로 해석이 된다. 저는 백트래킹이라고 하면 '아 DFS로 풀면 되겠구나'라고만 생각했었지 개념에 대해 자세히 알고있거나 정리한 적이 없었다... 그래서 이번 기회에 포스팅을 해보려 한다!위키백과 정의에 따르면 백

DFS

Disjoint-Set을 구현할 때 사용하는 알고리즘.집합을 구현하는데 비트 벡터, 배열, 연결리스트를 사용할 수 있으나, 가장 효율적인 트리 구조를 이용하여 구현함.크루스칼 알고리즘에서 그래프의 최소 신장 트리(MST)를 찾는데 활용된다. (정점 연결 및 사이클 형성

신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다.크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼

현실에서 우리가 컴퓨터를 이용하여 문제를 해결하려 할 때 컴퓨터로도 해결하기 어려운 문제들이 있을 것이다. 보통 최적의 해를 구하는데 시간이 매우 오래걸리거나 메모리 공간이 많이 필요한 문제 등이 해결하기 어려운 문제들이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. ('길 찾기 문제' 라고도 불린다.) 최단 경로 알고리즘 유형에는 다양한 종류가 있다. 대표적으로 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘, 이렇게 3가지이다. 그중 다익스

지난 포스팅에서는 다익스트라 알고리즘에 대해 작성했었다. 다익스트라의 경우 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에는 어떻게 해야할까? 바로 플로이드 워셜 알고리즘

정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다.예시를 통해 확실하게 이해

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다.일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다. (정렬 알고리즘은 이진 탐색의 전처리 과정이기도

이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는

벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?