공부/알고리즘2 [백트래킹] N-Queen문제 백트래킹이란? 해를 찾기 위해 DFS방식으로 탐색하다가 해당 루트가 유망한지(Promising) 검사하여 조건이 맞지 않다면 가지치기(Pruning)하고 다른 루트로 돌아가 최적의 해를 찾는 방법이다. 상태 공간 트리(State Space Tree) 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이다. N-Queen문제 대표적인 백트레킹 문제이다. 백준 9663번 문제: https://www.acmicpc.net/problem/9663 n = int(input()) row = [250] * n answer = 0 #현재 레벨에서 놓을 수 있는지 없는지 체크하는 함수 (행[자동 생략], 열, 대각선) def can(level): for i in range(level): if row[level] =.. 2021. 12. 28. [알고리즘] 외판원 문제 (TSP; Traveling Sales-man Problem) 외판원 문제란? 외판원이 n개 도시로 판매출장을 계획하고 있다고 가정하고, 각 도시마다 다른 도시로 이어지는 도로가 연결되어 있다. 출장시간을 최소로 줄이기 위해 외판원이 거주하고 있는 도시에서 출발하여 각 도시를 한번씩 방문하고, 다시 출발한 도시로 돌아오는 가장 짧은 여행길을 찾는 문제이다. 이 문제는 마디(Vertex, node)를 도시로 하여 가중치 포함 그래프로 표현할 수 있다.(가중치는 양의 정수로 가정) 방향 그래프에서 일주여행길은 한 도시에서 출발하여 다른 모든 도시를 한번씩만 들리고 출발한 도시로 돌아오는 여행길이다. (이를 헤밀톤 회로 라고도 한다.) 외판원 문제는 최소한 하나의 일주여행길이 존재하는 경우 가중치 포함 방향그래프에서 최적일주여행길을 찾는 문제이다. 출발도시가 어디 부터인.. 2021. 12. 17. 이전 1 다음
