알고리즘 문제의 복잡성에 대해 이야기할 때, P-NP, NP-완전, NP-난해와 같은 용어들이 등장하게 된다. 외판원 순회, 부분집합의 합과 같은 문제들에 대해 찾아볼 때 각 정보글마다 NP-완전이니, NP-난해니 말이 달라서 혼란이 있었다. 이에 대해 좀 더 조사해 보니, 그렇게 헷갈리게 된 원인이 파악되었다. 이 포스트에서는 P-NP의 개념과 함께 N…

컴퓨터 과학에서 정렬 알고리즘은 데이터를 효율적으로 정돈하는 핵심적인 작업이다. 이러한 알고리즘은 데이터의 크기와 유형에 관계없이 사용될 수 있으며, 다양한 응용 분야에서 중요한 역할을 맡는다. 버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보고, 각각 C언어와 Javascript로 나타내어 보았다. 버블 정렬(Bubble Sort) 버블 정렬은 주어진 …

여행하는 외판원 문제(TSP : Traveling Salesman Problem)는 모든 도시들을 단 한 번만 방문하고 원래 출발한 도시로 돌아오는 최단 경로를 알아내는 문제이다. 이번 포스트는 다음과 유사한 문제를 최근접 이웃 알고리즘(Nearest Neighbor Algorithm)을 통해 구현했던 프로젝트에 대해 다루었다. 여행하는 외판원 문제 어느…

온라인 저지, 알고리즘 대회 등에서 문제를 출제할 때 출제자의 의도에 맞는 효율적인 구조로 유도하기 위해 적절한 시간 제한을 두기 때문에, 알고리즘 설계 시 시간 복잡도를 고려하여 작성해야 한다. 알고리즘의 분석 기준 알고리즘의 성능을 분석하는 판단 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있다. 이러한 기준을 바탕으로 알고리즘을 …