앞서 Segment Tree를 알아 보았다. 2021.05.02 - [Problem Solving] - Segment Tree 그런데 생각보다 개발량도 많고 필요할때 바로 만들어서 쓴다는게 쉽지 않다. 그래서 Binary Indexed Tree를 알아보고자 한다. Binary Indexed Tree는 크게 2개의 Array가 필요하다. N+1 Size의 오리지널 Array N+1 Size의 Fenwick Tree Array 오리지널 Array는 입력하고자 하는 Array 그 자체라고 생각하면된다. [1,3,5,7,9,11,13,15] 라는 배열이 있다면 이것을 Original Array = [NA,1,3,5,7,9,11,13,15] 로 유지 하는 것이다. NA가 들어가는 이유는 첫번째 Value를 1이라..
어떤 Integer가 주어졌을 경우 해당 Integer의 가장 우측에 존재하는 1의 위치를 찾고자 한다면 다음과 같이 하면 된다. N & -N 6을 예로 들어보겠다. 6의 2진수는 0000 0110 이 된다. 해당 값을 음수로 변환하면 (보수 처리 하고 마지막 1을 더하면 음수이다.) 1111 1010 이 된다. And 처리를 하면 0000 0010 이 되고 가장 우측 위치 값은 2가 된다.
Segment Tree 특정 범위의 Array 의 Sum을 빠르게 하기 위해 만들어진 기법이다. 만약 [3,5,8,1,3,9] 라고 하는 Array가 주어 졌다고 생각해 보자. 이를 Tree로 만들면 다음과 같다. 이 Tree에서 주의해서 봐야할 점은 우측에 '0' 이다. 반듯이 Tree의 Balance를 맞춰줘야 한다. 이렇게 Tree가 만들어지면 다음과 같이 Query가 가능하다. [3,5,8,1,3,9] 에서 0 ~ 5까지의 Sum은? 상기와 같이 Index 0과 5 즉 Left Index < Right Index인 관계에서 Left Index가 짝수이면 상위 노드로 올라간다. Right Index 가 홀수이면 상위 노드로 올라간다 라는 개념을 만들 수 있다. 그런데 상위 노드의 Index는 몇인가..
Create Sorted Array through Instructions 문제 내용 빈 Array nums[]가 있고 이곳에 입력할 값 Array 인 instructions가 있다고 할때 instructions Array의 왼쪽에서 오른쪽으로 nums[] Array에 값을 추가해 나간다. 단, nums[]의 Array는 정렬이 되어야 한다. 정렬을 위한 cost는 다음과 같이 정의한다. Min( 현재 있는 nums 중 insturction[i] 보다 작은 숫자의 갯수, 현재 있는 nums 중 instruction[i]보다 큰 숫자의 갯수 ) 예를 들자면 [1,2,3,4,5]의 nums가 주어졌을 때 3을 넣기 위한 최소의 cost 값은 1,2 => 2개, 4,5 => 2개 min(2,2) 임으로 cost..
Employee Free Time 문제 내용 종업원들의 스케쥴이 주어진다 모든 스케쥴을 확인한 후 모든 종업원들이 쉬는 시간을 구하라 접근 방법 모든 종업원들이 쉬는 시간, 즉 업무를 진행 하지 않는 시간을 찾으면 된다. 예를 들자면 [[[1,2],[5,6]],[[1,3]],[[4,10]]] 이라는 스케쥴이 주어졌다고 생각하자 상기의 그림처럼 `3~4`를 찾는게 문제이다. 이 그림을 보면 예상이 되겠지만, 어떤 사람별 스케쥴은 의미가 없다. 즉 모든 스케쥴을 한사람의 스케쥴이라고 생각하고 쉬는 시간을 찾으면 된다. 보이는 것처럼 단 2개의 스케쥴만 확인하고 해당 스케쥴 사이의 거리를 찾으면 되는 것이다. 그럼 어떻게 스케쥴이 겹치지 않는지 확신 할 수 있는가? 이것을 이벤트로 보면 다음과 같이 정리 할 ..
First Missing Positive 문제 내용 주어진 Integer Array에 1부터 N까지의 수가 있다. 이중에 1이상의 수중에 첫번째로 없는 수를 찾아라 O(N)을 목표로 한다. 접근 방법 O(N)이라는 부분이 이 문제의 핵심이다. 만약에 쉽게 정리 한다면 Sorting O(NlogN)으로 문제를 해결할 수 있다. 그러나 O(N)의 속도는 Sorting으로 해결되지 않는다. 이런경우 자료 구조를 통한 접근을 우선적으로 생각할 수 있다. 나는 Priority Queue를 통한 접근을 생각했다. 값을 Push할 경우 O(LogN) Delete할 경우 O(1)과 자리를 찾는데 걸리는 시간 최대 (N)이 걸릴 수 있다. 그래서 최대 O(N)으로 Priority Queue를 생각했다. public in..
Merge k Sorted Lists 문제 주어진 N개의 Linked List가 주어지고, 이 N개의 Linked List를 Merge후 오름차순 정렬한 하나의 Linked List를 반환하라 접근방법 가장 쉬운 방법은 N개의 Node중 첫번째 노드의 Value를 상호 비교 하면서 List를 하나씩 Pop 하는 방법이다. 이방법을 사용하면 List의 갯수 만큼 Compare가 필요하다. 상기 그림을 보면 1,3,7 => 3번을 Compare하고 2,3,7 => 3번을 Compare하고 .... 7 => 1번을 Compare하게 되는데 만약에 3개의 Linked List가 동일한 Node의 갯수를 갖게 된다면 최악의 경우 O(numberOfList * Node) 만큼의 시간 복잡도를 갖게 된다. 그래서 다..
Consecutive Numbers Sum 문제 내용 주어진 숫자(N)보다 같거나 낮은 수의 연속적인 배열의 Sum이 주어진 숫자와 같은 경우의 수는 몇개인가? 접근 방법 수학적인 접근을 통해서 문제를 해결해야 한다. 만약에 15라는 N이 주어졌다고 생각해 보겠다. 15(N) = 4 + 5 + 6 으로 이루어 질 수 있다. 또는 15(N) = 8 + 7 로도 이루어 질 수 있다. 이것을 일반항화 시키면 다음과 같다. N = (x + 1) + (x + 2) + (x+ 3) + ... + (x + k) 여기서 k는 연속된 갯수이다. 8 + 7은 두개의 연속된 갯수 임으로 k는 2이다. 이를 x로 묶어 보겠다. N = x*k + (0 + 1) + (0 + 2) + (0+ 3) + ... + (0 + k) 여기..
Basic Calculator 문제 내용 숫자, 더하기, 빼기, 중괄호 '(' ')' 그리고 ' ' 스페이스로만 구성된 계산식을 계산 하시오 풀이 방법 기본적으로 후위연산을 통해서 해당 문제를 푸는게 학교에서 배우는 방법이다. 자세한 내용은 www.programmersought.com/article/93565454512/ 여기를 참고 하면 되는데 간단하게 순서를 설명하자면 아래와 같다. 1. Stack을 2개로 유지한다 2. 1번 Stack은 숫자와 Operand(연산자) 로 이루어진 Stack이다. 3. 2번 Stack은 Operand(연산자)와 '(' 왼쪽 대괄호로 이루어진 Stack이다. 4. 2번 Stack에서 ')' 좌측 대괄호를 만나면 2번 Stack에 있던 Operand를 1번 Stack으로..