알고리즘 9 P & NP 효율적인알고리즘이란-다차시간알고리즘 다차시간알고리즘 : 최악의 경우 시간복잡도의 상한이 입력크기의 다항식인 알고리즘.O(p(n)) 일 때, p(n) 이 다항식일 때.2n, 3n^3+4n…..2^n, n! 은 다항식이 아니다. = 다차시간알고리즘이 아니다. 다루기힘든문제 : 문제에 대해 다차시간 알고리즘을만드는 것이 불가능한 문제. 다루기힘든정도에따른분류분류1. 다차시간알고리즘이 발견된 문제분류1의 문제는 P집합.-합병정렬,퀵정렬,이진검색,쉬트라센(행렬곱)-연쇄행렬곱셈,최단경로구하기(플로이드),-다익스트라,프림,크루스컬 분류2. 다루기 힘들다고 증명된 문제분류2는 P, NP 어디에도 속하지 않음.-비다항식 크기의 결과를 요구하는 비현실적문제 = 모든 해밀토니안 회로 구하는 문제-요..
알고리즘 8 해싱 해싱의 장점. 속도가 매우 빠르고, 짧은 해시 키를 사용해 항목을 찾으면 원래의 값을 사용하여 찾는 것보다 더 빠르다. 2개이상의 키가 같은 해쉬값을 찾는 경우 충돌이 발생할 수 있음. 해결-> 같은 해쉬값을 갖는 키들을 bucket에 모아놓는다. 버킷은 연결리스트로 구현 한다." 각 Bucket을 가리키는 포인터 배열 Bucket[]을 만 당 Bucket의 연결 리스트를 가리키도록 한다.값 i 로 해시되는 키 값들은 모두 Bucket[i]가 가리키는 연 위치시킨다." 충돌해결법 : 오픈해싱버킷의 수가 키의 갯수와 같은 필요는 없지만,버킷의 수가 적다면 충돌은 필연적임.n개의키와m개의 버킷이 있고 키들이 버킷에 균일하게 분포 저장되어있다면. 각 버킷마다 n/m개의 키가 존재.평균 비교횟..
알고리즘 6 분기한정법각 노드를 방문할 때마다, 유망한지 여부를 확인하기 위해 Bound를 계산한다. 바운드= 해답치의 한계 이전까지의 최고 해답값보다 바운드가 더 좋다면 그 마디는 유망하다. 0-1 배낭채우기문제 - 깊이우선탐색 개념바운드설정법k = 총무게 W를 넘는 위치.totweight = 이전까지무게 + 시그마 i+1~k-1 앞으로무게바운드 = 이전까지금액 + 시그마~앞으로금액 + (W-totweight)*(k의 가성비)최대이익은 현재까지금액 기준, 이를 다음의 바운드값과 비교.유망하다면 자식노드를 계속 탐색.(재귀적) 0-1 배낭채우기문제 - 너비우선검색(분기한정 가지치기 최고우선검색)큐 사용 구현.코드if(profit(u) > maxprofit && weight < W) maxprofit = ..
알고리즘 5 되추적어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색.깊이우선탐색 함. -nQueens문제cols[i] = i번째줄.i = i번째 위치상태공간트리 사용유망성 확인. : 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않음. 정확한 분석은, 확률적알고리즘 사용 -부분집합의 합 구하기 문제원소들의 합이 W가 되는걸 구함.집합의 원소들을 오름차순으로 정렬.위에서부터 트리를 그린다.좌로 내려갈땐, 해당 원소의 값을 더함.우로 내려갈땐, 해당 원소의 값을 더하지 않음.더하면, SumOfSubset(i+1,weight+w[i+1],total-w[i+1]);안더하면, SumOfSubset(i+1,weight,total-w[i+1]) -m-색칠하기문제인접..
- Total
- Today
- Yesterday
- 워치os
- 22421
- 장치 확인
- IPA
- ios
- 아이패드
- Watch OS
- AppleTV
- 스위프트
- 애플
- 애플리케이션 로더
- 어플리케이션 로더
- 아이맥 프로
- iOS7
- 아이폰
- 홈팟
- 열거형
- TVos
- 단말기 확인
- Apple TV
- 업로드
- 개발
- 화면회전
- 열거
- homepod
- 애플와치
- xcode
- Swift
- Application Loader
- watchOS
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |