알고리즘/알고리즘
-
트라이 자료구조알고리즘/알고리즘 2022. 4. 20. 20:34
트라이(Trie)란? 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어 있는 자료구조입니다. Trie라는 말은 탐색 트리(retrieval tree)에서 나온 단어입니다. 트라이 자료구조의 예시이며 주황색으로 된 노드들이 입력된 문자열입니다. 예를 들어 cat이라는 단어를 검색하기 위해서는 제일 먼저 'c'를 찾고, 다음에 ca 그다음에 cat의 순서로 찾습니다. 여기에서는 리프노드(끝 노드)들에 모든 문자열들이 들어가 있습니다. 트라이 자료구조의 장단점 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색하는 것보다 시간 복잡도에서 훨씬 더 효율적입니다. 각 노드에서 자식들에 대한 포..
-
가장 빠르게 소수를 찾는 방법알고리즘/알고리즘 2022. 3. 26. 00:01
소수란? 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는, 1보다 큰 자연수입니다. 방법 1: 가장 간단한 방법 N이 소수인지 판별하기 위해서는 2 ~ N-1까지 나누어서 하나라도 나누어 떨어지는가를 확인하는 방법이 있습니다. 이는 한개의 숫자에 대해 소수인지 파별하기 위해서는 O(N)의 시간 복잡도를 가지며 N개의 수에 대해서는 O(N^2)의 시간 복잡도를 가집니다. 방법 2 : 제곱근 만약 12에 대하여 소수를 판별하려고 합니다. 12의 약수는 1, 2, 3, 4, 6, 12를 가집니다. 가장 간단한 방법처럼 12를 2부터 N-1까지 나누어보려고 할 때 2* 6 = 6 * 2의 성질을 이용한 방법입니다. (xy = yx) 제곱근을 기준으로 제좁근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 ..
-
외판원 순회(TSP : Traveling Salesperson Problem) 알고리즘알고리즘/알고리즘 2022. 3. 21. 00:16
외판원 순회란? 도시들이 존재하며 도시로 이동할 때 드는 비용이 주어졌을 때 불특정 한 도시에서 출발하여 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원이 가장 적은 비용으로 모든 도시를 방문하면서 자기 집으로 돌아온다고 하여 외판원 순회라는 이름이 붙었습니다. 이 문제의 특징은 비트 연산, DFS, DP를 모두 활용해서 해결해야 합니다. 만약 해당 개념을 활용하지 않고 가장 일반적으로 떠오르는 '각 도시를 잇는 모든 경로를 탐색하고 그중 최솟값을 찾자'라는 완전 탐색으로 푸는 방법도 있지만 이는 O(N!)의 시간 복잡도로 인해 시간 초과가 발생할 수 있습니다. 만약 0번째 도시에서 출발하고 남은 도시들을 어떤 순서로 방문할지만 정하면 되기 때문에 남은 n-1..
-
다익스트라(Dijkstra) 알고리즘알고리즘/알고리즘 2022. 3. 17. 18:44
다익스트라 알고리즘이란? DP를 활용한 최단 경로 탐색 알고리즘입니다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 이때 음의 간선은 포함할 수 없습니다. 다익스트라 알고리즘이 DP 문제인 이유는 ' 최단거리는 여러 개의 최단 거리로 이루어져 있기 때문입니다.' 예제 1 예를 들어 다음 그림과 같이 1번 노드부터 다른 노드로 가는 최단 경로를 구한다고 가정해 보겠습니다. 우선 1번 노드와 인접한 2번, 3번, 4번 노드 간의 최단 거리를 구합니다. 경로 1 -> 2의 비용은 3 경로1 -> 3의 비용은 6 경로1 -> 4의 비용은 7 이후, 1번 노드와 인접하면서 가장 비용이 적은 2번 노드를 방문합니다. 경로1 ->3의 비용은 원래 6이었는데 2를 경유해서 가는 경우 4로 ..
-
세그먼트 트리란?알고리즘/알고리즘 2022. 3. 13. 15:39
세그먼트 트리란? 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하기 위한 자료구조입니다. 배열에서 특정 구간의 합을 가장 빠르게 구하기 위한 방법은 무엇일까요? 예시 데이터 : 5 8 7 3 2 5 1 8 9 8 7 3 여기에서 인덱스 1부터 10까지 데이터의 합을 구하려면 어떻게 할 수 있을까요? 간단하게 인덱스 1부터 10까지 데이터를 다 더해준다면 데이터의 개수에 의존하여 O(N)의 시간 복잡도가 나옵니다. 이것을 트리 구조를 이용해서 구한다면 O(logN)의 시간복잡도로 부분합을 구할 수 있습니다. 다음 그림을 보면 조금 더 이해하기 쉽습니다. 이처럼 더한값을 다시 재사용하면서 최종적으로 0~14의 연산 결과를 얻기 때문에 O(logN) 시간을 보장합니다. Segment..
-
Upper_bound와 Lower_bound란?알고리즘/알고리즘 2022. 3. 10. 09:26
어떤 리스트에서 이분 탐색을 이용하여 특정 값을 찾을 때, 리스트가 중복된 값을 포함하고 있을 때 중복 값들을 전부 찾거나 또한 그 중복값들을 활용해서 문제를 해결하기 위해서 lower_bound, upper_bound를 사용하면 특정 target number 보다 크거나 같은 첫 번째 원소 인덱스, target number보다 큰 첫번째 원소의 인덱스를 찾을 수 있습니다. 이진 탐색을 이용하기 때문에 리스트는 항상 정렬되어 있어야 합니다. hashFunction을 이용하여 중복된 값들의 개수를 탐색하면 O(1)이라 훨씬 더 빠르게 탐색할 수 있을 것 같은데..?라는 생각이 들긴 합니다. 하지만 특정 구간의 범위를 지정하기 위해서는 유용하게 사용할 수 있을 것 같습니다. upper_bound 범위 [be..
-
반복과 재귀(Iteration, Recursion)알고리즘/알고리즘 2022. 3. 2. 00:01
반복문과 재귀의 공통점 반복은 (for / while) 문을 통하여 작업이 완료될 때까지 계속 반복합니다. 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법입니다. 반복문과 재귀를 통하여 유사한 작업을 수행할 수 있습니다. 반복문은 어떤 기준으로 반복할 것인가를 찾아내는 것이 중요하고, 이는 재귀 함수의 구현부를 의미합니다. 재귀 함수는 구현부를 통해 자기 자신을 호출하고 반복하게 됩니다. 반복문은 조건을 통해 반복문을 탈출하고, 재귀 함수도 특정 조건 시에 return을 통해 반복을 탈출합니다. 재귀 함수란? - 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수 - 기본 부분(basis part)과 유도 파트(inductive part)로 구성된다. (기..
-
자바 순열과조합알고리즘/알고리즘 2022. 3. 1. 00:01
순열 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현합니다. nPr A B C 중 2개를 뽑는다고 한다면 결과는 아래와 같습니다. A, B A, C B, A B, C C, A C, B 순열은 이처럼 AB와 BA // AC와 CA // BC와 CA를 다른 경우의 수로 봅니다. 만약 AB = BA가 성립한다면 순서가 의미 없기 때문에 이는 순열이 아니라 조합으로 접근해야 합니다. 프로그래밍적으로 접근해보자면 A를 뽑는다면 A는 더 이상 뽑지 못하고 다음 후보로는 (B, C)가 올 수 있습니다. 만약 다음 후보에 B, C 어떤 것이 뽑히던 2개를 뽑았기 때문에 끝나게 됩니다. 따라서 처음에 올 수 있는 후보는 3가지 (A, B, C) 그다음 ..