CS/Algorithm 검색 결과

해당 글 10건

바이너리 인덱스 트리 알고리즘 (펜윅 트리) 백준2042

바이너리 인덱스 트리 알고리즘 (Binary Indexed Tree) i&-i 앤드연산을 이용해 누적합을 계산하는 알고리즘이다. 1&-1 : 1 2&-2 : 2 3&-3 : 1 4&-4 : 4 ... 임을 이용한다. 이렇게 나오는 원리를 알아보면 아래와 같다. i i 2진수 2의 보수 i&-i result 1 00000001 11111111 00000001 1 2 00000010 11111110 00000010 2 3 00000011 11111101 00000001 1 4 00000100 11111100 00000100 4 1 2 1 4 1 8 1 16 1 32 ... 이렇게 나오는 원리를 이용해 각 인덱스별로 값 1개의 합, 값 2개의 합, 값 1개의 합, 값 4개의 합 구간합을 미리 구해놓는다. 백준..
CS/Algorithm 2021. 11. 22. 09:36

합병정렬 (Merge Sort), 백준 2751 Java

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 배열의 길이가 1이 될때 까지 분할 한뒤, 정렬하며 합치는 알고리즘 알고리즘 장점 : 안정정렬 (같은 값일 경우 상대적 위치가 바뀌지 않는다) 3 100000 -100000 0 -100000 0 100000 구현 방법 : (1) 배열을 반으로 나눠준다. (2) 나눈 배열을 다시 MergeSort에 태운다 (3) MergeSort를 타고 나온 두 배열의 요소들을 크기 비교하며 합친다. ..
CS/Algorithm 2019. 4. 23. 15:30

기수정렬 (Radix Sort) , 백준 2751 Java

기수정렬 (Radix Sort) , 백준 2751 Java 정수의 자리수의 숫자를 기준으로 큐에 넣어서 순서대로 꺼내는 방식으로 정렬을 기준이 되는 자리수를 바꿔가면서 정렬을 하는 알고리즘 아래와 같은 수가 있을 경우 65 22 125 83 9 70 첫번째, 배열 뒤부터 조회하며 65 22 125 83 9 70 일의 자리수를 기준으로 큐에 넣는다. 65 70 22 83 125 9 0 1 2 3 4 5 6 7 8 9 그리고 9부터 큐에서 꺼내 배열에 넣는다. 70 22 83 65 125 9 십의 자리수를 기준으로 큐에 넣는다. 22 9 125 65 70 83 0 1 2 3 4 5 6 7 8 9 그리고 9부터 큐에서 꺼내 배열에 넣는다. 9 22 125 65 70 83 세번째, 백의 자리수를 기준으로 큐에 ..
CS/Algorithm 2019. 4. 1. 10:32

[Algorithm] MST (최소 신장 트리)

프림(Prim) MST(Minimum Spanning Tree 최소 신장 트리) 프림 알고리즘(Prim's algorithm)가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용을 찾는 알고리즘이다. (greedy algorithm 임) 개요프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 임의의 하나의 정점을 선택한다.선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.1.2 과정을 반복 하여 모든 정점이 선택될까지 한다. 알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다. 동작 예제 어떤 점에서 시작하던 관계는 없습니다. 좌측 그래프에서는 임의의 시작점 D를 선택합니다. D지점..
CS/Algorithm 2017. 7. 7. 17:17