나홀로 프로그래밍 공부하기

문제 출처 : algospot.com :: RESTORE algospot.com :: RESTORE 실험 데이터 복구하기 문제 정보 문제 토요일에 출근해서 연구실에서 놀고 있던 대학원생 진호는 실수로 실험에 사용하던 데이터를 삭제하고 말았습니다. 복사본도 없는 터라 이대로라면 교수 algospot.com 1. 문제 분석 (1) 답의 구조 파악하기 1) 예제에서 답의 구조 확인하기 3번째 예제 입력에서 부분 문자열 조각 [ abrac, cadabra, dabr ]을 이용하여 만들 수 있는 문자열 중 가장 짧은 문자열은 cadabrac이다. 두 조각 abrac과 cadabra에서 abra가 일치하는 것을 알 수 있다. 부분 문자열 조각 dabr는 cadabra의 일부인 것을 알 수 있다. 2) 정리하기 어떤..

문제 출처 : algospot.com :: TSP2 algospot.com :: TSP2 Traveling Salesman Problem 2 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 algospot.com 1. 함수의 정의 바꾸기 6.7 단원(6.7 예제 : 최적화 문제 - 여행하는 외판원 문제(Python) (tistory.com))에서 완전 탐색 알고리즘을 통해 이 문제를 해결한 전력이 있다. 전에는 n개의 도시들에 대해 n!개의 경로를 모두 생성하는 방법을 사용했는데, n이 15만 되더라도 계산이 불가능할 지경이다. 또한, sh..