NP Hard

🎅흥미로운 주제 발견

Dacon에서 흥미로운 주제로 대회를 열었길래, 이번에 참여해보기로 했다.
대회링크
대회 이름은 산타 배송 경로 최적화

내용을 간단히 설명하자면

(0,0) 에 위치한 산타가 (100,100) 좌표 위의 모든 마을에 선물을 전달할 수 있는 최단경로 마을 방문순서 구하기!
⚠️ 🦌가 힘들기 때문에 한번에 선물 25개만 실을 수 있고, 한번 방문한 마을은 다시 방문할 수 없음.
⚠️ 점수는 참가자가 도출한 배달 순서를 기반으로 유클리드 거리를 계산하여 산정

TSP 알고리즘이 카테고리로 설정되어 있었다.
외판원 알고리즘이라고 예전에 코테 스터디할 때 잠깐 들었던 기억이 있긴한데,
당시에 너무 어려웠어서 그냥 패스했었다. 자랑스럽다.

그래서 대회에 본격적으로 참여하기 앞서 여러 개념들을 공부해보려고 한당.

이번 주제는 NP-Hard ~
뭔진 몰라도 상당히 Hard 한 기운이 느껴진다.

NP-Hard

NP-Hard의 정의

NP-Hard(Non-deterministic Polynomial-time Hard)는 계산 복잡도 이론에서 아주 어려운 문제의 집합

NP-Hard 문제의 특징

1. 해결하는 데 시간이 매우 오래 걸림(기존의 알고리즘으로는 다항 시간 안에 해결 불가능).
2. 문제의 해가 주어졌을 때, 그것이 맞는지 확인하는 것도 시간이 오래 걸림.
3. NP 문제보다도 더 어려운 문제를 포함.

TSP(Traveling Salesman Problem)는 NP-Hard 문제 중 하나이다.
도시 수가 많아질수록 가능한 경로 수가 기하급수적으로 증가하기 때문에 빠르게 최적해를 찾는 것이 어렵다고 한당.

쉽게 이해하는 NP-Hard

1️⃣ P(Polynomial-time):
문제를 해결하는 데 필요한 시간이 다항 시간 내에 가능

• 덧셈, 뺄셈, 정렬 등.

2️⃣ NP(Non-deterministic Polynomial-time):
문제를 해결하는 데 시간이 오래 걸릴 수 있지만, 해가 주어졌을 때, 그것이 맞는지 검증하는 것은 다항 시간 내에 가능

• Sudoku 퍼즐: 문제를 푸는 데 시간이 오래 걸리지만, 정답이 주어졌을 때 검증하는 것은 빠름

3️⃣ NP-Hard:

• P 문제와 NP 문제를 모두 포함하는 더 어려운 문제
• 어떤 알고리즘을 사용하더라도 일반적으로 빠른 해결책을 찾기 어렵
• NP-Hard 문제를 해결할 수 있는 알고리즘이 있다면, 모든 NP 문제를 해결 가능

TSP가 NP-Hard인 이유

TSP의 핵심은 모든 도시를 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 경로를 찾는 문제이다.
그러므로 도시 수가 증가할수록 가능한 경로 수가 기하급수적으로 증가하게 된다.

가능한 경로 수:

• 도시가 ( n )개일 때, 가능한 경로 수는 ((n-1)!) 즉, 시간복잡도가 n! 이 된다.

예시로 도시 수를 증가시켜 보면:

이처럼, 도시 수가 많아지면 가능한 경로 수가 기하급수적으로 증가하기 때문에, 현실적으로 모든 경로를 탐색하여 최적 경로를 찾는 것은 힘들어보인다.

그럼 NP-Hard 문제는 우찌 해결하나여

NP-Hard 문제를 해결하기 위해 완벽한 최적해를 찾기보다 근사해(Approximate Solution)를 찾는 알고리즘을 사용한다고 한다.

몇 가지 대표적인 알고리즘:

쉽게 이해하는 TSP와 NP-Hard

🔧 TSP가 어려운 이유

• 도시가 많아질수록 가능한 경로 수가 급격히 증가하기 때문
• 단순히 가능한 모든 경로를 탐색하는 것은 현실적으로 불가능

💡 그래도 해결은 해야지?

• 완벽한 최적해를 찾는 대신, 근사 알고리즘을 사용하여 빠르게 좋은 경로를 찾기

일상적인 NP-Hard 문제 예시

결론

그니까, 원래 알던 코드로 돌리면 한세월 걸릴테니 시간복잡도와 정답 모두 챙긴 코드가 필요하다는 뜻 같다.
어렵겠지만 그만큼 재밌을 것 같당.