알고리즘 개념

(이미지 출처 : https://mathmonks.com/binary-operation) 이항 연산(Binary Operation) 두 개의 원소를 이용해 하나의 원소를 만들어내는 것이 이항 연산(Binary Operation) 입니다. 닫힘(Closure) 같은 집합에 속한 두 수의 이항 연산 결과가 항상 같은 집합에 속하는 것. 닫힌 이항 연산은...

그리디 알고리즘이란? 최적의 값을 구해야하는 상황에서 사용되는 근시안적인 방법론 "각 단계에서 최적이라고 생각되는 것을 선택"후 나가는 방식으로 진행하며 "각 단계에서 최선의 선택을 한 것이 전체적으로 최선이길 바라는 알고리즘" 입니다. 다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데, DP가 하위 문제에 대한 최적의 솔루...

정의 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하...

깊이 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 넓게(wide)...

넓이 우선 탐색(BFS)이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 ...