728x90 반응형 2019/0446 이진 탐색 vs 이진 탐색 트리 근본적으로 같은 원리에 의한 탐색 구조 이진 탐색 배열에 저장된 데이터를 탐색 - 동적으로 크기가 변하는 데이터 집합 탐색에는 부적합 - 삽입과 삭제가 상당히 힘들다 시간 복잡도 O(logN) 처음에 입력된 갯수가 N 이라 하면, 첫 시행 후에 반이 버려지게 되서 1/2 * N, 두번째 시행 후에 또 반이 버려져서 1/2 * 1/2 * N, 세번째 시행 후에 또 그 반이 버려져서 1/2 * 1/2 * 1/2 * N, K번 시행후에는 (1/2)^K * N 이렇게 수행을 계속하다가 탐색이 끝나면 자료가 한개 남개 된다. 따라서 (1/2)^K * N ≒ 1 K = logN 이진 탐색 트리 연결 리스트 데이터에 대한 탐색 - 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 - 삽입, 삭제가 빈번히 이.. 2019. 4. 30. 최단 경로 가중치 그래프 G = (V,E), 즉 모든 edge에 가중치가 있다. 방향그래프이냐 무방향 그래프이냐는 별로 중요하지 않다. 경로 p=(v0,v1,....,vk)의 길이는 경로상의 모든 엣지의 가중치의 합 BFS의 경우 edge의 갯수가 경로의 길이가 될 때, 모든 edge의 weight가 다 1이거나 모두 동일하다면 edge의 갯수가 가장 작은 경로가 최단 경로가 된다. 이런 경우에는 BFS 알고리즘 만으로도 최단 경로를 구할 수 있다. single-source : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 방식(다익스트라) single destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 방식 무방향 그래프일 때는 이 두가지 방식이 똑같다. All.. 2019. 4. 28. 그리디 알고리즘 욕심쟁이 알고리즘 매 선택에서 지금 이 순간 최적인 답을 선택하여 적합한 결과를 도출하자 라는 모토를 가지는 알고리즘 설계 기법 예를 들어, 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다. 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그 중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것.. 2019. 4. 28. 배낭 문제 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 때 짐을 쪼갤 수 있다면 분할가능 배낭문제, 쪼갤 수 없다면 0-1 배낭문제 라고 한다. 0-1 배낭 문제 무게 제한이 50인 배낭에 다음과 같은 세 개의 물건을 넣는 문제이다. 넣은 물건들의 가치(v) 합이 최대가 되면 된다. 직관적으로 2,3번 물건을 넣어서 무게는 50에 맞추고, 가치를 220으로 하면 최적이다. zeroOneKnapsack(item, cap){ for i 2019. 4. 28. 동적 계획법 동적계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 원리 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 동적 계획법과 그리디 알고리즘의 차이 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체.. 2019. 4. 28. 벨만 포드 알고리즘(The Bellman-Ford algorithm) 알고리즘 정의 하나의 시작점에서 하나의 도착점으로 가는 최단경로 문제를 해결하는 알고리즘이다. 특징 음의 간선이 있는 경우에도 문제를 해결한다. 수도코드 Bellman-Ford(G,w,s) Initialize-Single-source(G,s) for i 2019. 4. 28. 퀵 정렬 보호되어 있는 글 입니다. 2019. 4. 26. 이전 1 2 3 4 ··· 7 다음 728x90 반응형
