Computer Science/알고리즘14 그래프 탐색(2) - BFS(너비우선탐색) 알고리즘 너비 우선 탐색(Breadth First Search : DFS)은 그래프의 특정 노드에서 시작하여 전체 노드를 탐색하는 알고리즘이다. 탐색을 할 때 시작 정점에서 인접한 노드를 먼저 탐색하여, 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 방식을 가진다. level을 높여가면서 각각의 정점을 탐색해나가는 알고리즘이다. 알고리즘 구현 방식에는 큐를 사용한다. 정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간복잡도 - 인접 행렬로 표현된 경우, 시간복잡도는 O(n^2) - 인접 리스트로 표현된 경우, 시간복잡도는 O(n+e) ** 그래프의 크기가 작을 경우, BFS가 더 유리함 (알고리즘 구현) 재귀 함수 - 인접 행렬(이차원 배열)로 구현했을 때. 아래와 같은 그래프(트리)가 .. 2021. 1. 20. 그래프 탐색(1) - DFS(깊이 우선 탐색) 알고리즘 깊이 우선 탐색(Depth First Search : DFS)은 그래프의 특정 노드에서 시작하여 전체 노드를 탐색하는 알고리즘이다. 탐색을 할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면, 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방식을 가진다. 알고리즘 구현 방식에는 재귀 함수로 코드를 작성하거나 스택을 사용하는 두 가지가 있다. 정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간복잡도 - 인접 행렬로 표현된 경우, 시간복잡도는 O(n^2) - 인접 리스트로 표현된 경우, 시간복잡도는 O(n+e) (알고리즘 구현) 재귀 함수 - 인접 행렬(이차원 배열)로 구현했을 때. 아래와 같은 그래프(트리)가 존재할 때, 행렬에서 간선이 존재하는 부분은.. 2021. 1. 19. 자카드 유사도란? 자카드 유사도란? : Jaccard Similarity 혹은 자카드 지수라고 불리며, 두 문장을 각각 단어의 집합으로 만든 뒤 두 집합을 통해 유사도를 측정하는 방식 중 하나다. (정의) 교집합의 크기 / 합집합의 크기 - 0과 1 사이의 값을 가진다. - 만약 두 집합이 동일하다면 1의 값을 가진다. - 만약 두 집합의 교집합이 없다면 0의 값을 가진다. 자바로 만든 자카드 유사도 >> jihyeong-ji99hy99.tistory.com/148 2020. 12. 27. [알고리즘] Dynamic 프로그래밍과 예제들 우리가 여태 배워온 것들은 아래와 같다. - D&C 기법 - Backtracking 기법 : 어떤 결정의 연속을 통해 문제의 답을 점차적으로 만들어가는 것. Recursion을 돌린다. -> 문제에 대한 일반화가 필요함. // 이번시간에 배울 것 - Recursion은 항상 옳은가? - 쓸데 없이 많은 Recursive call을 줄여보자. - 점화식을 이용한 효율적 구현 >> Dynamic program (동적 계획법) Dynamic Programming을 사용한 알고리즘 - Fibonacci number 계산 - Longest Increasing Subsequence(LIS) - Subset Sum ---------------------------------------------------------.. 2020. 5. 13. [알고리즘] D&C 기법의 예시와 좋은 pivot이란? (지난주) D&C기법? 같은 문제의 더 작은 instance로 recursion 하는 방법. D&C 알고리즘의 시간 복잡도 분석 1. 점화식을 찾아라 ( 재귀하는 부분 & 나머지 부분 ) -> T(n) = r*T(n/c)+O(f(n)) 형태 2. 점화식을 풀어라 ( Recursion tree , Master Theorem 등) Mater Theorem : 점화식이 T(n) = r*T(n/c) + O(f(n)) 형태를 만족할 때만 적용 가능, f(n)과 n^(log c r)을 비교 - f(n) = Ω(n^(logc r+ε) >> T(n) = O(f(n)) - f(n) = Θ(n^(log c r) >> T(n) = O(f(n) * log n) - f(n) = O(n^(log c r-ε) >> T(n) = O.. 2020. 5. 11. [알고리즘] D&C 기법, Recursion tree와 Master Theorem //저번 시간 Recursion : simple and delegate! 자기 자신으로 reduce 하는 전략 Reduction >> 다른 문제의 알고리즘을 활용한다. Recursive algorithms : Correctness : induction으로 증명한다. Time Complexity Analysis : 점화식을 구한다. ---------------------------------------------------------------------------- //이번 시간 1. Divide and Conquer //패턴(결국엔 recursion) 알고리즘 설계, 문제 해결 기법 n이 주어지면 -1씩 줄어드는 것이 아닌 더 덩어리가 크게 나누어진다. 2. D&C (divide and conquer).. 2020. 5. 8. 이전 1 2 3 다음
