코드저장소

이번 문제는 최대 힙을 이용하여 배열에서 가장 높은 값을 출력하고 제거하는 프로그램을 만드는 것이다. 문제를 풀기위해서는 먼저 최대 힙에 대해서 알고 있어야 하는데, 자바에서는 우선순위 큐라는 것을 이용하여 비슷한 형태를 만들 수 있다. 최대 힙에 대해서 궁금하다면 잘 정리된 글이 있으니 참고하기 바란다. https://innovation123.tistory.com/111 [JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap) 힙(Heap) 힙은 완전 이진트리 형태로 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조이다. 힙은 중복값을 허용한다. 부모-자식 간 (레벨 별) 정렬은 보장하고, 형제간의 정렬은 보장하지 않아 innovation123.tistory.com ..

이번 문제는 A,B,C 세가지 수가 주어지면 A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제이다. 입력의 최대값은 2,147,483,647로 큰 값을 Long의 범위 안에서 어떻게 처리 할지가 핵심이었다. 그럼 어떻게 풀지 살펴보자. 수학적 지식이 필요하다 이번 문제를 풀기 위해선 수학적 지식이 조금 필요한데, 첫째는 지수 법칙이고 두번째는 모듈러 성질이다. 1. 지수 법칙 2. 모듈러 성질 이 2가지를 이용하여서 문제를 해결한다. 그럼 위의 공식과 분할 정복이 문제와 무슨 연관이 있느냐? 위 문제를 그냥 A*B %C로 푸는 경우 입력값이 최대인 2,147,483,647인 경우 Long의 범위를 넘어가게 된다. 따라서 지수를 보다 작은 값으로 나눠 줄 필요가 있는데, 이를 위하여 분할 정복과 지수..

이번 문제는 2차원 행렬에 담긴 데이터를 판단하여 0,1,-1로 분류하여 같지 않으면 9등분 하고 맞으면 갯수를 구하는 문제이다. 문제 자체가 크게 어렵지 않아 금방 풀어낼 수 있었다. 그럼 어떻게 풀었는지 살펴보자. 분할 정복이란? 분할 정복이란 큰 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체의 답을 계산하는 알고리즘이다. 언뜻 봐서는 재귀호출과 비슷해 보이지만, 일반 재귀 호출과 분할 정복의 가장 큰 차이는 일반 재귀 호출은 문제를 한 조각과 나머지 전체로 나눈다면 분할 정복은 문제를 거의 같은 크기의 부분 문제로 나눈다는 점이다. 분할 정복은 3가지 과정으로 이루어 지는데 1. 문제를 더 작은 문제로 분할하는 과정 2. 각 문제에 대한 답을..

이번 문제는 이분 탐색 기법을 활용하여 랜선의 갯수와 길이가 주어질 떄, 만들어야 할 랜선의 갯수를 충족하는 최대 길이 값을 구하는 문제이다. 처음 문제를 보았을 때는 어떻게 풀어야 할지 잘 생각이 나지 않았는데 문제 설명을 보면 파라메트릭 서치(Parametric Search)라는 말이 나와 검색을 해보고 풀 수 있었다. 그럼 파라메트릭 서치가 어떤 것이고 어떻게 문제를 풀었는지 다시 한번 복기해본다. 파라메트릭 서치(Parameteric Search)란? 파라메트릭 서치는 주어진 문제가 최적화 문제(최대, 최소값을 구하는 문제) 일 때 주로 사용한다. 이진 탐색과의 비슷하지만 차이가 있다면 이진 탐색이 결정 문제(특정 값이 존재하는지 여부)를 해결하는데 사용된다면 파라메트릭 서치는 최적화 문제의 답을..

이번 문제는 이분 탐색을 이용하여 주어진 수가 특정 배열에 존재하는지 판단하는 프로그램을 작성하는 문제이다. 이분 탐색의 첫 문제인 만큼 이분 탐색이 무엇이고 어떻게 만들어야 하는지 정리해본다. 이분 탐색이란? 어렸을 때 한번쯤 Up&Down 게임을 해본적이 있을 것이다. 상대방이 숫자를 생각해 내면 내가 숫자를 추측해서 말하고 상대방이 그 수가 정답보다 큰지 작은지 말해주는 게임이다. 이분 탐색 알고리즘은 위의 게임과 거의 유사하다. 특정 값을 찾을 때, 중간 값을 기준으로 값을 비교하고 적으면 처음 부터 중간까지, 크다면 중간부터 끝까지 탐색하는 것이다. 다만, 이렇게 하기 위해서 기준 배열이 정렬이 되어있어야 한다는 것이 주의점이다. 예를 들어서, 1,5,3,2,4라는 값이 있고 2라는 값을 찾는다..

