기록공간

문제 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)이하는 되어야 통과가 가능하다. 위 예제에 있는 디스크들의 모양을 다음과 같이 표식화 시켜..

문제 N개의 정수를 담은 컨테이너가 주어진다. 그리고 0 (2 + 2) / 2 => 2 일때 가장 작은 평균값이 나오기 때문에 답은 P = 1 이다. 해결 방법 단순하게 위의 방법을 코드로 구현하여 접근한다면, 효율성이 떨어지게 된다. 이때 시간 복잡도는 O(N^2)이 나온다. O(N)이 나와야 효율성에서 통과가 되기 때문에, 다른 방법을 생각해야 한다. 평균값의 원리를 잘 알고 있다면, 다른 방법을 사용해 볼 수 있다. 평균값은 항상 평균값을 계산할 숫자중에 가장 작은 값보다 크거나 같다. 예를들어 (1, 2, 3)이 있다면 (1 + 2 + 3) / 3 = 2로 가장 작은 값인 1보다 크다. 이 뜻은 최소 범위에서의 평균값을 알고 있다면, 그 이후 범위의 평균값은 구할 필요가 없다는 것이다. 예를들어 ..

문제 A, C, G, T는 순서대로 1, 2, 3, 4 값이다. 즉 A < C < G < T이다. A, C, G, T를 입력한 문자열 S와 탐색할 범위 P[i] ~ Q[i] 가 주어진다. 탐색 범위에 들어있는 알파뱃 중 가장 값이 작은 것을 컨테이너에 담아 출력하면 되는 문제이다. 예를 들어 CAGCCTA를 S로 입력받았고, P와 Q는 다음과 같이 입력되었다고 가정하자. P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6 i가 0일때 범위는 2 ~ 4번째 까지이다. 2번째 인덱스 G부터 4번째 인덱스 C까지 범위에서 가장 작은 알파뱃은 C이므로 정답은 2이다. i가 1일때 범위는 5번째이므로, 5번째 알파뱃 T가 가장 작으므로 정답은 4이다. i가 2일때 범위..

문제 A와 B 사이에 있는 수들 중 K와 나눠지는 개수를 출력하는 문제이다. 해결 방법 갯수만 출력하면 되기 때문에 A부터 B까지 반복하며 K와 나눠지는지 검사할 필요가 없다. A가 0일 경우 B까지의 K로 나눠지는 숫자의 개수는 (B / K) + 1이다. 1이 더해지는 이유는 0일 때에도 K와 나눠지기 때문이다. A가 0이 아닐 경우에는 0부터 B까지의 개수인 (B / K) + 1에서 A까지 K와 나눠지는 개수를 빼주면 된다. 만약 A가 K와 정확히 나눠진다면 (B / K) + 1 - (A / K) 를 해주면 된다. 만약 그렇지 않은 경우 (B / K) + 1 - ((A / K) + 1)을 해주면 된다. 둘의 차이는 A를 K로 나눠지는 것을 포함하느냐 안 하느냐의 차이이다. 코드는 다음과 같다. int..

문제 주어진 N개의 원소들을 담은 컨테이너에 1 ~ N까지 모두 존재하는지 확인하면 되는 간단한 문제였다. 해결 방법 주어진 컨테이너 원소들을 오름차순 정렬 한 후 차례대로 탐색하며 1부터 N까지 있는지 검사하면 된다. 만약 없는 경우 바로 0을 리턴한다. 반복문을 정상적으로 마친 경우 1을 리턴한다. 코드는 다음과 같다. #include #include using namespace std; int solution(vector& A) { int check = 1; sort(A.begin(), A.end()); for (const auto iter : A) { if (iter != check++) return 0; } return 1; }

문제 주어진 숫자들 중 연속되지 않고 중간에 비어 있는 숫자가 있는 경우 가장 작은 정수를 출력하는 문제이다. (이 정수는 0보다 크다) 만약 연속으로 끝까지 이어진 경우에는 그 이후의 숫자를 출력하면 된다. 그리고 음수만 존재하는 경우에는 조건을 만족하는 가장 작은 정수인 1을 출력하면 된다. 해결 방법 우선 주어진 숫자가 순서가 맞아야 쉽게 정답을 찾을 수 있으므로 오름차순 정렬한다. 음수만 있는 경우를 알 수 있도록 가장 끝 값이 음수인지 검사한다. 만약 음수라면 1을 출력한다. 이제 처음부터 끝까지 반복하며, 중간에 숫자가 비었는지 검사한다. 음수는 정답에 포함되어 있지 않으므로 생략하고 진행한다. 만약 이전 값과 현재 값의 차가 2이상이라면 중간에 숫자가 한가지 이상 비어있다는 것으로 현재 값의..