만들어가는 세상

문제를 풀어보진 않았습니다. 개념 이해 및 공유 차 내용 포스팅 합니다. 문제 정수 배열이 주어졌을 때, 배열 안에서 곱이 최대가 되는 두 정수를 찾으시오. 매일프로그래밍 문제 기준 Input: [-10, -3, 5, 6, -2] Output: [-10, -3] 또는 [5, 6]풀이1 단순한 방법은 모든 쌍에 대해 곱을 계산하는 것입니다. 계산한 쌍의 곱이 이전보다 크면 새로운 쌍의 곱과 두 수를 저장하면서 가장 큰 곱을 찾아갑니다. class FindMaximumProduct { public static void findMaximumProduct(int[] A) { int max_product = Integer.MIN_VALUE; int max_i = -1, max_j = -1; // 모든 원소들의 쌍..

병합 정렬 개념 병합 정렬은 여러 개의 정렬된 자료의 집합을 결합해 하나의 집합으로 만드는 정렬 방법이다. 이 정렬은 전체를 상대로 수행하지 않고 분할(Divide)한 뒤 각 부분집합들에 대해 정렬한 후 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다. 분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트 나 합병정렬이 있다. 매일프로그래밍 문제 기준 문제 사이즈가 m인 배열 X와 사이즈가 n인 배열 Y가 주어집니다. 두 배열은 모두 정렬된..

계수 정렬 개념 계수 정렬(Counting Sort)이란? 데이터 값을 직접 비교하지 않고, 단순하게 개수를 세어 기록하고 정렬하는 방식이다. 값 비교가 일어나지 않기 때문에 속도가 매우 빠르다. 하지만 개수를 저장하는 배열, 정렬할 배열을 위한 추가 공간이 필요하다. 또한 숫자가 매우 큰 경우에는 속도가 현저히 느려질 수 있다. 매일프로그래밍 문제 기준 문제 원소가 0, 1, 2로 구성된 배열이 주어졌을 때, 상수 공간을 이용해 선형 시간에 배열을 정렬하시오. 문제의 핵심은 주어진 배열만을 이용하는것 입니다. 주어진 배열로 Output을 처리하려면 병합정렬을 사용하면 됩니다. Input: [0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0] Output: [0, 0, 0, 0, 0, 1, ..

병합 정렬 개념 병합 정렬은 여러 개의 정렬된 자료의 집합을 결합해 하나의 집합으로 만드는 정렬 방법이다. 이 정렬은 전체를 상대로 수행하지 않고 분할(Divide)한 뒤 각 부분집합들에 대해 정렬한 후 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다. 매일프로그래밍 문제 기준 문제 두 개의 정렬된 배열 X, Y가 주어졌을 때, 두 배열의 크기를 유지하면서 두 배열의 전체를 정렬하시오. 즉, 배열 X에는 작은 수들로 배열 Y에는 큰 수들로 구성되고 원소들은 정렬되어 있어야 합니다. 단, 정렬 시 다른 자료 구조를 사용하지 않고 주어진 배열만을 이용해야 합니다. 문제의 핵심은 주어진 배열만을 이용하는것 입니다. 주어진 배열로 Output을 처리하려면 병합정렬을 ..