목록CS/알고리즘 (7)
개발자 김수진
[ 알고리즘] 이분탐색(Binary Search)
[개념] 이분탐색이란 탐색기법중 하나로 중간값을 기준으로 탐색 범위를 절반씩 줄여가며 탐색한다. 따라서 처음부터 끝까지 모두 탐색하는 기법은 worst case의 경우 시간복잡도가 (O(N))이다. 하지만 이분탐색의 경우 탐색범위를 절반씩 줄여나가기 때문에 O(logN)으로 완전탐색보다 빠르다. 1. 탐색하고자 하는 배열은 이미 정렬이 되어있다. 2. left, right 값을 통해 중간값인 mid 값을 구한다. 3-1. 찾고자하는 값이 mid 위치에 존재하는 값보다 클 경우 , left를 mid 뒤로 옮긴다. 3-2. 찾고자하는 값이 mid 위치에 존재하는 값보다 작을 경우 , right를 mid 앞으로 옮긴다. 4. 다시 위의 과정을 left가 right 값보다 커질 때까지 반복한다. - 예시 배열의..
[알고리즘] 위상 정렬 (Topology Sort)
[개념] 위상 정렬이란 ? 위상 정렬(Topology Sort) 알고리즘이란 순서가 정해진 작업을 차례대로 수행해야 할 때, 순서를 결정하기 위해 사용하는 알고리즘이다. 하나의 노드에 들어오기 위해 필요한 노드의 개수를 '진입차수'라고 한다. 위의 예제에서 보면 2번 노드의 진입차수는 13,7에 의해 2가 된다. 위상 정렬은 방향 그래프에서 진입차수가 0인 노드가 하나 존재해야 된다. 그리고 해당 노드가 위상 정렬의 시작 노드가 된다. 위상 정렬은 진입차수가 0인 노드를 시작으로 순서대로 queue에 넣어준다. 하나의 방향 그래프에서 여러 가지의 위상 정렬이 가능하다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐에서 꺼내고 해당 노드에 부속된 간선 삭제 1,2번을 계속 반복해가면서 모든 노드가 선..
[알고리즘] 투 포인터 알고리즘
[개념] 구간 합을 구할 때 사용되는 알고리즘으로 배열의 길이가 짧은 경우 이중 for문을 사용해서 구하면 되지만 배열의 길이가 길어지면 시간 초과가 발생하므로 투 포인터 알고리즘을 사용한다. 아래 코드에서 보면 N은 배열의 크기, M은 구하고자 하는 합이다. 구간의 합이 M을 만족하는 경우의 수를 구한다고 하자. start, end 모두 배열의 첫번째부터 시작한다. - M = sum 구간의 합이 M과 같다면 경우의 수 total에 1을 추가한다. 그리고 end를 한칸 뒤로 움직인다. - M < sum 현재 구간의 합이 구하고자 하는 구간의 합보다 크다면 start를 1씩 증가시켜 주면서 구간의 범위를 좁혀준다. 이 때 start가 end보다 커지게 되는 경우 start, end를 같은 위치로 처리한다...
[알고리즘] 크루스칼 알고리즘 ( Kruskal Algorithm)
[개념] 크루스칼 알고리즘은 모든 노드들을 최소 비용으롤 연결하는 알고리즘이다. N개의 노드를 N-1개의 간선으로 연결 ex) 모든 도시를 도로로 연결할 때 가장 적은 비용으로 연결하는 방법 1. 노드 간의 연결 정보를 저장하고 비용을 기준으로 오름차순으로 정렬한다. 2. 비용이 적은 것부터 연결 이 때 사이클이 발생하지 않도록 주의 ==> Union-Find 를 사용해 확인, 노드를 연결할 때 부모가 같다면 이미 연결된 것이므로 제외 3. 현재 간선을 현재 MST 집합에 추가 아래 그림과 같이 가중치를 기준으로 오름차순으로 정렬한다. 가중치가 작은 것부터 선택하여 노드를 서로 연결한다. 해당 예제에서는 2번 노드와 5번 노드를 연결한다. (아래 그림에서 방향 그래프로 그렸는데 잘못 그렸습니다. 크루스칼..
[알고리즘] 이진탐색 ( Binary Search)
[개념] 이진 탐색은 데이터가 정렬되어 있는 상태에서 특정 데이터를 찾는다. 배열의 시작, 중간, 끝 index를 조절해가며 탐색을 한다. 찾고자 하는 값인 x가 배열의 중간 값보다 작으면 중간을 기준으로 왼쪽에 있는 데이터 중에서만 찾고 x가 배열의 중간 값보다 클 경우 중간을 기준으로 오른쪽에 있는 데이터 중에서만 찾는다. 이와 같이 탐색 범위를 좁혀가면서 찾고자하는 값을 찾아낸다. 위의 그림은 이진 탐색의 예시로 정렬된 배열을 가지고 시작한다. 찾고자 하는 값인 13은 처음 mid인 7보다 크므로 low = mid +1이 되고 , mid = (low+high)/2 = 3 이 된다. arr[3]이 13이므로 true를 반환하면서 탐색을 종료한다. [코드] 아래 코드와 같이 low는 배열의 시작, hi..
[알고리즘] 기본 정렬 알고리즘 (삽입 정렬, 선택 정렬, 버블 정렬)
- 선택 정렬 ( Selection Sort) [ 개념 ] 선택 정렬은 현재 자신의 index보다 뒤에 있는 index들 중에서 배열의 원소 값이 가장 작은 원소랑 자리를 서로 바꿔줍니다. 이러한 방식으로 배열의 처음부터 끝까지 진행하여 정렬을 할 수 있습니다. 아래 그림은 선택 정렬의 예시로 다시 한번 설명해드리겠습니다. 먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다. 첫번째 index부터 시작하여 자신의 값보다 작은 값들 중에서 가장 작은 값을 찾습니다. 해당 배열에서는 '13'보다 작은 값 중에서 제일 작은 '2'를 택하게 됩니다. 제일 작은 값을 찾은 뒤 서로 자리를 swap합니다. 다음 index로 넘어가 두번째 index를 기준으로 뒤에 있는 값들 중에서 가장 작은 값을 찾습니다. ..
[알고리즘] 유니온 파인드 ( Union-Find)
[ 유니온 파인드란 ? ] 합집합을 찾는 대표적인 알고리즘 Disjoint-Set이라고도 부른다. - Union : 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 하나로 합친다. - Find : 노드 X가 포함된 집합을 찾아준다. [ 구현 ] - i는 노드번호, parent[i]는 i 노드의 부모 노드를 저장 [그림 1]과 같이 처음에는 parent[i] 를 자기 자신인 i로 초기화한다. Union(1,2) Union(3,4)을 통해 그림 2와 같이 변한다. 노드 2의 부모 노드는 1이 되고 , 노드 4의 부모 노드는 3이 된다. Union(1,3)을 통해 노드 3의 부모 노드는 1이 된다. 따라서 1,2,3,4가 하나의 집합에 포함되는 것을 확인할 수 있다. [ Find 함수 ] 위에서 설명한 것과..