# NP-hard
백준 7579번 앱
백준 7579번 링크NP hard 문제이다. Optimization version의 정의는 다음과 같다.Input: Positive integers $$W, w{1}, ... , w{n}$$ and $$v{1}, ... , v{n}$$Output: A subset S
[BOJ] 2098 외판원 순회
2098\. 외판원 순회 문제 링크문제 풀이 코드 링크하...도저히 설명없이는 풀 수 없었던 문제... 구글링을 열심히 했다. 시간 제한이 되게 빡빡해서, 생각조차 못한 부분을 수정해야했다.일반적인 외판원 순회(Traveling Salesman problem) 문제이다
회고
KBO가 수립한 계획이 너무 훌륭해서 할까말까 고민을 많이 했는데 해보기를 잘했다는 생각이 듭니다.확실히 말씀드릴 수 있을 것 같습니다. 구단 별로 총 통행거리를 보더라도, 변동계수가 0.04라는 정말 좋은 결과가 나왔습니다. 또한 주말 및 휴일 배정도 12~15건으로
2022 KBO 일정을 세워보자(3)
AI Constraints Solver인 Optaplanner를 활용하여 계획을 수립하였습니다. 이론적 배경, 메타 휴리스틱 알고리즘 소개, Optaplanner에 대한 소개, Optaplanner를 활용한 개발 과정은 다음 글에서 상세하게 공유하겠습니다. 정석대로라면
2022 KBO 일정을 세워보자(2)
우리는 지금까지 목적함수를 정의하였습니다. 그렇다면 우리가 정의한 목적 함수 기준으로 KBO가 수립한 2022년 일정은 몇 점일까요? 계산해 본 결과 아래와 같습니다. \- 모든 제약 조건에 대해 준수함 : 0 scoreKBO가 수립한 2022년 일정에 대한
2022 KBO 일정을 세워보자(1)
이제 본격적으로 2022년 프로야구 일정을 세워보도록 하겠습니다.우리가 원하는 것은 실현 가능한 각 구단별로 총 통행거리와 주말 및 휴일 배정 건수가 공정한 계획을 원합니다. 그러나 컴퓨터가 이를 어떻게 판단할 수 있을까요? 따라서 생성된 계획을 어떻게 평가할지를 생각
얼마나 복잡한 문제인가?
현재 KBO 리그는 10개 팀으로 운영되고 있습니다. 그렇다면 한 경기에서 나올 수 있는 경우의 수는 어떻게 될까요?10개 팀에서 2개 팀을 고르는 경우의 수는 90($${10}{9}$$)개 입니다. (10개에서 2개를 고르는 조합이 아닌 순열 의 개수입니다.) 그러면
드디어 시작하다.
올해 초에 기술블로그를 만들어야겠다고 다짐은 했지만 어디서부터 시작을 해야 할지 결정을 내리지 못하고 있었습니다. 어떻게는 이번 설 연휴 전에는 무언가 행동을 취해야 한다고 결심했지만 딱 이거다 하고 싶은 것이 없었습니다. 후보는 많았지만 모든 사람들의 관심을 가질 수
NP 난해 (NP-hard)
출처 - 위키NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이다. 다시 말하면, NP-난해는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다.NP-난해 집합에 속하는 문제가 NP에도 속하면 NP-완전에