분류 전체보기114 기타 알고리즘 ( 투 포인터, 구간 합 ) : 투 포인터 ( Tow pointer ) : 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 두개의 점의 위치를 기록하면서 처리하는 알고리즘이다. : 흔히 2,3,4,5,6,7 번 학생을 지목할 때, 간단히 2번부터 7번 까지의 학생 이라고 부르곤 한다. 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝 점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. : 두개의 포인터를 어떻게 활용하냐가 관건이 되는 것으로 딱히 어떤 형태로 규정되어있지 않다. 고로 아이디어를 떠올려보는 한가지 경로로 생각해두면 될 것 같다. : 구간 합 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제 N개의 정수로 구성된 수열, M개의 쿼리 ( Query ) .. 2021. 12. 31. 위상정렬 알고리즘 ( 참고 강의 : https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9&t=1986s&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 ) : 위상 정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 용어로는 진입차수 ( Indegree ) : 특정한 노드로 들어오는 간선의 개수 진출차수 ( Outdegerr ) : 특정한 노드에서 나가는 간선의 개수 를 알아두자. 위상 정렬 알고리즘은 큐를 이용해서도 구현할 수 있는데, 1. 진입차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원.. 2021. 12. 31. 위상정렬 ( 참고 강의 : https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9&t=1986s&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 ) : 위상 정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 위와 같이 표현되고, 고급 알고리즘은 자료구조와, 알고리즘 모두 충족해야 가능하다. 용어로는 진입차수 ( Indegree ) : 특정한 노드로 들어오는 간선의 개수 진출차수 ( Outdegerr ) : 특정한 노드에서 나가는 간선의 개수 를 알아두자. 위상 정렬 알고리즘은 큐를 이용해서도 구현할 수 있는데, 1. 진입차수가 0인 모든.. 2021. 12. 30. 서로소 집합 연산을 통해 Cycle을 확인하는 방법의 궁금증의 답 ( 궁금했던 내용을 확인해보려면 : https://the-bingle.tistory.com/85 ) 나온 자료들에대해 내가 잘 못 알고 있었다. union은 둘의 root를 연결하는 연산 find는 root노드를 찾는 것. 이렇게 분리하고 인식해야 했다. 간선에대해서 양 노드의 루트 노드를 find를 이용해 찾고, 이 두개의 루트 노드가 동일하다면 cycle 동일하지 않다면, union을 통해 둘의 루트 노드를 연결하는 것이다. 이 과정을 반복하면 되는데, union을 통해, 두 노드의 루트노드가 같아지는건 연결되어있음을 의미하고, 당연한 결과이다. 간선에대해서 라는 부분이 확인하는 지점임을 생각하자. 2021. 12. 30. 서로소 집합의 Union 연산을 통한 Cycle 판별에 대한 궁금증. 이와 같이 5개의 간선으로 연결된, 5개의 노드가 있다. 노드 번호 1 2 3 4 5 부모 노드 1 2 3 4 5 Union 연산을 이용해 사이클 ( Cycle ) 여부를 알아보고자 한다. Union(1,2) 노드 번호 1 2 3 4 5 부모 노드 1* 1* 3 4 5 Union(2,3) 노드 번호 1 2 3 4 5 부모 노드 1 1* 1* 4 5 Union(3,5) 노드 번호 1 2 3 4 5 부모 노드 1 1 1* 4 1* Union(4,5) 노드 번호 1 2 3 4 5 부모 노드 1 1 1 1* 1* Union(1,4) 노드 번호 1 2 3 4 5 부모 노드 1* 1 1 1* 1 루트 노드가 같아, Cycle이 있음을 알 수 있다. 여기서, 궁금증이 생기는데, 지금은 Union 연산이 사실 의미를 .. 2021. 12. 30. 기타 그래프 이론 ( 서로소 집합 자료구조 ) : 서로소 집합 자료구조 서로소란? 공통 원소가 없는 두 집합을 의미한다. { 1, 2 }, { 3, 4 } 는 서로소 관계이다. { 1, 2 }. { 2, 3 } 은 서로소 관계가 아니다. 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원한다. 합집합 ( Union ) : 원소가 포함된 두 개의 집합을 하나의 집합으로 합치는 연산 찾기 ( Find ) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기 ( Union Find ) 자료구조로 불리기도 한다. 여러개의 합치기 연산이 주어졌을 때, 서로소 집합 자료구조의 동작과정은 다음과 같다. 1. 합집합( Union ) 연산을 확인해, 서로 연결.. 2021. 12. 30. 최단 경로 알고리즘 ( 강의 출처 : https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 ) 최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘 : 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 음의 간선이 없을 때 정상적으로 동작한다. ( 현실 세계의 간선은 음의 간선으로 표현되지 않음 ) 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨 : 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복. 또한, 최단경로 알고리즘은 다이나믹 프로그래밍의 분류에 속하기도 함... 2021. 12. 29. 다이나믹 프로그래밍 ( Dynamic Programming ) ( 참고 출저 : https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 ) : 다이나믹 프로그래밍 ( 동적 계획법 ) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법. 이미 계산된 결과 ( 작은 문제 ) 는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 일반적으로 탑 다운, 보텀 업 두 가지 방식으로 구현한다. 이름을 보고 제일 먼저 공부해보고 싶은 영역이라 여기까지 오는데 안달났었다. 드디어 이 멋진 이름의 프로그래밍이 어떤건지 알아보자. 일반적인 프로그래밍 분야에서의 동적 ( Dynami.. 2021. 12. 23. 이진 탐색 ( Binary Search ) ( 참고 출저 : https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 ) : 이진 탐색 알고리즘 순차 탐색과 비교해보면, 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법. 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. : 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 정렬된 리스트안에 중간점의 값과 목표한 값을 비교하고, 중간점의 값이 목표한 값보다 크다면, 시작점과 중간점의 사이에서 탐색을 하게되고, 중간점의 값이 목표한 값보다 작다면, 중간점과 끝점 사이에서 탐색을 하는 .. 2021. 12. 20. 정렬 알고리즘 ( 참고 출처 : https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 ) : 정렬 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 처리되지 않은 데이터중에 맨 앞에 있는 데이터와 바꾸는 것을 반복. 4 3 2 1 1 3 2 4 1 2 3 4 와 같은 흐름이다. 선택 정렬은 처리되지 않은 데이터 중에서 가장 작은 데이터를 골라내는 연산, 맨 앞에 데이터와 바꾸는 연산이 시행이되고 처리되지 않은 데이터를 골라내는 작업을 반복해서 시행하므로 시간복잡도는 O(n^2)에 해당한다. 삽입 정렬 : 처리되지 않은 데.. 2021. 12. 20. 이전 1 2 3 4 5 6 7 ··· 12 다음
