ZeddiOS

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

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