본문 바로가기 메뉴 바로가기

ZeddiOS

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

ZeddiOS

검색하기 폼
  • 전체 보기 (841)
    • iOS (278)
    • Swift (126)
      • Concurrency (9)
    • SwiftUI (26)
    • Combine (17)
    • watchOS (2)
    • iPadOS (2)
    • Xcode (3)
      • Xcode Cloud (2)
    • Flutter (12)
    • 공부 (205)
    • 피아노 (39)
    • 요리 (2)
    • 시 (25)
    • 일상 (91)
  • 방명록

np-hard (5)
Undirected Hamiltonian Cycle은 NP-Complete이다.

안녕하세요! 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..

공부 2017. 8. 23. 21:45
NP-Hard의 잘못된 정의

안녕하세요 :) Zedd입니다. 에서, NP-Hard의 정의는"NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다." 라고 말씀드렸어요. 근데, 인터넷에 NP-Hard의 정의를 찾아보시면 이런글들이 엄청나게 많습니다. 저도!!! 저 글에 이렇게 써놨었어요. 이렇게요. 근데..오늘 지하철을 타면서 문득 "NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다."이거랑,"NP-Hard는 어떤 Certificate를 주더라도 그것을 다항시간에 대답할 수 없다."이거랑 뭔상관이지???라는 궁금증이 들었습니다... 솔직히 서로 하나도 상관없잖아요. 근데 둘다 NP-..

공부 2017. 8. 21. 22:48
TSP는 NP-Complete.

안녕하세요 :) 주말 잘 보내시고 계신가요 ㅎㅎ?비도 오고 그래서 뭔가 코딩하기 싫은...날이라서 계속 쓰자고 쓰자고 마음먹었던 NP-Hardness의 3탄!!!!바로 TSP(Traveling Salesman Problem)는 NP-Complete라는 것을 증명하는 글을 써보려고 해요 :) 아직 P, NP의 개념을 모르시는 분들은 .NP-Hard, NP-Complete의 개념을 모르시는 분들은 를 읽고와주세요.이제부터 말할 개념들은 위 두 글을 읽고오지 않으면, 이해가 전혀 되지 않을거에요 ㅠㅠ제 글이 아니더라도, P, NP, NP-Hard, NP-Complete의 개념에 대해서 공부하고 이 글을 봐주세요 :) 시작할게요! TSP(Traveling Salesma..

공부 2017. 8. 20. 12:43
NP-Hard, NP-Complete

ㅎㅎ 안녕하세요 :)이전글에서 P와 NP의 개념에 대해서 아주 길게.. 설명드렸는데...조금 이해가 가셨나요 ㅠㅠ? 궁금한점이 있다면 댓글이나 채널서비스를 이용해서 바로 질문해주세요!! 오늘은 NP-Hard와 NP-Complete에 대해서 설명드릴려고 해요.무서워하지마세요!!!우리는 그냥 얘네가 어떤건지~~ 그냥 살짝만 알아볼거에요.(과연;) 근데 정말 잘 읽으셔야 합니다. 헷갈리시면 안돼요. 특히 NP와 NP-Hard...자. NP-Hard가봅시다. NP-Hard NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다. 엥;;;;....reducible..?;;"축소시킬 수있는"..?...;;; 이게 무슨뜻일까요?;; 지금!! 몰라도 괜찮습니다. 제가..

공부 2017. 6. 22. 17:32
P와 NP의 개념

안녕하세요 ㅎ_ㅎ종강을 했습니다..드디어XD이번학기에는 알고리즘을 들었었는데요, 그 중에 꼭!! 쓰고싶은 주제가 있어서 까먹기 전에 얼른 쓰려고..엄청 길어질듯한 느낌.. 그 주제는 바로!! NP-Complete Problems입니다.정말 이 주제를 배울 수 있어서 너무너무 재밌었어요XD 이 챕터에서 P, NP, NP-Hard, NP-Complete에 대해서 배웠어요.하나하나 순서대로 알아봅시다. 최대한 쉽게 설명할게요! Polynomial Time : Class P 클래스 P란 간단합니다.어떤 문제에대해서 Polynomial Time Algorithm이 존재하면 그 문제는 클래스 P에 속합니다.(그 알고리즘이 클래스 P에 속하는 것이 아닌, 문제가 속한다는 것에 헷갈리시면 안됩니다.) Polynomia..

공부 2017. 6. 21. 11:00
이전 1 다음
이전 다음
TAG
  • github
  • iOS delegate
  • UIBezierPath
  • fastlane
  • Git
  • Combine
  • swift tutorial
  • WidgetKit
  • WWDC
  • WKWebView
  • Swift
  • 피아노
  • swift delegate
  • SwiftUI
  • swift sort
  • 스위프트
  • swift3
  • ios 13
  • np-complete
  • FLUTTER
  • swift 공부
  • 스위프트 문법
  • IOS
  • np-hard
  • swift array
  • 제이슨 파싱
  • 회고
  • Xcode
  • actor
  • Accessibility
more
글 보관함
Total
Today
Yesterday

Blog is powered by Tistory / Designed by Tistory

티스토리툴바