SY DevLog

어떤 문자열(T)에서 특정 문자열(P)를 찾을 때 사용하는 알고리즘 예를 들어, 문자열(T) : "CDABABKABADABABC" 문자열(P) : "ABABC" 문자열 T에서 문자열 P를 찾는 방법을 단순하게 완전탐색으로 구현해보면 이중 for문을 통해 다음과 같이 구현해 볼 수 있다. String T="CDABABKABADABABC" String P="ABABC" for(int i=0;i pattern과 pattern의 비교 text와 pattern을 비교한 것과 마찬가지로 pattern과 pattern의 비교도 비슷한 방식으로 이루어진다. 따라서 pattern과 pattern을 비교하는 알고리즘을 이해하고 나면, text와 pattern을 비교하는 알고리즘도 이해하기가 쉬울 것이다. 우선 건너뛰기 표..

동적 계획법(Dynamic Programming) 동적 프로그래밍, 다이나믹 프로그래밍 이라고도 한다. 동적 계획법이란 하나의 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이다. 동적 계획법에서 가장 중요한 개념은 메모이제이션(Memoization)과 점화식이다. 메모이제이션(Memoization) : 동일한 계산이 반복될 때, 이전에 계산한 결과를 메모리에 저장하여 동일한 계산을 반복하는 것을 피하는 방법이다. 이전에 계산한 결과를 메모리에 저장하기 때문에 중복된 계산을 할 필요가 없으므로 속도가 빠르다는 장점이 있다. 그리고 동적 계획법에서는 이 메모이제이션을 위해 점화식을 세우는 과정이 필요하다. 동적 프로그래밍하면 가장 대표적인 예시가 바로 피보나치 수열이다. 피보나치 수열은 앞의 두 항의..

Disjoint Set(분리집합)이라고도 한다. 서로 중복되지 않는(교집합이 없는) 둘 이상의 집합의 정보를 저장, 조작하는 자료구조이다. 유니온 파인드는 3가지 연산이 존재한다. make - set(x) : 초기화를 하는 연산이다. x를 원소로 하는 새로운 집합을 생성한다. 이때 생성되는 집합은 x만을 원소로 갖는다. union(x, y) : x가 포함된 집합과 y가 포함된 집합을 하나의 집합으로 합친다. find(x) : x가 어느 집합에 속해 있는지를 찾는다. 유니온 파인드를 구현하는 방법은 다양한데, 그 중에서도 가장 잘 알려진 트리를 이용한 방법을 설명할 것이다. 트리를 이용한 Union-Find 트리를 이용하여 유니온 파인드를 구현할 경우, 하나의 트리는 집합 1개를 의미하며 트리의 루트 노드..

비트마스크(BitMask) 이진수 표현을 자료구조로 사용하는 기법이다. 하나의 비트에서 나타낼 수 있는 경우의 수는 0 혹은 1 두가지가 있다. 보통 비트마스크를 이용하는 경우에 0이면 false, 1이면 true를 나타내며, 특정 집합에서 원소의 포함 여부를 표현할 때 사용한다. 비트단위로 정보를 처리하기 때문에 메모리를 적게 사용할 뿐만 아니라 수행 속도가 빠르다는 장점이 있다. 비트 연산 비트마스크는 비트 연산을 이용하여 집합 내의 원소를 다룰 때 주로 사용된다. 예를 들어, 0부터 9까지 넣을 수 있는 어떠한 집합 S가 존재하고 그 집합 내에 들어있는 원소가 0,1,2 이라고 하자. 만약 배열로 이를 표현한다고 하면, 10개의 크기를 가지는 boolean 배열을 생성하고, arr[0] = true..

플로이드 워셜 알고리즘 그래프에서 모든 정점들 간의 최단거리를 구하는 알고리즘 다익스트라 알고리즘 비교 다익스트라 알고리즘은 하나의 시작 정점을 정해서 다른 모든 정점까지의 최단경로를 구한다. 반면에 플로이드 워셜 알고리즘은 모든 정점을 시작 정점으로 했을 때의 최단경로를 구한다. 따라서 정점 간의 모든 최단거리를 구할 경우에는 플로이드 워셜 알고리즘을 사용한다. 다익스트라 알고리즘은 가중치가 음수인 경우에는 사용할 수 없다. 플로이드 워셜 알고리즘은 가중치가 음수라도 사용이 가능하다. 플로이드 워셜 알고리즘에 대해 먼저 간단히 설명하면 이렇다. 플로이드 워셜 알고리즘에서 시작정점(s)와 도착정점(e)간의 최단거리를 구할 때, 경유하는 정점(t)에 관한 개념이 등장한다. 경유하는 정점(t)이란, 말그대로..

이번 글은 이분 탐색을 사용하는 알고리즘 문제를 좀 더 쉽게 풀기 위해 작성한 것이다. 대부분의 이분 탐색을 사용하는 문제는 특정 값을 찾는 문제보다도 주어진 조건을 만족하는 수 중에서 최대값을 찾거나, 최소값을 찾는 문제가 자주 등장한다. 무엇을 구하는 문제이냐에 따라서 이분 탐색에서 최종 반환하는 인덱스가 약간씩 달라진다. 특정값을 찾는 문제 최대값을 찾는 문제 최소값을 찾는 문제 아래 글은 기본적인 이분 탐색에 대한 개념을 정리한 것이다. 이분 탐색(Binary Search) - 특정값 찾기 이분 탐색(Binary Search) 정렬된 배열에서 특정 값을 검색할 때 사용하는 알고리즘 탐색을 진행하기 전에 반드시 배열이 정렬된 상태이어야 한다. 이분탐색 알고리즘 문제를 풀 때, 주어진 배열에 lotu..

이분 탐색(Binary Search) 정렬된 배열에서 특정 값을 검색할 때 사용하는 알고리즘 탐색을 진행하기 전에 반드시 배열이 정렬된 상태이어야 한다. 시간복잡도 : O(logN) 한번 탐색을 진행할 때마다 탐색의 범위가 반으로 줄어들기 때문에 선형 탐색에 비해 속도가 빠르다. 알고리즘 : 1. 이분 탐색 범위의 시작 위치를 가리키는 포인터를 pl, 마지막 위치를 가리키는 포인터를 pr로 설정한다. 그리고 탐색 범위의 가운데를 가리키는 포인터를 pc로 설정한다. arr[pc] = key 이면, 탐색하려는 값을 찾았으므로 이분탐색을 종료한다. arr[pc] pl = pc + 1 arr[pc] > key 이면, pr을 pc보다 하나 왼쪽으로..

저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그 수열에서 가장 긴 증가하는 부분 수열을 구하는 알고리즘 (최장 증가 수열의 요소가 꼭 연속하지 않아도 됨) 1. 최장 lotuslee.tistory.com 이분탐색을 이용하여서 새로 입력받은 수가 리스트에 들어갈 위치를 구하였다. 그러나 이 알고리즘은 최장 증가 수열의 길이를 구할 수는 있지만 수열 자체를 구할 수는 없었다. (위의 포스팅 참고) 예를 들어, 다음과 같은 반례가 있다. 수열 10 30 50 20 60 이 있다고 할 때 위의 알고..

트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 위의 글에서는 트라이 개념, 트라이 노드 특징(Map, isLastChar)에 대해 설명했었다. 이번에는 트라이(Trie)의 동작 1. 단어 삽입 2. 단어 포함 여부 3. 단어 삭제 에 대해서 자세하게 다룰 것이다. 트라이 위의 트라이 그림에서 포함되어 있는 단어는 "bird", "big", "beer", "girl", "god", "grow" 여섯 가지이다. 트라이노드(TrieNode)의 클래스는 아래와 같이 구현할 수..

트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 시간복잡도 : O(m) (m은 문자열 길이) 트라이 예 트라이(Trie) 특징 트라이(Trie) 노드 특징 1. 트라이의 각 노드는 문자와 자식 노드를 맵 형태로 가지고 있다. -> Map 예를 들어, 루트노드의 경우, 자식노드가 2개이므로 Key가 'b' 이고, Value에 왼쪽 자식 노드를 가지고 있으며, Key가 'g' 이고, Value에는 오른쪽 자식 노드를 가지고 있다. 루트의 왼쪽 자식 노드도 마찬가지이다. 이 노드는 그림에서 보면 'b'를 가지고 있는 것처럼 보이지만, 사실은 특정 문자를 가지고 있는 것..