정리 노트

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 크기가 N인 집합에 속한 원소들만 담은 스트림이 있다고 합시다. 이 스트림에서 서로 다른 원소들의 개수를 구하려면 집합을 만들어 스트림의 모든 아이템을 집합에 넣으면 됩니다. 집합은 동일한 아이템을 원소로 가지지 않기 때문에 이를 통해 쉽게 찾을 수 있습니다. 하지만 생성해야 할 집합의 크기가 너무 커져 메모리에 올릴 수 없는 정도라면 어떻게 찾아야 할까요? Flajolet-Martin(ver. 1) Flajolet-Martin 알고리즘을 통해 이를 대략적으로 구할 수 있습니다. 이 알고리즘을 위해 아이템을 \(..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 0과 1로만 이루어져 있는 bit들의 stream이 입력으로 들어오는 상황에서 최근 들어온 k개의 bit 중 1의 개수를 구해야 하는 상황이 있다고 합시다. 가장 쉽게 생각할 수 있는 방법은 최근 k개의 bit들을 저장해서 개수를 세는 방법입니다. 새로운 bit가 들어오면 가장 예전의 bit를 버린다면 스트림으로 들어오는 입력에서 1의 개수를 셀 수 있을 것입니다. 자료구조 queue를 사용한다면 어렵지 않은 해결책입니다. 하지만, 저장해야 할 bit 용량이 너무 커서 메모리에 담을 수 없다면 어떻게 해야 할까요..

이번 글에서는 DFA(Determistic Finite State of Automaton)을 이용해 문자열 안에서 특정 패턴을 찾는 방법에 대해 적어보겠습니다. Naive 한 방법 DFA로 들어가기 전에 왜 DFA를 써야 하는지 느끼기 위해 naive 하게 찾는 방법부터 보겠습니다. 예를 들어 문자열 "BLUERED"이 있고, 여기서 패턴 "RED"을 찾는 문제를 푼다고 합시다. RED를 찾는 가장 naive 한 방법은 하나하나 다 살펴보는 것입니다. 이렇게 하나하나 체크해서 패턴을 찾을 수 있습니다. 하지만 이렇게 찾는다면 시간이 오래 걸립니다. 문자열의 길이를 N, 패턴의 길이를 M이라고 한다면, time complexity는 O(NM)이라 표현할 수 있습니다. 그리고 이러한 방법은 매번 불일치가 일..

이 글은 저번에 적었던 글에 이어서 진행됩니다. 2022.12.10 - [개념 정리/알고리즘] - Heap 정렬(Heap Sort) - Heap 만들기 Heap 정렬(Heap Sort) - Heap 만들기 힙 정렬의 과정 Heap 정렬이 일어나는 과정은 크게 두 단계로 나눠서 볼 수 있습니다. 입력으로 받은 배열을 Heap으로 만드는 과정 만들어진 Heap을 가지고 정렬하는 과정 이번 글에서는 첫 번째 과 study-note-99.tistory.com Heap 정렬하기 Heap을 정렬하는 단계에서는 아래와 같은 과정을 거치게 됩니다. heap에서 최댓값(max heap인 경우) 또는 최솟값(min heap인 경우) 제거 => 루트 노드 제거 heap의 가장 마지막 원소를 root 노드로 복사 root 노..

힙 정렬의 과정 Heap 정렬이 일어나는 과정은 크게 두 단계로 나눠서 볼 수 있습니다. 입력으로 받은 배열을 Heap으로 만드는 과정 만들어진 Heap을 가지고 정렬하는 과정 이번 글에서는 첫 번째 과정인 heap을 만드는 과정에 대해 적겠습니다. 입력이 {0, 7, 2, 5, 3, 1, 6}(0은 인덱스 1부터 맞춰 적기 위해 끼워 넣은 의미 없는 값)과 같이 들어왔다고 할 때, heap이 만들어지는 과정을 봅시다. 힙 만들기(Heap Construction) Heap 정렬을 하기 위해서는 먼저 입력받은 배열을 heap 구조를 따르게 재구성해야 합니다. 오름차순으로 정렬하는 것을 목적으로 한다면 max heap으로 구성해야 합니다. 현재 입력받은 배열의 상황은 아래와 같습니다. Heap의 구조를 만들..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! Backtracking이란? Backtracking(백 트래킹)은 해답을 구할 수 없는 경우가 나온 경우, 더 진행하는 것을 포기하고 이전 상태로 되돌아가서 다른 경우를 찾는 방법을 말합니다. 흔히 생각할 수 있는 예시가 '미로 찾기'입니다. 미로를 빠져나가는 방법들 중에서 가장 많이 알려진 방법이 '우수법' 입니다. 오른손으로 한쪽 벽을 짚으면서 걸으면 무조건 미로를 빠져나갈 수 있는 방법입니다. https://youtu.be/YS4ng_vKr7o?t=89 우수법으로 나아가는 과정이 백트래킹과 같다고 생각이 됩니다. 위와 같은 ..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 동적 계획법 동적 계획법은 분할 정복 기법으로 문제를 해결하는 방식과 유사합니다. 분할 정복 기법에 대해 모르시는 분들은 제가 저번에 적은 포스트를 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 동적 계획법도 하나의 문제를 여러 작은 문제들로 나눈 다음, 각 문제들의 해답을 이용해서 원래 문제의 답을 구합니다. 분할 정복 기법과의 차이점은 여러 작은 문제들의 연관성입니다. 예를 들어, 병합 정렬이나 퀵 정렬을 구현할 때 나눠지는 배열들은 서로 상관이 없습니다...

이 글은 제가 저번에 적은 글에 이어서 작성하는 글입니다. 그러니 이전 글을 읽고 이 글을 읽어주시기 바랍니다. 2022.10.22 - [개념 정리/알고리즘] - 퀵 정렬(Quick Sort) (with Lomuto) 두 번째 Partiton 방법 이번에 소개하는 partition 방법은 Hoare가 제시한 방법입니다.(사실 퀵 정렬 알고리즘을 제안한 사람이 Hoare입니다.) 이번 partition도 pivot 값을 배열의 가장 왼쪽 값으로 정하고 시작합니다. i와 j의 초기값은 각각 -1, 배열의 길이로 배열의 양 끝을 지정하는 인덱스입니다. 먼저 i의 값을 하나 증가시키고 i번째 원소가 pivot값보다 작으면 다시 i값을 늘려줍니다. 이 과정을 배열의 i번째 값이 pivot보다 크거나 같을 때까지 ..