알고리즘 (54) 썸네일형 리스트형 알고리즘26 randomization 알고리즘은 determination 알고리즘에 비해서 약하다. 왜? 간단한 게 별로 없다. 확률 계산이 정확해야 한다. 소인수분해는 너무 느리다. n이 있으면 2로 나눠보고 3으로 나눠보고...n-1까지 나눠본다. 하나도 나눠지지 않으면 소수 => 굉장히 느리다 입력은 숫자 한개 n 인데 예를 들어 367이라면 367번 계산? O(n)? 너무 느리다. 숫자가 작고 크고에 따라 시간이 다르지만, 주어진 숫자가 32비트 이하라면 시간이 똑같다고 쳐도 되는 수준 예를 들어 merge sort의 경우 n개 숫자 크기와 상관없이 갯수만 가지고 O(nlogn)이라고 말할 수 있다. 정확히 말하면 O(nlogn x s) -> s는 숫자 두 개를 비교하는 시간 주어진 숫자의 범위가 1~m이라면.. 알고리즘25-2 Las Vegas vs Monte Carlo Las Vegas: 답은 항상 정확하지만 언제 끝나는지 왔다갔다한다. Monte Carlo: 시간은 똑같지만 답이 맞을 때가 있고 틀릴 떄가 있다. 답이 항상 맞지 않아도 정확할 확률이 아주 높아야 한다,, 시간이 nlogn에 끝날 확률이 매우 높은 것처럼 Las Vegas->Monte Carlo: 항상 가능 미리 시간을 딱 정해서 시간이 끝나면 아무 답이나 출력하는 방법이 있다. 시간은 정해져있고 가끔 맞고 가끔 틀리는 알고리즘으로 바뀐다. Monte Carlo->Las Vegas: 바꿀 수 있지만 항상은 아님. 답이 나오면 그 답이 맞는 답인지 알 수 있는 경우가 있고 모르는 경우가 있다. 답을 푸는 것과 답이 맞는지 확인하는 것은 매우 다른 문제! 예를들어, 소인수분해 문제는 풀기는 어렵지만 확인은.. 알고리즘25 Randomized Algorithm 보호되어 있는 글입니다. 알고리즘24-2 traveling salesman problem 세일즈맨이 집에서 출발해서 다른 곳들을 방문하고 자기 집으로 돌아온다. 최소 weight로 모든 곳을 한 번씩만 다 가는 path (출발점인 s만 두번) 노드가 n개면 (n-1)!가지 = 노드의 모든 시퀀스 한군데를 끝까지 다 가봤다고 치는 작전! 현재까지 cost중 가장 좋은 것 찾기 답이 없다는 것이 확실하면 cut off하니까 답을 찾고 있다는 것은 보장할 수 있다. 루트에서 쭉 내려오면 cost를 계산할 수 있다. 1. current cost가 current best cost보다 크면 cut off하면 된다. 2. (current cost + 남은 엣지의 갯수)를 current best cost와 비교 (edge weight가 최소 1이므로) 3. current cost + 남은 엣지의 갯수 * .. 알고리즘24 State Space 수업 때 배운 이야기 70,80%를 평소에 알고있어야한다,, 찔린다 빈공간과 상하좌우를 스와이프하는 퍼즐! 퍼즐을 부셔서 넣었을 때, 왼쪽 -> 오른쪽 상태로 맞출 수 있는가? * 안되는 경우가 있다 * 한 그룹은 solve가능한 상태 / 한 그룹은 불가능한 상태 뽑아서 아무거나 두개를 바꾼다. => 못 푼다. 옆에 것도 뽑아서 바꾸면 => 다시 풀 수 있는 상태 하나의 판은 각각의 노드이고 두개를 연결하는 엣지가 있다. (빈 칸에 인접한 칸이 3개이므로 엣지 3개) 16!은 생각보다 큰 숫자 다 그려서 알아낸 건 아니다. 16개짜리 수열로 나타내자 (빈칸 = 16) number of inversion을 정의한다. 각각 뒤집어진 것의 갯수(자신보다 오른쪽 중 자신보다 작은 수의 갯수)를 구해서 모두 더하.. 알고리즘23-2 동전 교환 다이나믹 프로그래밍 적용 후) O(W N) 동전 갯수를 가장 적게쓰는 방법을 쓴다. 하나로 못만드는 금액이면 여러개로 만들어야하는데, 이미 가능한 금액에 2원 or 5원 or 9원을 추가해야한다. 마지막에 추가한 것은 2,5,9원 중 하나일 것이다. 마지막에 2원을 추가해서 3를 만들수있나? 없다. 마지막에 5원을 추가해서 3를 만들수있나? 없다. 마지막에 9원을 추가해서 3를 만들수있나? 없다. 하나의 값을 계산하는데 n개를 본다. 0,1,2,...,w = O(WN) 막대기 자르기 n-1번 자르므로 2^(n-1)가지 다 해보는 것: O(2^(n-1 x n)) 다이나믹 프로그래밍 : O(nk) 동전 나누기와 아이디어 자체는 비슷하다. 합 분해 순서가 다른 것을 따로 센다. 순서를 무시하게 되면 훨씬 어려.. 알고리즘 23 Backtracking and Pseudopolynomial - N-Queen 모든 경우 + cut off (이런 경우에는 안보겠다는 규칙) N-Queen 퀸 : 상하좌우,대각선을 공격할 수 있음 1. 다 해본다. 64^8가지의 방법으로 배치 후 테스트 (같은 자리에 퀸이 여러개 놓을 수 있는 경우) 각각의 퀸의 쌍에 대해서 공격하는지에 대해 보는 전체 시간 : 64^8 x 8 x 7 (대충 2^54) 2. 겹치는 경우를 뺀다. 64C8 (64개의 자리에 8개를 고른다.) 전체 시간: 64C8 x 8 x 7 3. 각 row에 하나씩 배치 8^8 x 8 x 7 (대충 8^10 = 2^30) 4. Recursion + cut off i : 몇번째 row에 퀸을 배치해야 하는지 4x4 Example (차이 == 거리면 대각선으로 안됨!) 재귀적으로 다 돌렸다. 사실 대칭이니까 위에는 반.. 알고리즘22 SCC SCC 안에서는 다른 어느 노드든 다 이동할 수 있다. 더 이상 키울 수 없는 노드들의 집합 그 안의 노드들은 양쪽으로 reachable 사이클 = SCC는 아니지만 사이클 하나는 SCC. 일단 그냥 사이클이라고 생각하고 일단 무작정 DFS를 해보자. (cut vertex는 어디에서 시작해도 같은 결과가 나온 것과 다르게) 하지만 시작 지점에 따라 DFS tree가 다르게 나오고 전진할 수 있는 것이 여러개 있을 때 어디로 전진하느냐에 따라서 다르게 나온다. 같은 그래프지만 트리가 두개로 나올 수도! 한 트리가 여러개의 SCC를 가지고 있을 수는 있지만, 한 SCC가 여러 Tree에 나눠있지는 않다! 한 번 들어오면 다 돌기 때문에 다른 트리로 나눠질 수 없다. 한 SCC에 들어 있는 노드들이 두 개의 .. 이전 1 2 3 4 5 ··· 7 다음
