알고리즘

    Sorting Algorithm

    2020.09.20

    데이터를 오름차순 / 내림차순으로 나열 하는 것. 종류 선택 정렬 ( Selection Sort ) 삽입 정렬 ( Insertion Sort ) 버블 정렬 ( Bubble Sort ) 셸 정렬 ( Shell Sort ) 퀵 정렬 ( Quick Sort ) 힙 정렬 ( Heap Sort ) 합병 정렬 ( Merge Sort ) 기수 정렬 ( Radix Sort ) 계수(카운트) 정렬 ( Count Sort ) 트리 정렬 (업로드 예정) 큐브 ...

    최장 증가 수열

    2021.06.03

    주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열이다. 예를 들어, 341256784134라는 수열에서 LIS는 345678 or 125678 이 된다. 찾는 방법 LIS의 크기 구하는 방법은 dp와 이분탐색에 따라 방법이 나뉘며 경로 추적(trace)방법은 두 방법 모두 인덱스를 가리키는 배열을 하나 추가하여, 탐색하면서 해당 값의 앞의 수열 인덱스를 저장하는 방법으로 구현한다. 이 배열을 가지고 가장 큰 부분순열을 갖는 값부터 역 추 ...

    Permutation(순열)

    2021.05.28

    1. next_permutation c++에는 algorithm헤더에 매개변수의 배열/iterator의 다음 순열을 적용시켜 바뀌었다면 true/false를 반환해주는 메서드가 존재해서 이를 do~while문으로 쉽게 순열문제를 해결할 수 있다. 하지만, 자바는 존재하지 않기 때문에 다음과 같이 구현할 수 있다. public boolean next_permutation(int[] arr){ //뒤에서부터 탐색해서 내림차순이 깨지는 지점(a) 찾 ...

    [APSP] Floyd Warshall알고리즘

    2021.04.12

    벨만-포드 알고리즘과 다익스트라 알고리즘과 달리 모든 최단 경로를 구하는 알고리즘입니다. (물론 두 알고리즘도 모든 정점에대해 수행하면 모든 최단 경로를 구할 수 있습니다.) 특징 음의 가중치 허용 optimal substructure 개념 이용 배열을 이용하여 구현 밀집그래프에서 모든 edge간 경로 구할때 적합 Pesudo Code let dist be a |V| × |V| array of minimum distances initia ...

    [MST] Prim알고리즘

    2021.04.12

    우선순위 큐의 방법을 이용하는 알고리즘으로 vertex를 한개씩 선택하며 최소 비용의 edge를 찾는 방법입니다. decrease-key의 개념을 이용하며 decrease-key는 현재 계산된 v노드까지의 거리보다 현재 노드 u부터 v까지의 경로가 더 작다면 값을 갱신해주는 방법을 이용합니다. 특징 정점 선택 기반 시작 정점부터 출발하여 해당 노드까지의 최소 비용을 기록하는 배열을 이용하여 구하는 방식 자료구조중 하나인 우선순위 큐 ...

    [Disjoint Set] Union Find 알고리즘

    2021.04.12

    Disjoint Set 번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set)으로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합입니다. Union-Find Union : 두개의 집합을 하나의 집합으로 합치는 것. Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것. 집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단할때 각 집합의 대표값(root)을 이 ...