hello world

최소신장트리(MST) 입력 : n 개의 도시, 도시와 도시를 연결하는 비용 문제: 최소 비용으로 모든도시들이 서로 연결되게한다. 정점 = 도시 위의 그림에서 d와 f를 연결하는 도로건설하려면 비용이 14가 든다고 볼수있다. 예산은 항상 부족하기 마련이므로 비용을 최소로 들여서.. 이그래프중 edge 중 일부의 edge만 선택을해서 내가 선택한 edge에 의해서 이 그래프의 모든 node가 연결이 되면서 비용이 최소가 되는.. 무방향 가중치 그래프..(가중치는 다 양수다) 위 그림의 굵은 선이 MST - MST는 유일하지 않다! 왜 트리라고 부르나? -싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다. -MST 문제의 답은 항상 트리가 됨 . 왜? 위의 그래프는 서로 연결됨.. 노드 n개인 트리는 항상..

깊이 우선 순회 (DFS) 1.출발점 S에서 시작한다. 2.현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다. 3.2번 계속 반복한다. 4.만약 unvisited 인 이웃노드가 존재하지 않는동안 계속해서 직진 노드로 되돌아감. 5.다시 2번을 반복 6.시작 노드 S로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 아래와 같은 그림 흐름으로 깊이 우선순회가 이루어짐 DFS(G, v) visited[v]

해슁3 좋은 해쉬 함수란? -현실에서는 키들이 랜덤하지 않음 -만약 키들의 통계적 분포에 대해 알고있다면 이를 이용해서 해쉬함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 -키들이 어떤 특정한 패턴을 가지더라도 해쉬함수값이 불규칙적이되도록 하는게 바람직 (랜덤보다는 특정 패턴을 가지는게 흔함) -해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야한다. DIVISION 기법 - h(k) = k mod m -예 : m = 20 and k =91 => h(k) =11 -장점 : 한번의 mod 연산으로 계산. 따라서 빠름 -단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. Multiplication 기법 -0에서 1사이의 상수 A를 선택 0

해슁1 - 정리 SUHA(Simple uniform Hashing Assumption) -각각의 키가 모든 슬록들에 균등한 확률로 독립적으로 해싱된다는 가정 -성능 분석을 위해서 주로 하는 가정임 -hash 함수는 deterministric 하므로 현실에서는 불가능 -Load Factor a = n/m;() -n:테이블에 저장된 키의 개수 -m:해쉬테이블의 크기, 즉 연결리스트의 개수 -각 슬롯에 저장된 키의 평균 개수 어떤 키가 각각의 슬록에 따라 균등하게 분포된다는것은 말이안됨 해싱을 포함하는 어떤 알고리즘의 성능을 분석하기위해서 사용하는 가정 (현실에서 실행X) 참고 영상 www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%..

Binary Search Tree 3가지 Search insert delete - 노드입장에서 왼쪽은 나보다 작고 다른쪽은 큰 트리. 극단적으로 치우칠수 있다. O(n), O(h) Random Permitation - 실제로 극단적인 경우를 제외하고 저장되는 데이터들이 랜덤하다면 평균 시간복잡도가 n 이 된다. 저장된 데이터의 순서가 정렬된 bst에 insert 된다면 처음 온것이 루트가 될것이다. 동작원리 - 2진검색트리와 비슷(단, 트리가 완벽하게 Balance 가 맞춰있다면....) 최악의 겨우 트리가 극단적으로 unBalance 될 수 있다. 그러므로 트리가 무너지지 않도록 추가적인 작업이 필요하다. ->>>>>> 여러가지 방법중 대표적인 예시가 red black tree 이다. red black..

DELETE 연산 -삭제할 노드를 찾음(key를 가진 노드) -사전 작업으로 search 1.DELETE할 노드가 자식이 없는 경우 2.DELETE할 노드가 자식이 한명인 경우 3.DELETE할 노드가 자식이 두명인 경우 세가지 케이스를 나누어 각각 처리하는 알고리즘 1.DELETE할 노드가 자식이 없는 경우 (위그림에서 숫자 4의 경우) : 그냥 삭제 2.DELETE할 노드가 자식이 한명인 경우 ( 위그림에서 숫자 7의 경우) : 자신의 자식노드를 원래 자신의 위치로 부모도,자식도 유일하므로 바로 부모-자식으로 연결해줌 3.DELETE할 노드가 자식이 두명인 경우 (위 그림에서 13을 삭제하는 경우) -노드 13을 트리로 부터 제거하면 상황이 복잡해짐,, 6과 18이 부모노드가 없어지기때문,, 그래서 ..

검색트리의 필요성을 알아보기위해 배열과 정렬의 [시간 복잡도] SEARCH INSERT DELETE 배열 정렬 O(logN) O(N) O(N) 정렬X O(N) O(1) O(1) SEARCH INSERT DELETE 연결리스트 정렬 O(N) O(N) O(N) 정렬X O(N) O(1) O(1) 배열 정렬했을경우 INSERT와 , DELETE자기자리를 찾아야하기때문에 아무렇게나 넣기 불가능 연결리스트의 경우 정렬을 해뒀더라도 binary search 불가능하다. 순차적으로 따라가 볼 수 밖에 없음 정렬된 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n) 어떻게 하면 INSERT, SEARCH, DELETE 를 효율적으로 하는가? 대표적인..

보호되어 있는 글입니다.