코딩스토리

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 23장 우선순위 큐와 힙에 나온 내용을 바탕으로 작성하였습니다. 개요 우리는 기존에 "큐(Queue)"라는 자료구조를 배웠었다. 큐는 스택과 비슷한 자료구조로 '선입선출'이라는 형태를 갖추고 있다. 그렇다면 우선순위 큐와 큐의 차이점은 무엇일까? 바로 '우선순위', 즉 선입선출 구조이나 '우선순위'대로 원소를 꺼낼 수 있다는 점이다. 우선순위를 만족하게 정렬하려면 여러가지 방법이 있다. 가장 단순한 방법은 O(n)이라는 시간에 모든 원소를 비교해서 정렬할 수 있다. 하지만 당연히 이 방법은 사용하지 않을 것이다. 이진 탐색 트리(Binary Search Tree)를 사용하면 O(logn)의 시간에 정렬할 수 있지만 이는 책의 표현을 빌려 쓰자면 "닭 ..

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 이전에 KMP알고리즘에 대해 알아 보았었다.그럼에도 문자열 문제는 쉽지 않다. 가장 최근 2020 카카오 코딩 테스트를 보면 문자열 문제가 시작부터 연달아 나옴을 알 수 있다. 그만큼 중요하면서도 어려운 유형이다. 이번에는 접미사를 통해 문자열 알고리즘을 좀 더 확장시켜 보려고 한다. 1. 접미사 배열 문자열을 다룰 때 빼놓을 수 없는 자료구조로 접미사 배열이 있다고 한다. '문자열의 맥가이버 칼' 이라고도 부른다는데 한번 공부해 보도록 하자. 먼저 접미사 배열은 말 그대로 한 문자열의 모든 접미사들을 사전 순으로 배열에 저장해 놓은 것을 말한다. 이때 접미사들을 그대로 저장하면 문자열의 길이..