최근 동적계획법 문제가 약한것 같아 다시 해당 단계를 풀어보는 중이다. 이번 문제는 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제이다. 점화식을 만드는데 꽤 애를 먹었는데 어떻게 풀었는지 정리해보고자 한다. 점화식이 가장 중요하다. 이번 문제에서의 핵심은 점화식을 어떻게 만드느냐였다. 처음에 점화식을 어떻게 만들지를 생각하지 못해서 꽤 애를 먹었는데 결국 핵심은 어떤 정수를 1,2,3의 합으로 나타내는 방법이므로 만드는 숫자는 3개로 한정된 것이 핵심이였다. 우선, 초기값으로 1,2,3에 해당하는 값인 1,2,4를 dp배열에 넣어두었다. 그 후, 4 이상의 값은 n-3,n-2,n-1을 모두 더한값과 같게된다. 무슨 말인지 잘 이해가 안되니 4와 5..

이제 동적 계획법도 얼마 남지 않았다. 이번 문제는 양 쪽의 전봇대에 전깃줄이 교차하지 않도록 없애야 하는 전깃줄의 최소 갯수를 출력하는 문제이다. 점화식을 어떻게 만들지가 좀 어려운 문제였는데 어떤 식으로 풀었는지 살펴보자. 어떻게 구해야 할까? 이번 문제의 핵심은 점화식을 어떻게 만들것인가가 핵심이었다. 처음 생각했을때는 1차원 배열 2개를 만들어 각각의 전봇대의 숫자를 넣은 후, A 전봇대를 기준으로 하여 반복문을 돌린 후 B 전봇대의 값이 이전 인덱스의 최대 값 보다 높으면 카운트를 추가하는 형식으로 구현하려고 하였다. 예를 들어서 예제를 기준으로 보자. 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 8 2 9 1 4 6 7 10 A 전봇대를 기준으로 하면 다음과 같이 ..

이번 문제는 n개 만큼의 포도주가 있을때, 연속으로 3잔을 마실 수 없는 경우 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하는 문제이다. 저번에 풀었던 계단 문제와 크게 다르지 않으므로 간단하게 풀어 낼 수 있었다. 그럼 어떻게 풀었는지 살펴보자. 규칙은 간단하다! 규칙은 이전 계단 문제와 비슷하다. 3잔을 연달아 마실수 없으므로 결국 비교해야하는 것은 -3 인덱스에 -1 인덱스에 해당하는 값을 더한 값과 -2된 값중 큰것을 자기 인덱스의 값과 더하면 된다. 테이블로 살펴보자. 0 1 2 3 4 5 6 0 6 10 13 9 8 1 0 6 16 초기값을 셋팅해주면 (0번째 인덱스는 무조건 0이라고 가정한다.) 2번째 인덱스의 값은 무조건 1번 인덱스의 값에 자기 값을 더한 값이 된다. 그..

주어진 수를 규칙에 따라 1로 만들 때 가장 최소 연산하는 횟수를 구하는 간단한 문제이다. 정말 간단한 문제였는데 생각을 잘못해서 한참을 헤멘 문제이기도 했다. 그럼 문제를 한번 살펴보자. 정말 간단한 문제! 문제는 정말 간단하다. 우선 규칙은 3으로 떨어지면 3으로 나누거나 2로 떨어지면 2로 나누거나 1을 뺀다. 이다. 즉, 주어진 수 크기의 배열을 만들고, 최소값만 가져오면 마지막 주어진 수 n 에는 최소 횟수가 기록되게 된다. 다만, 주의 할점이 있는데 예를 들어 10의 경우 2로 나눌수 있기 때문에 바로 2로 나누는 경우 10 > 5 > 4 > 2 > 1의 4번이 되지만 -1을 하면 10 > 9 > 3 > 1 이되므로 3번만에 나눌수 있다. 그렇다면 우리가 비교할 것은 지금 수에 -1 한 값과 ..

이번 문제는 각각의 집을 RGB중 하나로 칠한다고 할때, 규칙을 만족하면서 비용의 최솟값을 구하는 문제이다. 핵심은i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다라는 조건을 어떻게 구현할 것인지 였는데 어느정도 동적계획법에 익숙해져서 인지 아니면 문제가 쉬웠던 건지 조금 생각해본 후에 간단하게 풀어 낼 수 있었다. 그럼 어떻게 풀었는지 되짚어 보자. 규칙은 무엇인가? 우선 입력값을 보면 딱 봐도 2차원 배열 형태로 저장해야 할 것 같은 느낌이 든다. 예제 입력 1을 기준으로 살펴보자. 나는 이번 동적계획법을 2차원 배열을 사용하여 구현했다. 우선 각각의 값을 기록하기 전 초기 상태는 다음과 같을 것이다. 0 1 2 26 40 83 당연히 0번 index에는 첫행이 ..