풀이 세그먼트트리를 응요한 자료구조인 머지 소트 트리(Merge Sort Tree)를 이용하면 O((logn)^2)시간 안에 해결할 수 있는 문제입니다. 머지 소트트리는 간단하게 말해서 트리의 각 노드에 자식들의 최솟값이나 최댓값을 저장하는 것이 아니라, 머지소트(Merge Sort)시에 일어나는 각 배열들의 중간 상태를 저장하는 자료 구조입니다. [5, 2, 4, 6, 1, 3, 2, 6]의 배열을 머지소트를 이용해서 정렬할 경우, 위의 그림과 같은 과정을 거치게 됩니다. 이 때, 각 노드의 상위 노드에는 두 배열을 머지하여 생긴 새로운 배열을 저장합니다. 즉 배열(혹은 리스트)의 배열 구조를 띄게 되는 것입니다. 이렇게 머지소트트리를 생성하고 난 후에는 쿼리를 날려서, 각 구간안에 포함되는 배열들 중..

Overview 트리 자료구조는 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행할 수 있도록 도와줍니다. 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다. 구간 트리는 특히 일차원 배열의 특정 구간에 대한 질문들(최대, 최소값 등)을 빠르게 대답하는 데에 주로 사용합니다. 예를 들어, 일차원 배열의 특정 구간에서 최대인 값을 찾기 위해서는 특정 구간을 일일이 순회하면서 최소값을 찾아야 했습니다. 하지만, 구간 트리를 이용하면 특정 구간의 최대값을 미리 전처리해서 부모 노드에 저장하는 방식을 취하기 때문에 (일종의 다이나믹 프로그래밍 방법이라고도 할 수 있습니다.) 훨씬 더 빠른 시간에 ..

풀이 트리의 중위 순회(InOrder), 후위 순회(postOrder)의 성질을 이용하여 전위 순회(preOrder)의 결과를 출력하라는 문제입니다. 중위 순회와 후위 순회를 이용해서 직접 트리를 생성한 후에 그냥 전위 순회를 재귀적으로 호출하는 방법도 있겠지만, 이 방법은 트리를 생성해야 하기 때문에 귀찮고 비효율적인 작업이 될 가능성이 보여서 다른 방법으로 문제를 해결하였습니다. 트리의 중위 순회는 트리의 모든 데이터를 일차원 직선에 사영했을 때, 그 결과를 순차적으로 보여준다는 특징이 있습니다. 정렬된 이진 탐색 트리의 경우 트리의 중위 순회 결과는 숫자 배열을 정렬된 순서대로 출력합니다. 트리의 후위 순회는 재귀적인 방식으로 Left child -> rightChild -> Parent Node의..

풀이 이분 탐색을 통해 문제를 해결하면 주어진 시간 안에 문제를 해결하는 알고리즘을 구현할 수 있다.먼저 주어진 나무들의 길이를 배열에 저장하고 Arrays.sort를 통해 빠르게 길이순으로 정렬한다.이분탐색의 탐색범위는 0부터 길이가 가장 긴 나무의 길이까지이며(left = 0, right = arr[arr.length-])mid 는 0부터 시작해 반복문의 매번 마지막에는 (left+right)/2 로 재설정해준다.각각의 반복문이 돌아갈 때마다또 다른 반복문을 통해 mid의 길이에 따른 잘린 나무들의 길이의 합을 구해준다.이 길이가 m과 같으면 mid의 값을 출력하고, 아닌 경우 각각 mid의 값을 갱신하여 반복문을 돌게 한다. 하지만 한 가지 주의해야 할 점이 있는데문제의 조건을 잘 살펴보면, 높이가..

풀이 BFS를 이용하여 풀어야 하는 문제였다. 먼저 창고에 있는 토마토들을 쭉 스캔해서 큐에 넣는다.큐는 FIFO(First - In - First - Out)의 성질을 가지는 자료구조이기 때문에큐에 먼저 넣은 토마토들의 상하좌우의 좌표를 먼저 탐색할 수 있다. 창고에 있는 토마토들을 쭉 스캔해서 넣은 다음에는 !q.isEmpty()를 조건으로 while문을 이용한다.큐에서 빼낸 좌표의 상하좌우의 좌표가 유효한지를 먼저 확인하고, (isValid) 그 좌표에 익지않은 토마토가 있다면 토마토를 익게 만들고,원래의 토마토의 날짜에 1을 더해 익은 토마토의 좌표와 함께 큐에 다시 넣어주고 BFS를 반복한다. 즉, 큐에 들어가는 객체는 창고의 x좌표, y좌표, 그리고 경과일수가 들어가며, 맨 처음 스캔할때의 경..

풀이 문제 자체는 크게 어려운 문제는 아니었던것 같다.하지만, 풀이 과정에 따라서 시간 복잡도가 천차만별이 될 수 있다는 것을3번의 실패끝에 경험했다. 몇 자리수인지를 물어보는 것이 아니라 뒷자리에 0이 몇개가 있는지를 계산하는 문제였기 때문에비교적 간단하게 2 와 5의 개수만으로 답을 구할 수 있다. 단 이때 참고해도 될 만한 부분은 1. 2의 개수는 무조건 5의 개수보다 많으므로 굳이 2의 개수를 세느라 시간을 낭비할 필요가 없다 2. 1~N 사이의 2나 5의 배수를 탐색하는 과정에서 모든 숫자를 탐색할 필요가 없다 이 2가지 정도로 정리할 수 있겠다. 2번을 몰랐던 상황에서 1024!의 값을 구하기 위해1~1024 까지의 모든 자연수의 2, 5의 배수개수를 세고 있었고결과적으로 시간 복잡도가 증가하..