안녕하세요! Zedd입니다 :)오늘은 UHC(Undirected Hamiltonian Cycle)는 NP-Complete인 것을 증명해볼려고 해요 XD Hamiltonian Cycle(이하 헤밀토니안 사이클)문제는 글에서 소개했었죠? 헤밀토니안 사이클이 뭔지 모르시는 분들은 읽고와주세요 :)이 글 역시 P, NP, NP-Hard, NP-Complete에 대한 개념이 없으면 전혀 이해를 하지 못하실거에요 :(P, NP : NP-Hard, NP-Complete : 그럼 시작할게요! Undirected Hamiltonian Cycle은 NP-Complete이다. 주어진 그래프에서 출발점과 종료점만 두 번 나타나는 것을 제외하고는 정점이 한 번씩만 나타나는 사이클을 해밀턴 사이클 (Hamiltonian cycl..
안녕하세요 :) Zedd입니다. 에서, NP-Hard의 정의는"NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다." 라고 말씀드렸어요. 근데, 인터넷에 NP-Hard의 정의를 찾아보시면 이런글들이 엄청나게 많습니다. 저도!!! 저 글에 이렇게 써놨었어요. 이렇게요. 근데..오늘 지하철을 타면서 문득 "NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다."이거랑,"NP-Hard는 어떤 Certificate를 주더라도 그것을 다항시간에 대답할 수 없다."이거랑 뭔상관이지???라는 궁금증이 들었습니다... 솔직히 서로 하나도 상관없잖아요. 근데 둘다 NP-..
안녕하세요 :) 주말 잘 보내시고 계신가요 ㅎㅎ?비도 오고 그래서 뭔가 코딩하기 싫은...날이라서 계속 쓰자고 쓰자고 마음먹었던 NP-Hardness의 3탄!!!!바로 TSP(Traveling Salesman Problem)는 NP-Complete라는 것을 증명하는 글을 써보려고 해요 :) 아직 P, NP의 개념을 모르시는 분들은 .NP-Hard, NP-Complete의 개념을 모르시는 분들은 를 읽고와주세요.이제부터 말할 개념들은 위 두 글을 읽고오지 않으면, 이해가 전혀 되지 않을거에요 ㅠㅠ제 글이 아니더라도, P, NP, NP-Hard, NP-Complete의 개념에 대해서 공부하고 이 글을 봐주세요 :) 시작할게요! TSP(Traveling Salesma..
- SwiftUI
- 스위프트
- WidgetKit
- swift3
- fastlane
- WWDC
- FLUTTER
- Combine
- IOS
- 스위프트 문법
- np-hard
- Git
- ios 13
- Xcode
- WKWebView
- Swift
- 제이슨 파싱
- swift 공부
- swift tutorial
- Accessibility
- UIBezierPath
- actor
- 피아노
- 회고
- swift sort
- iOS delegate
- swift array
- github
- swift delegate
- np-complete
- Total
- Today
- Yesterday