본문 바로가기

전체 글

 (84)
모노톤 스택 / 큐 / 덱 monotone 이라고 한다면 증가하고 있거나 감소하는 등의 (mono- ) 일정한 경향을 보임을 뜻한다. 그러한 형태를 띠는 스택, 큐, 덱인 것이다. 모노톤이라고 해서 한 방향을 띠긴 하지만, 모든 데이터를 담는 것은 아니다. 필요가 없어진 데이터는 버릴 수 있어야 하고, 필요가 없는 데이터는 기록조차 하지 않는다. 하지만 보통 이 방법을 통해 시간 복잡도를 O(N)으로 줄일 수 있어서 매우 강력하다고 생각한다. 다양한 활용처가 있겠지만, 이 포스트에서는 특정 범위내의 최대 / 최소를 구하는 방법에 대해 알아보고자 한다. 보통 최소값, 최대값 등을 구하기 위해 정렬을 한다. 정렬에도 다양한 방법이 있다. 하지만 정렬은 모든 데이터가 주어졌을 때 사용 가능하다. 더 이상 생성, 수정, 삭제 등의 연산이..
백준 11003 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 이 문제는 우선순위 큐로 해결할 수도 있지만, 모노톤 덱을 이용하면 더 빠르다. 우선순위 큐를 활용하려 할 경우, 데이터가 들어왔을 때 우선순위 큐에 담고, 최솟값 찾을 때 이미 범위를 벗어났는지 여부만 확인해주면 된다. 모노톤 덱을 사용한다면, 크기가 증가하는 수열 형태로 덱을 만들어주면 된다. 차근 차근 오른쪽으로 넣어준다. 범위가 벗어났다면 왼쪽에서 버려주고,..
백준 1185 유럽여행 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 위 문제는 다양한 경우의 수가 있을 것 같지만, 문제에 걸린 제한을 통해 '자동'으로 코너 케이스가 다 사라졌다고 생각한다. 증명할 수만 있으면 자신 있게 코드를 제출할 수 있다. 가장 중요한 조건은 N-1개의 길만 남겨야한다는 것이다. 이를 통해 모든 정점들이 빠짐없이 연결되는 트리구조를 갖게 된다는 것을 알 수 있다. 사이클이 없다는 것이다. 여기서 최소 ..
백준 3015 오아시스 재결합 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 결론부터 먼저 말하면 이 문제는 스택 활용이 필요하다. 어차피 검색을 했다면, 풀이가 필요했을 테니 스포일러가 아니리라 생각한다. 스택 활용 문제는 항상 쉽지 않다. 하지만 시간 복잡도를 O(N)으로 낮춰주는 대단히 강력한 방법이다. O(N^2)이 보통 최악이라면, 그것을 O(NlogN)으로만 낮추어도 효율이 좋은 건데 O(N)은 사실상 최선의 방법이다. 적어도 모든 데이터..
자바스크립트의 비동기 처리 (배열에서의 비동기 처리) - 2 앞선 포스팅에서 비동기 처리의 기본적인 부분을 살펴보았다. 이번에는 그것보다는 까다로운 케이스, 배열에서의 비동기처리를 알아보겠다. 쿼리의 결과로 리스트를 받으면 그것에 대한 추가 가공을 해야 하는 경우가 생기는데 그때 다시 필연적으로 배열에서의 비동기 처리가 필요하다. 이번에도 예제를 통해 작동 방식을 알아보자 b = [1, 3, 4] const f = async arr => { return arr.map(e => e + 3) } console.log(f(b)) 일단 위와 같이, 간단하게 1차원 배열 b부터 시작하자. f라는 함수에 배열을 넣으면 각 원소에 3을 더해서 리턴해준다. 근데 콘솔에 찍히는 건 프로미스가 붙어있다. 이제 이건 예상할 수 있어야 한다. async함수이기에 리턴에는 프로미스가 붙..

티스토리툴바