본문 바로가기

알고리즘

 (405)
우선 순위 큐 - 예제 1 [1. 문제 설명] 수열에 새로운 수가 추가 될 때 마다 수열 내 중간 값들의 합을 출력한다. [2. 풀이 접근] 수열의 중간 값은 정렬 된 수열 내 중앙에 오는 값이며, 수열의 길이가 짝수 개인 경우 둘 중 더 작은 값이다. 원소 추가 때마다 정렬을 하면 N2LogN 이므로 시간초과가 발생한다. maxHeap 에는 정렬된 수열의 왼쪽 값들이 저장되고 minHeap 에는 정렬된 수열의 오른쪽 값들이 저장된다 하면 중간 값은 maxHeap 의 root 와 minHeap 의 root 사이에 존재하게 된다. 수열의 길이가 홀수 개인 경우와 (empty 인 경우 최대 힙의 root 가 중간 값이 된다.) 짝수 개인 경우 더 작은 값이 중간 값이 되는 특성을 이용하여 중간 값 까지 최대 힙에 저장하도록 한다. 여..
스위핑. [2836] [1. 문제 설명] 0번 위치에서 M번 위치까지 가려고 하는데, 이 사이에 A 위치에서 B 위치로 이동하려는 사람들을 운송해야 할 때, 이동해야 하는 최소거리를 구한다. [2. 풀이 접근] A B 인 경우로 운송자가 가려는 방향과 반대되는 경우이다. 검정색 화살표는 운송자가 이동하는 방향이고 빨간색 화살표는 승객이 이동하려는 방향이다. 이 빨간색 화살표들을 최소 거리로 이동하면 된다. 2번 승객을 처리하고, 3번 승객을 처리하고, 마지막으로 1번 승객을 처리하는 것이 아니라 1번 승객을 먼저 처리하고, 2번 승객을 태우고, 3번 승객을 태운 다음 3번 승객을 먼저 내리고 2번 승객을 먼저 내리게 하면 된..
스위핑. [2170] [1. 문제 설명] 선을 여러번 그었을 때, 그어진 선의 총길이를 구한다. 중복되어 그어진 구간은 한번만 계산해야 한다. [2. 풀이 접근] 단순한 풀이로는 절대 시간내 해결 할 수 없다. 겹치는 구간등을 확인해야 할 때, 그 범위가 너무 넓기 때문이다. (문제 입력 상 구간의 최대 길이는 20억) 그림을 좀 그리다보면 풀이에 대한 실마리가 조금 잡힌다. // 여기에 그림이 필요.. 즉, 모든 구간을 X 를 기준으로 정렬 하면, 순차적으로 탐색하다보면 X 를 시작으로 하여 선을 그었을 때 겹쳐지는 최대 구간을 알 수 있다. => 자신보다 뒤에오는 구간의 시작 점은 자신보다 앞에 위치 할 수 없다. => 지금까지 업데이트 한 구간 내에 있거나, 그 구간을 좀 더 확장시키거나, ... 여기서 중요한 점은 새..
구간 트리. [1168] [1. 문제 설명] 1 부터 N 까지 나열 된 원이 있을 때, 순서대로 K 번째 값을 제거 했을 때 제거되는 순서를 출력한다. [2. 풀이 접근] 기본적인 전략은 아래 문제와 동일하다. https://testkernelv2.tistory.com/412 간단히 다시 정리하면 구간에 속한 원소의 개수를 알 수 있으므로, logN 시간복잡도로 남아 있는 수열에서 k 번째 숫자를 찾는 것이다. 여기서 문제는 수열이 원형 형태라는 것이다. 예제 입력을 토대로 동작 방식을 살펴보면, (N=7, K=3) ▼ [1][2][3][4][5][6][7] ▼ [1][2][4][5][6][7] # 이전 위치를 기준으로 3번째 원소 ▼ [1][2][4][5][7] # [1][2][4][5][6][7][1][2][4][5][7] ..
treap https://testkernelv2.tistory.com/413
이진 트리 - 예제 2 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
구간 트리. [12899] [1. 문제 설명] 아래 쿼리를 수행하는 프로그램을 작성한다. A. 수열 S 에 자연수 X 를 추가한다. (append) B. 수열 S 에 포함된 숫자 중 X 번째로 작은 수를 출력하고, 수열에서 제거한다. [2. 풀이 접근] 간단한 풀이를 생각해보면, 트립(treap) 의 적용을 생각해 볼 수 있다. 트립을 통해 원소의 삽입과 삭제를 logN 에 할 수 있다. 또한 K번째 원소도 쉽게 찾을 수 있다. 그러나 구현이 살짝 까다로울 수 있으니, 나중에 다시 정리해보도록 하고, 구간 트리를 사용하여 풀이를 해볼 수 있다. 자연수 X 의 범위는 1 이상 2,000,000 이하이므로, 구간을 [1, 2,000,000] 을 하는 구간 트리를 생각 해 볼 수 있다. 각 노드가 저장하는 값은 구간이 포함하는 원소의 ..
io 성능 향상 [0. C] printf 와 scanf 는 매우 빠르니 그냥 사용 하면 된다. [1. C++] std::cout 과 std::cin 은 printf 와 scanf 에 비해 매우 느리다. 멀티 스레딩 환경이 아니라면 아래 방법을 통해 io 성능 향상을 노릴 수 있다. std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); 기타 자세한 설명? [2. go] bufio 를 활용하도록 한다.
이진 트리 - 예제 1 [1. 문제 설명] https://algospot.com/judge/problem/read/NERD2 [2. 풀이 접근] [3. 코드]
트리 - 예제 2 [1. 문제 설명] [2. 풀이 접근] [3. 코드]

티스토리툴바