dotdotdot

현실 세계에서 우리는 종종 어떤 출발지에서 목적지까지 가장 빠른 길, 가장 저렴한 경로, 혹은 가장 짧은 통신 경로를 찾아야 할 때가 있다. 이런 문제들은 그래프라는 수학적 구조로 표현할 수 있다. 그래프는 정점(노드)과 간선(정점 간 연결선)으로 구성되며, 간선은 이동에 필요한 비용, 거리, 시간 같은 가중치를 가진다. 그래프는 유방향(방향이 있는 간선)일 수도 있고, 무방향(양쪽으로 이동 가능한 간선)일 수도 있다. 다익스트라 알고리즘은 둘 모두에 적용할 수 있으며, 무방향 그래프에서는 각 간선을 양 방향 모두 등록해야 한다. 예를 들어, \( u \)와 \( v \) 사이에 간선이 있다면, \( u \to v \), \( v \to u \) 모두 추가해주어야 다익스트라 알고리즘이 정상 동작한다.문제..

우리가 알고리즘을 공부하면서 마주치는 수많은 문제들 — 예를 들면 미로 탈출, 경로 찾기, 친구 관계 분석, 조직도 순회 등 —은 겉보기에는 다양해 보이지만 결국 "대상들 간의 연결 관계를 어떻게 탐색할 것인가"라는 문제로 귀결된다.이때 필요한 개념이 바로 그래프(Graph)다. 그래프는 노드(정점)과 간선(연결선)으로 이루어져 있으며, 정점은 어떤 대상(예: 도시, 사람, 웹페이지 등)을, 간선은 그들 사이의 관계(예: 도로, 친구 관계, 하이퍼링크 등)를 나타낸다. 그래프를 활용한 문제를 해결하려면, 그래프 자체를 어떤 방식으로 표현할 것인가가 먼저 결정되어야 한다.이를 위해 보통 그래프를 코드로 표현하는 두 가지 방식, 즉 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency ..

재귀란?재귀(Recursion)는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 알고리즘 기법이다. 보통 하나의 큰 문제를 동일한 구조를 가진 더 작은 하위 문제로 나누어 해결하는 방식으로, 수학적 귀납법과 유사한 방식으로 작동한다.재귀는 반복문처럼 루프를 돌며 문제를 해결할 수 있지만, 특히 트리 구조, 분할 정복, 백트래킹 등의 알고리즘에서는 반복문보다 재귀가 더 자연스럽고 간결한 표현되는 경우가 많다. 알고리즘 구조재귀 함수는 보통 두 가지 핵심 요소로 구성된다:기저 조건(Base Case)더 이상 재귀를 진행하지 않고 함수를 종료시키는 조건이다. 반드시 필요하며, 없을 경우 무한히 자기 자신을 호출하게 되어 스택 오버플로우(Stack Overflow) 가 발생한다.재귀 호출(Recursiv..

에라토스테네스의 체소수(prime number)란?1과 자기 자신을 제외한 다른 어떤 수로도 나누어지지 않는 자연수이다. 예를 들어, 2, 3, 5, 7, 11 등은 소수이다. 일반적으로 소수를 판별하는 방법 중 하나는 특정 수가 소수인지 하나씩 확인하는 O(√N) 방식이다. 예를 들어, 어떤 수 xxx가 소수인지 판별하려면 1부터 xxx까지 모든 수를 나누어보는 대신, √x까지만 확인하면 충분하므로 O(√N)의 시간 복잡도를 갖는다.하지만 N까지의 모든 소수를 찾을 때 이 방식을 그대로 적용하면, 각 숫자마다 O(√N) 연산을 수행해야 하므로 전체적으로 O(N√N)의 시간 복잡도가 발생한다.이 때문에 여러 개의 소수를 한 번에 찾기에는 비효율적이며, 보다 빠르게 소수를 구하기 위해 에라토스테네스의 체 ..