Algorithm/이론 문자열 검색 - 브루트 포스, KMP, Boyer-Moore 문자열을 검색하는 알고리즘을 알아보자. 문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어있는지를 조사하고 들어 있다면 그 위치를 찾아내는 것을 말한다. 예제를 설명할 때는 편의상 어떤 문자열의 문자를 말할 때 원래는 string.charAt(idx)라고 해야 하지만 string[idx]라고 쓰겠다. 브루트-포스법 브루트 포스법으로 문자열을 검색하는 과정은 아래와 같다. 텍스트 "ABABCDEFGHA"에서 "ABC"를 찾는다고 가정했을 때, 다음과 같은 과정을 거치게 된다. 3번에서 4번으로 넘어가는 과정을 보면, 패턴의 문자와 다른 문자를 만나면 패턴을 1칸씩 뒤로 옮긴 다음 다시 패턴의 처음부터 비교하는 모습을 볼 수 있다. 이미 검사를 진행한 위치를 기억하지 못해 불필요한 검사를 진행하기 때문에 .. 더보기 BFS(너비우선탐색)와 DFS(깊이우선탐색) 알고리즘을 공부하다가 꼭! 알아야하는 너비우선탐색과 깊이우선탐색에 대해 알아보고자 한다. 자료구조-트리 포스트에서 가볍게 훑어보고 넘어갔었는데, 알고리즘 문제에 적용하기 위해서는 더 알아볼 필요가 있다. 특히나 검색하면서 마이구미님의 Hello World 블로그에 이 이론들을 어떻게 문제에 적용시켜 풀지 생각하는데 도움이 많이 됐다. 링크로 가기 👉 마이구미의 Hello World 그래프(Graph) 연결되어 있는 객체 간의 관계를 표현하는 자료 구조이며 비선형 자료구조이다. 정점(vertex)과 두 노드를 연결하는 간선(edge)으로 이루어져있다. 부모-자식 관계라는 개념이 없으며 2개 이상의 경로가 가능하다. 계층이 없기 때문에 루트라는 개념도 존재하지 않는다. 또, 순환 구조일 수도 있고, 비순환 .. 더보기 자료구조 - 이진트리와 이진검색트리 이진트리(binary tree) 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다. 이때 각 노드의 자식은 2명 이하만 유지해야 한다. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 완전이진트리(complete binary tree) 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 한다. 1. 마지막 레벨을 제외한 레벨은 노드를 가득 채운다. 2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다. 높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^k+1 - 1개이다. 따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n이.. 더보기 자료구조 - 트리(tree) BFS와 DFS에 대해서 알아보기 이전에 먼저, 트리라는 자료 구조에 대해 알 필요가 있다. 아래의 내용은 이지스퍼블리싱의 Do it! 자료구조와 함께 배우는 알고리즘입문 책을 참고하여 재구성하였다. 트리(tree) 데이터 사이의 계층 관계를 나타내는 자료 구조이다. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지를 통해 다른 노드와 연결되어 있다. 트리 관련 용어 루트(root): 트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 한다. 하나의 트리에는 하나의 루트가 있다. 리프(leaf): 트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라고 한다. 이때 '가장 아랫부분에 위치한다'라는 말은 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라 더 이상 뻗.. 더보기 유클리드 호제법(Uclidean algorithm) 최대 공약수란? 주어진 정수들의 공통된 약수들 중 가장 큰 약수를 말한다. 최대공약수를 구하는 방법은 소인수 분해와, 유클리드 호제법이있다. 두가지 방법으로 192와 72의 최대 공약수를 구하는 방법을 살펴보자. 소인수 분해 소인수 분해로 구할 때는 먼저 주어진 수들을 각자 소인수 분해한다. 그 후에 중복되는 부분을 서로 곱해주면 최대 공약수를 구할 수 있다. 192 = 2^6 * 3 = 2 * 2 * 2 * 2 * 2 * 2 * 3 72 = 2^3 * 3^2 = 2 * 2 * 2 * 3 * 3 이때, 중복되는 2^3 * 3 = 2 * 2 * 2 * 3 = 24로 두수의 최대 공약수는 24이다. 유클리드 호제법 유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법이며 소인수 분해보다 훨씬 빠.. 더보기 자료구조 - 스택과 큐(Stack and Queue), 링버퍼(Ring buffer) 스택(Stack) 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다(가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.). 스택에 데이터를 넣는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 이때, 푸시와 팝을 하는 위치를 꼭대기(top)이라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. 스택의 push와 pop은 꼭대기 top자리에서만 이루어지므로 복잡도는 O(1)이다. 큐(Queue) 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 스택과 다르게 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, Fisrt In F.. 더보기 검색 알고리즘 - 선형 검색, 이진 검색 검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다. 알고리즘에 들어가기 앞서, 복잡도에 대해 알아보자. 복잡도 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다. 시간 복잡도(time complexity): 실행에 필요한 시간을 평가한 것 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것 선형 검색(linear search) 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다. [검색이 종료되는 종료 조건.. 더보기 Sieve of Eratosthenes(에라토스테네스의 채) 들어가기에 앞서, 중1 때 배웠던 소수와 합성수에 대해서 잠깐 알아보면 더 이해가 잘 될 것이다. 소수와 합성수 1보다 큰 모든 정수는 소수이거나 합성수이다. 소수는 1과 자기 자신으로 밖에 나누어 떨어지지 않는 수이다. (두 개의 약수만 가지고 있다.) 합성수는 1과 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수를 의미한다. (두개 이상의 약수를 가지고 있다.) 따라서 1은 소수도 합성수도 아니다. Sieve of Eratosthenes(에라토스테네스의 채) 간단하게 말하면, 1부터 어떤 수 N까지의 범위에서 소수들을 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였으며, 구하는 방법이 마치 채에 거르는 것과 같아 '에라토스테네스의 채'라고 불린다. 알고리즘은 아래의 이미지를.. 더보기 Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘) 오늘도 어김없이 Codility의 문제를 풀다가, brutal force로 풀기는 정말 싫은데 도저히 다른 방법이 떠오르지 않아서 검색하다가 발견한 알고리즘에 대해 글을 써보려 한다. 검색을 해보니 Kadane's Algorithm에 대한 설명을 정말 잘 해준 포스트가 있었다. 포스트로 가기 👉 Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work? 유튜브 비디오 보기 👉 https://www.youtube.com/watch?v=86CQq3pKSUw 위의 포스트와 비디오를 기반으로, Kadane's Algorithm이란 무엇인가를 설명하고자 한다. 우선, 다이나믹 프로그래밍에 대해서 집고 넘어갈 필요가 있다. 다이나믹 프로그래밍이란?.. 더보기 이전 1 다음