Jonyo Programming

[BOJ 13537(P4)리뷰] 유명한 수열과 쿼리 1번문제다. 세그먼트 트리 + 이분탐색을 이용하여 문제를 해결할 수 있다. 세그먼트 트리를 구성할때 각 부모노드들은 자식의 값들을 정렬된 상태로 갖는 형태여서 머지소트 트리 라고도 불리는 것 같다. 이렇게 트리를 구성함으로 우리는 각 구간별 정렬된 값들을 가질 수 있다. 쿼리가 들어오면 구간을 확인한 후에 K보다 큰 값들의 개수를 출력하면 된다. 정렬된 상태이기 때문에 upper_bound를 통해 쉽게 구할 수 있다. 1. 구간에 맞지 않는 경우 2. 구간에 걸친 경우 3. 구간에 완전히 속하는 경우 위 세가지의 경우로 처리하여 반환되는 값들의 합을 출력하면 정답처리를 받을 수 있다. /* 21.01.25 BOJ : 13537 수열과 쿼리 1 (http..

[BOJ 11505(G1)리뷰] N개의 값이 1번 index부터 차례대로 주어진다. 그 후에 명령을 입력받는데 "1 a b"의 형태라면 a를 b라는 수로 바꿔야하고, "2 a b"의 형태라면 a번 index부터 b번 index까지의 곱을 출력해야 한다. 값을 update하는 작업이 있으므로 단순히 구간의 곱을 저장하는 것으로는 시간내에 해결 할 수 없다. 따라서 값을 update하고 구하는 과정을 O(logN)에 수행할 수 있는 세그먼트 트리 자료구조를 이용했다. 일반적으론 구간의 합을 세그먼트 트리 구조로 저장하지만, 이번 문제는 구간의 곱을 저장해주면 된다. 따라서 값에 영향을 주지 않도록 비어있는 노드는 1로 초기화 해주어야하며, 값을 update할때는 botoom-up방식으로 구현 하는 것이 깔끔..

[BOJ 5670(P3)리뷰] 저장된 단어를 기준으로 자판 자동완성(?) 기능을 만들어야 한다. 예를들어, hello라는 단어가 저장되어 있다면 he만 입력해도 hello라는 단어가 완성되어야 한다. 하지만 h로 시작하는 단어가 2개 이상이라면 자동완성이 되어서는 안되고 사용자로부터 입력을 받아야 한다. 즉, 단어 사전에 hello 와 heaven만 저장되어 있다면 h를 누르는 순간 'e'가 자동으로 입력되어야 하고 (h로 시작하는 단어는 모두 뒤에 e가 붙으므로) 그 후에는 사용자로부터 입력을 받아야 한다. 그리고 만약 he가 입력된 상태에서 'l'을 입력하게 되면 그 후에는 존재하는 단어가 1개이므로 'hello'까지 자동완성 되어야 한다. 입력으로 휴대폰에 저장된 단어의 목록이 주어졌을 때, 각각의..

[BOJ 9202(P5)리뷰] 간단해 보이지만 간단하지 않은 문제다. 사용자로 부터 미리 N개의 단어를 입력받는다. 그리고 4X4크기의 보드를 입력받는다. 이 보드에서 가로,세로,대각선으로 이동하며 만들 수 있는 단어의 개수, 단어의 총 점수(단어의 길이마다 점수가 있다.), 가장 긴 단어를 출력해야 한다. 보드에서 단어를 찾는것 + 미리 입력받은 N개(최대 30만개) 의 단어목록에 있는지 확인하는 작업을 완전탐색으로 하려면 내가 늙어 죽을때 까지 돌려도 찾기가 힘들것이다. 따라서 이 문제를 해결하기 위해서는 "트라이"라는 자료구조에 대해 알아야 한다. 트라이는 위 그림과 같은 구조를 갖고있다. 각각의 노드는 객체로 이루어져있으며 객체는 a~z 또는 A~Z의 26개의 동일한 객체를 갖는 구조로 되어있다...

[BOJ 2243(P5)리뷰] 세그먼트 트리를 응용하는 문제다. 사탕상자에서 사탕을 넣거나 뺄 수 있고, 동생에게 N번째로 맛있는 사탕을 줘야할 때도 있다. 사탕의 맛은 1부터 100만이다. 이걸 배열로 기록하여 값을 업데이트 한다면 시간복잡도O(N^2)으로 시간초가가 나게 된다. 따라서 업데이트를 O(logN)에 가능하게 하여 최종적으로 O(NlogN)으로 풀어야 정답처리를 받을 수 있다. 일반적으로 세그먼트 트리에는 구간의 합을 저장한다. 가장 리프노트에는 본래의 값이 들어있고, 리프노드에서 부모노드로 올라갈 수록 자식노드의 합들을 저장하며 루트노드까지 올라간다. 최종적으로 루트노드에는 전체범위의 합이 저장되어 있다. 이 문제는 이러한 구조를 갖는 세그먼트 트리를 응용하여 풀어야 하는 문제다. 사탕의..