에라토스테네스의 체. 이름이 조금 어려운 알고리즘입니다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 소수(Prime Number)를 찾는 알고리즘 중 하나인데요. 일반적으로 정수 n이 소수인지 확인할 때, for문을 돌리며 2~sqrt(n)으로 나누어 떨어지나 확인하는 방법이 있습니다. 하지만 특정 범위 내 여러 개의 수를 소수인지 판단해야 할 때, 각각 2~sqrt(n)으로 나누어 떨어지는지 확인하는 것은 조금 비효율적일 수 있습니다. 하지만, 처음에 범위 내 숫자들에 대해 소수인지 구해놓고 이후에 각 숫자들이 소수인지 확인한다면 더 빠르게 작동할 수 있습니다. 에라토스테네스의 체 에라토스테네스의 체의 원리를 그림으로 표현하자면 위 이미지와 같습니다. 2 ~ 120 범위 내 숫자들..

이분 매칭을 간단히 이야기하면 연애 매칭 프로그램입니다. 남과 여 두 그룹이 있고, 남 -> 여 혹은 여 -> 남으로 맘에 드는 이성을 골랐을 때, 커플이 가장 많이 매칭되는 경우를 찾는 것이지요. 좋은 예시가 없을까 하며 돌아다니다가, MIT 오픈 코스 유튜브에서 남과 여를 매칭하는 걸 예로 들길래 이거다! 하고 참고해서 포스팅해봤습니다. https://www.youtube.com/watch?v=HZLKDC9OSaQ&ab_channel=MITOpenCourseWare 이분 그래프 이분 그래프는 k분 그래프의 일종으로 k=2인 경우의 그래프입니다. k분 그래프는 아래와 같이 나타낼 수 있는데요. 집합 V(i), V(j) 가 있다고 했을 때 쉽게 말해서 간선의 양 끝은 서로 다른 그룹이여야 한다는 의미입니..

공간 복잡도 (Space Complexity) 시간 복잡도가 알고리즘의 연산횟수, 수행시간을 평가하는데 쓰이는 척도라면, 공간 복잡도는 알고리즘이 메모리를 얼마나 사용하는 지에 관한 척도입니다. 알고리즘을 설계할 때는 시간 복잡도와 공간 복잡도 모두 고려한 적절한 알고리즘을 설계 및 사용해야 합니다. 다만, 두 마리 토끼를 둘 다 잡을 수 없을 경우엔 공간 복잡도 보다는 시간 복잡도를 더 우선시하는 경향이 있습니다. 하드웨어의 발전 메모리 용량 자체가 커지기도 했고, 병렬 처리와 분산 컴퓨팅 역시 발전했습니다. 요즘 같은 대용량 데이터를 처리해야 하는 시대에는 처리 시간이 짧은 알고리즘이 중요하기 때문입니다. 그럼에도, 공간 복잡도는 중요한 개념입니다. 하드웨어가 얼마나 발전했던 간에, 메모리의 한계는 ..

알고리즘의 성능을 판단하는 데에는 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity) 등이 쓰입니다. 시간 복잡도는 알고리즘이 얼마나 빠르게 실행되는지, 공간 복잡도는 알고리즘이 얼마나 메모리를 잡아먹는지를 판단하는데 쓰입니다. 이번 편에서는 그 중에서도 시간 복잡도(Time Complexity)를 알아보겠습니다. 시간 복잡도 (Time Complexity) 시간 복잡도는 입력되는 데이터의 양에 따라 알고리즘의 수행 시간이나 연산 횟수가 어떻게 달라지는지를 분석하는데 쓰입니다. 알고리즘을 짤 때에는 문제를 해결하는 것도 좋지만, 알고리즘을 얼마나 효율적으로 짜는 것 역시 중요합니다. 같은 입력을 넣었을 때, 같은 출력을 갖는다 하더라도, 알고리즘에 따라 성능이 달라질..

그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다. 물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요. 깊이 우선 탐색 (DFS, Depth - First Search) DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다. 한 노드의 연결된 노드를 먼저 탐색한다는 의미죠. 해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다. 한 노드를 탐색할 때, 해당 노드와 연결된 ..

최소 스패닝 트리 / 최소 신장 트리 (MST, Minimun Spanning Tree) 스패닝 트리 / 신장 트리는 모든 정점(Vertex, Node)을 간선(Edge)로 사이클이 생기지 않게 연결한 그래프입니다. 최소 스패닝 트리 / 최소 신장 트리는 신장 트리 중에서도 간선의 총 비용이 최소가 되는 트리 입니다. 각 노드와 노드간의 간선이 위와 같이 주어졌습니다. 그럼, 이 위 그래프에서 모든 노드가 이어져 있으면서, 간선의 합이 최소가 되려면 어떤 간선을 선택해야 할까요? 빨간색으로 칠한 간선들을 선택한다면, 간선의 비용을 최소로 하면서 모든 노드를 연결할 수 있습니다. 위 형태가 해당 그래프의 최소 스패닝 트리가 됩니다. 물론, 그래프에 따라 비용이 최소가 되는 스패닝 트리는 여러개 있을 수 있..