코드저장소

이번 문제는 최대 힙을 이용하여 배열에서 가장 높은 값을 출력하고 제거하는 프로그램을 만드는 것이다. 문제를 풀기위해서는 먼저 최대 힙에 대해서 알고 있어야 하는데, 자바에서는 우선순위 큐라는 것을 이용하여 비슷한 형태를 만들 수 있다. 최대 힙에 대해서 궁금하다면 잘 정리된 글이 있으니 참고하기 바란다. 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..

드디어 누적합 단계로 들어왔다. 이번 문제는 누적 합을 이용하여 연속된 날짜간의 온도의 최대값을 구하는 문제이다. 각 날짜에 대한 온도와 구해야 하는 날짜를 받아서 계산을 해야하는데 누적합을 이용하여 계산 시간을 줄이는 것이 핵심인 문제였다. 그럼 어떻게 문제를 풀었는지 살펴보자. 반복의 반복... 이번 문제를 누적합을 쓰지 않고 계산한다고 생각해보자. 총 10일이 주어지고 구해야하는 날짜가 5일인 경우를 생각해보자. 계산은 위의 그림과 같이 이루어져야 한다. 중요한것은 위의 그림을 어떻게 구현할 것인가 인데, 단순히 반복문을 이용하여서 로직을 만든다고 생각해보자. 나와야하는 값은 총 6개이므로 반복도 6번이 될것이다. 그렇다면 전체 갯수 n개가 주어지므로 반복을 최소화 하기 위해 메서드를 통하여 만든다..

이제 동적 계획법도 얼마 남지 않았다. 이번 문제는 양 쪽의 전봇대에 전깃줄이 교차하지 않도록 없애야 하는 전깃줄의 최소 갯수를 출력하는 문제이다. 점화식을 어떻게 만들지가 좀 어려운 문제였는데 어떤 식으로 풀었는지 살펴보자. 어떻게 구해야 할까? 이번 문제의 핵심은 점화식을 어떻게 만들것인가가 핵심이었다. 처음 생각했을때는 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 전봇대를 기준으로 하면 다음과 같이 ..

이번 문제는 동적 프로그래밍을 이용하여 배낭에 넣을 수 있는 최대 가치 값을 찾아내는 문제이다. 골드 난이도 답게 난도가 좀 있었는데 혼자서 이리저리 짜보다가 생각처럼 잘 되지 않아 ChatGpt의 도움을 약간 받아 해결하였다. 그러면 어떻게 문제를 풀었고 어디가 문제였는지 살펴보자. 무엇이 반복되는가? 이전 글에서도 서술 했지만 동적 계획법의 핵심은 반복되는 요소를 기록하여 시간을 단축시키는 것이다. 그러면 무엇이 반복되는 것이고 그것을 어떤 방법으로 기록할 것인지가 핵심이 되겠다. 문제는 배낭의 넣을 수 있는 물건들의 최대 가치값만을 요구하고 있기 때문에 안에 몇개가 들어가는지, 몇종류가 들어가는지는 중요하지 않다. 즉, 배낭에 무게별로 들어가는 가치합이 반복되는 요소가 될 것이다. 그럼 남은 문제는..

이번 문제는 동적 프로그래밍을 이용하여 피보나치 수열을 풀어보는 문제이다. 기존에 재귀를 이용하여 피보나치 수열을 계산하는 것을 해보았지만, 이번에는 동적 프로그래밍을 이용하여 더 빠르고 효율적인 프로그래밍을 하는것이 목적이다. 그럼 우선 동적 계획법에 대해서 자세하게 살펴보자. 동적 계획법(Dynamic Programming) 이란... 동적 계획법(줄여서 DP라고 부르기도 한다.) 을 간단하게 설명하면 답을 재활용하는 것이다. 좀 더 본질적인 의미를 살리자면 기억하며 풀기라고 생각해도 되겠다. 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거의 구한 해를 활용하는 것이 동적 계획법의 핵심이다. 문제를 작은 문제로 쪼개어 생각한다는 점에서 분할 정복 알고리즘과 비슷하게 보이기..