728x90 공부/알고리즘31 Computational Complexity(계산 복잡도 이론) https://com24everyday.tistory.com/198 P, NP, NP-Hard, NP-Complete 이를 잘 설명해주시는 블로그를 찾았어요! 예시들이 굉장히 찰지고 머리에 쏙쏙 들어왔어요ㅎㅎ P, NP 설명 https://zeddios.tistory.com/92 P와 NP의 개념 안녕하세요 ㅎ_ㅎ 종강을 했습니다..드디어XD 이�� com24everyday.tistory.com Traveling Salesperson Problem exponential 보다 나은 시간 복잡도 없음 NP-Complete Intractability (아주 다루기 힘듦) "difficult to treat or work" - 효율적 알고리즘 없음 - 증명 안됨 - 자연에 있는 많은 최적화 문제 Tractabl.. 2020. 7. 1. P, NP, NP-Hard, NP-Complete 이를 잘 설명해주시는 블로그를 찾았어요! 예시들이 굉장히 찰지고 머리에 쏙쏙 들어왔어요ㅎㅎ P, NP 설명 https://zeddios.tistory.com/92 P와 NP의 개념 안녕하세요 ㅎ_ㅎ 종강을 했습니다..드디어XD 이번학기에는 알고리즘을 들었었는데요, 그 중에 꼭!! 쓰고싶은 주제가 있어서 까먹기 전에 얼른 쓰려고.. 엄청 길어질듯한 느낌.. 그 주제는 바로!! zeddios.tistory.com NP-Hard, NP-Complete 설명 https://zeddios.tistory.com/93 NP-Hard, NP-Complete ㅎㅎ 안녕하세요 :) 이전글에서 P와 NP의 개념에 대해서 아주 길게.. 설명드렸는데... 조금 이해가 가셨나요 ㅠㅠ? 궁금한점이 있다면 댓글이나 채널서비스를 이용.. 2020. 7. 1. 기말 Greedy_approach 정리 Greedy algorithm : Make a sequence of choices, each of which simply looks the best at the moment 선택들 중에서 그 순간 가장 좋아보이는 선택을 함. 대표적인 그리디 알고리즘의 예시는 '동전 고르기' . ex) 730 원을 채우기 위해 동전을 선택하자. Greedy approach vs Dynamic programming -최적화 문제를 푸는데 사용(Solve optimization problems) -그리디 알고리즘은 다이나믹 프로그래밍과 달리 문제를 작은 부분 문제로(sub-problems) 나뉘어지지 않음. 지역적 최적화 선택을 하면 재고려하지 않음 선택은 과거나 미래 선택에 영향을 미치지 않음 최적화인지는 증명해야함(pro.. 2020. 6. 24. Knapsack Problem(배낭 문제) 오늘은 배낭 문제(Knapsack Problem, 냅색 프라블럼) 에 대해 배워보겠습니다. 배낭 문제는 조합 최적화의 유명한 문제 입니다. :도둑이 다른 가치와 다른 무게가 있는 보석을 훔치는데 넣을 수 있는 무게가 정해진 가방에 최대한 많이 넣는 문제입니다. 이 배낭문제는 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem) 과 짐을 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem) 라 부릅니다. 저희 분할 가능 배낭문제를 그리디 관점에서 살펴보도록 하겠습니다. (다항시간에 풀 수 있습니다. 0-1 배낭문제는 DP로 풀 수 있습니다.) 훔친 물건 중에 가치가 가장 높은 거 부터 넣습니다. 그리디는 쉽게 생각할 수 있지만 항상.. 2020. 6. 21. 이전 1 2 3 4 5 ··· 8 다음 728x90
