기록공간

문제 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의..

그리디 알고리즘을 사용하는 문제였다. 우선 나이트의 모든 이동방법이 위, 아래 오른쪽으로 무조건 1칸 이상 움직이므로, 세로 길이가 1인 체스판의 경우에 나이트는 한번도 이동 할 수 없다. 즉 세로가 1일때는 방문한 최대 칸 수는 1칸이다. 이제 이동 횟수가 4번 미만일 경우를 먼저 생각해보자. 이동 횟수가 4번 미만일 경우에는 이동방법에 제한이 없다는 것을 생각하고 다음을 살펴보자. 우선 세로 길이가 2인 체스판의 경우이다. (2 X 5) 최대로 방문할 수 있는 방법은 위 그림처럼 이동방법 2, 3번을 이용하여 가로 홀수 칸을 방문하는 방법이다. 이 방법을 사용하면 체스판의 가로 길이가 M이라고 했을때 나이트는 최대 (M + 1) / 2 칸을 방문할 수 있다. 하지만 위 규칙에 따라 이동횟수는 4번 미..

그리디 알고리즘을 사용하는 문제였다. 입력에서 키 정보와 자신보다 키가 큰 사람이 왼쪽에 몇 명이 있는지에 대한 정보가 주어진다. 그렇게 때문에 줄을 어떻게 서야 하는지에 대한 정보를 저장할 배열 result를 만들어 놓고 가장 작은 키의 사람부터 정보에 맞게 result에 키를 나열해주면 된다. 사람의 수는 10을 넘기지 않으므로 키의 범위는 1~10이 될것이다. 이 범위를 넘어가는 11을 빈자리로 선언하고 result를 빈자리로 채워넣는다. 위의 예제를 예로들어 설명하겠다. 사람 4명이 있으므로 result 배열의 크기는 4일 것이다. 둘째 줄 입력에 정보를 바탕으로 result에 줄의 순서를 배치해보자. 우선 키 1인 사람은 자기보다 키큰 사람이 왼쪽에 2명이 있다. 그러므로 자신의 키보다 큰 EM..

동적계획법을 사용하는 문제였다. 우선 점화식을 찾기 위해 규칙이 어떠한지 부터 살펴보자. P(1)~P(3)일때는 1로 모두 동일하다. 그리고 P(4)~P(5)일때 2이다. P(4)의 값은 P(1)과 P(2)를 더하여 2가 나오며, P(5)의 값은 P(2)와 P(3)을 더하여 2가 나온다. P(6)의 값은 P(3)과 P(4)를 더하여 3이 나온다. 이러한 규칙을 봤을때 점화식은 다음과 같을 것이다. P[N] = P[N - 3] + P[N - 2] 결과값이 int의 범위를 넘어가기 때문에 P(N)의 값을 저장할 dp 테이블 배열을 long long 형식으로 선언해주어야 한다. 코드는 다음과 같다. #include using namespace std; int main() { long long dp[100 + ..