기록공간

문제 N개의 정수를 담는 배열 A가 주어진다. 0

문제 N개의 숫자를 원소로 가지고 배열 A가 주어진다. 여기서 (X, Y, Z) 인덱스 위치가 주어진다. (0 1일 경우 max(0, M[1 - 1]) + max(0, N[1 + 1]) Y -> 2일 경우 max(0, M[2 - 1]) + max(0, N[2 + 1]) ... Y -> 6일 경우 max(0, M[6 - 1]) + max(0, N[6 + 1]) 이 값들중 가장 큰 값이 정답이 된다. 코드는 다음과 같다. for문을 중첩하여 사용하지 않았기 때문에 시간 복잡도는 O(N)이 된다. class Info{ int sum_from_front = 0; int sum_from_back = 0; } class MaxDoubleSliceSum { public int solution(int[] A) { if..

문제 N개의 숫자가 들어있는 배열 A가 주어진다. 우선 여기서 Leader 숫자를 먼저 찾는다. Leader 숫자가 되기 위해서는 두 가지 조건 중 하나가 필요하다. 배열에서 가장 많이 중복되는 값 배열 길이의 절반 값보다 더 많이 나오는 값 이제 A를 둘로 쪼갠다. (0 = limitEquiLeft) && (RightCount >= limitEquiRight)) { ++result; } } return result; } }

문제 정수값을 담는 N개의 배열 A가 주어진다. A에 존재하는 정수값이 중복으로 배열 사이즈의 절반 이상 존재하는 경우 그 정수값은 Dominator가 된다. 이 Dominator를 찾고, 이 Dominator 값인 인덱스 위치 중 하나를 출력하는 문제이다. 해결 방법 중복되는 값으로 몇 개가 존재하는지 효과적으로 알 수 있도록 해시 테이블을 사용한다. 해시의 Key값에는 인덱스에 존재하는 값이 들어가고, Value값은 그 값이 존재하는 인덱스들을 담는 Vector 컨테이너가 들어간다. 배열 A를 순회돌며 해시 테이블에 Key값과 Value값을 넣어준다. 그 작업이 끝나면 해시 테이블에 들어간 값(Iterator)를 순회돌며 배열 A 사이즈의 절반이 넘어가는 Dominator가 존재하는지 찾는다. 만약 ..

문제 N개의 원소가 담긴 배열 H가 주어진다. H[0] ~ H[N-1] 까지의 원소에는 벽의 높이 값이 들어간다. 이때 H 높이들을 만족하는 벽을 쌓기 위해서 최소 몇 개의 블럭이 필요한지를 구하는 문제이다. 해결 방법 스택을 활용하여 풀 수 있는 문제였다. 스택을 사용하는 이유는 서로 같은 높이에 있는 있거나 가장 낮은 높이의 값들은 블럭을 하나로만 써야 최소한의 블럭을 만들 수 있기 때문이다. 이러한 값들을 스택에 기록해 블럭을 어떻게 만들지 결정한다. 다음과 같은 규칙으로 높이 값을 순회돌며 스택을 사용한다. (i번째 높이 값을 h라고 했을때) 1. 스택이 비어있다 => h를 push한다. 2. 스택 top의 값이 h보다 큰 경우 => pop 하고 배치 블럭 수를 1 증가시킨다. 3. 스택 top의..

문제 N개의 배열 A에서 0 A[R], A[Q] + A[R] > A[P], A[R] + A[P] > A[Q]. 1을 출력하고 모든 경우에서 위 조건을 만족하지 않는다면 0을 출력하면 되는 문제이다. 해결 방법 우선 위와 같은 방법을 직접 적용하여, 모든 인덱스 경우에서 조건을 만족할때까지 찾는 방법이 있다. 예를 들면 (0, 1, 2), (1, 2, 3), ..., (0, 2, 3), ..., (N - 3, N - 2, N - 1) 모든 경우의 인덱스를 검사하며 위 조건을 만족하는 것을 찾으면 바로 1을 리턴하는 것이다. 하지만 이 방법은 삼중 반복문을 사용하므로 시간복잡도가 O(N^3)이다. 즉 최대 10만개의 배열 크기를 처리하기에는 매우 비효율적인 알고리즘이다. 우선 이것을 해결하기 위해서는 정수를..

문제 N개의 배열에 각 디스크의 반지름 크기 값이 들어 간다. 그리고 0 ~ N-1 까지의 인덱스 범위가 디스크의 위치가 된다. 디스크끼리 서로 교차하는 경우 그것을 한 쌍으로 본다. 이러한 쌍이 몇개 있는지 구하는 문제이다. 해결 방법 우선 처음으로 시도했던 방법은 각 디스크 별로 순회하며 다른 디스크끼리 서로 교차하는지 검사한 후, Heap에 집어넣어 중복값을 배제하고 Heap 크기만큼 출력하는 방법이다. 하지만 디스크를 검사할때마다 그 디스크를 제외한 모든 디스크를 검사하기 때문에(이중 반복문) O(N^2)의 시간 복잡도가 나왔다. 이 방법은 역시 효율성이 안좋기 때문에 통과할 수 없었다. 최소 O(NlogN)이하는 되어야 통과가 가능하다. 위 예제에 있는 디스크들의 모양을 다음과 같이 표식화 시켜..

구간 합(Prefix Sum)이란? 만약 N개의 정수형 배열이 있다고 가정했을 때, 부분 합은 0 ~ (N - 1)까지의 합을 의미하는 것이고, 구간 합은 a ~ b (0