본문 바로가기

알고리즘

 (405)
구간 트리. [2517] [1. 문제 설명] https://www.acmicpc.net/problem/2517 [2. 풀이 접근] 첫번째 좌표 압축 실력이라는 값은 10억 이하의 값이다. 그러나 주어지는 데이터 개수는 최대 50만개 이다. 또, 고유한 값으로 주어지므로, 좌표 압축을 통해 현실적인 메모리에서 각 실력의 순위를 확인 할 수 있다. iterate 순서 꼴지부터 iterate 해서, 자신 보다 앞에 있으면서 낮은 실력을 갖는 사람의 수를 구하기 => 이 방식으로 하면, 구간 트리를 먼저 만들고, => 구간 트리에서 낮은 순위에 있는 사람의 실력을 점차적으로 제거해나가야 한다. 1등부터 iterate 해서, 자신 보다 앞에 있으면서 낮은 실력을 갖는 사람의 수를 구하기 => 이 방식으로 하면, empty 한 구간 트리에..
구간 트리. [7578] [1. 문제 설명] https://www.acmicpc.net/problem/7578 [2. 풀이 접근] 구간 트리 작성 시 실수했던 부분 update() 시, index 가 이번 구간을 벗어나는 경우, 현재 노드에 저장되어 있는 값을 그대로 반환해야 한다. query() 와 다른 부분 해결 과정 앞에서 부터 순서대로 확인해왔다고 가정하고 351번 기계 (A index 상 4번째) 가 추가됨으로 인해 교차되는 개수를 구할 때, 351번 기계가 B 에 위치한 곳에서 마지막 구간까지, 존재하는 index 개수를 전체 결과에 더하면 된다. [3. 코드]
구간트리. [2243] [1. 문제 설명] https://www.acmicpc.net/problem/2243 [2. 풀이 접근] 전체 사탕 중, N 번째 순위의 사탕의 맛 정도를 출력해야 한다. 1번째 사탕 3개, 3번째 사탕 2개가 있다고 하면, 1, 1, 1, 3, 3 사탕이 있으므로, 3번째 2번째 순위의 사탕은 1번 사탕이 되는 것이다. 사탕 상자에는 1번 사탕, 3번 사탕, 총 2종류의 사탕이 있어서, 3번 사탕이 되는 것이 아니다,. [3. 코드]
트라이. [14725] [1. 문제 설명] https://www.acmicpc.net/problem/14725 [2. 풀이 접근] [3. 코드]
우선순위 큐. [11003] [1. 문제 설명] https://www.acmicpc.net/problem/11003 [2. 풀이 접근] A[i] 부터 이전 L 개 원소 중 최소 값을 출력하는 문제이다. 우선순위 큐를 이용해서, 최근 L 개 중 최소 값을 구하고, L+1 이전 원소는 제거해야 한다. 그러나 힙에 담긴 원소를 제거 할 수는 없으므로, 각 원소의 아이디에 대해서 탐색 범위에 있는지 없는 지를 체크하고, 최소 값을 선택하는 구간에서, 현재 힙에 최소에 해당하는 값의 아이디가 탐색 범위 밖에 있다면, 힙에서 pop 하고, 다름 최소를 확인해보는 방식으로 구현하면 된다. [3. 코드]
트라이 - 예제 [1. 문제 설명] https://algospot.com/judge/problem/read/SOLONG [2. 풀이 접근] [3. 코드]
문자열 - 트라이 [1. 개요] 트라이(trie) 는 문자열의 집하을 표현하는 트리 자료구조로 M 이 모든 문자열의 최대 길이일 때. 원하는 원소(문자열)를 O(M) 시간내에 찾을 수 있다. 트라이의 루트는 항상 길이 0인 문자열에 대응 되며 노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1 씩 늘어난다. 특성 종료 노드는 해당 위치에 대응되는 문자열이 트라이가 표현하는 집합에 포함되어 있다는 것을 의미한다. 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻는다. 각 노드에 대응되는 문자열을 저장하지 않는다. [2. 트라이 노드] 트라이 노드는 보통 다음과 같이 구성된다. 자손 노드를 가리키는 포인터 목록 => 입력에 등장 할 수 있는 모든 문자에 대응되는 원소를 갖는..
우선순위 큐. [11000] [1. 문제 설명] https://www.acmicpc.net/problem/11000 [2. 풀이 접근] 탐욕법 문제 중 회의실 배정 문제랑 비슷해 보여서, 먼저 종료되는 강의 순서대로 배치해보려 했는데, 회의실 배정 문제와 결정적인 차이가 있었다. 회의실 배정 문제는 서로 겹치지 않는 회의들만 골라서 최대한 많이 선택하는 것이고, 이 문제는 시간이 겹치더라도 선택 할 수 있기 때문이다. 시간이 겹치면 새로운 강의실을 배정한다. 아래와 같은 시간표가 있을 때 먼저 {시작시간, 종료시간} 순서대로 정렬한다. 이번 강의의 시작시간이 이제 가장 먼저 종료되는 강의 뒤에 올 수 있다면, 해당 강의 뒤에 연달아 강의를 배치하면 되고, 없으면, 새로 강의실을 만들면 된다. [3. 코드]
접미사 배열 - 예제1 [1. 코드]
문자열 - 접미사 배열 [1. 개요] 접미사 배열은 굉장히 다양한 문자열 문제를 푸는 데 사용 할 수 있으며, 이 자료구조는 아래와 같은 데이터를 표현한다. 어떤 문자열 S 의 모든 접미사를 사전순으로 정렬 이때, 배열에 실제로 저장하는 것은 각 접미사의 시작 위치이다. 예를들어, A[i] = 7 일 때, S[7...] 을 표현하는 것이다. 그래서 이 자료구조를 이용하여 아래와 같은 문제를 해결 할 수 있다. 문자열 검색 찾고자 하는 "문자열 N" 이 "문자열 H" 의 어떤 접미사의 접두사라는 점을 이용한다. H 의 접미사 배열을 이진 탐색하여, 문자열 N 이 출현하는 위치를 찾을 수 있다. [2. 접미사 배열 생성] 접미사 배열을 생성하는 가장 단순한 방법의 시간복잡도는 O(n^2logn) 으로, 일반적인 경우에서는 이 보다..

티스토리툴바