코딩 테스트 정복기/기타

문제3열 N행의 가중치가 있는 배열 arr이 주어집니다.이 배열에 다음 규칙을 준수하면서 조약돌을 놓을 때 최대 가중치의 합을 반환하는 Solution() 함수를 구현하세요. 제약조건• 각 열에 조약돌은 적어도 하나는 놓아야 합니다.• 각 조약돌에 바로 인접한 위치에 조약돌을 놓을 수 없습니다.- 인접 기준은 상하좌우입니다. 입출력의 예arrreturn[ [ 1, 3, 3, 2 ], [ 2, 1, 4, 1 ], [ 1, 5, 2, 3 ] ]19[ [ 2, 7, 13, 2, 6 ], [ 2, -4, 2, 5, 4 ], [ 5, 3, 5, -3, 1 ] ]32   풀이 및 코드3열 N행에서 각 열에 조약돌을 놓는 방법은 다음과 같다.예) 1행에서1. 1열에 두는 방법이전 행에서 2열이나 3열을 선택했을 때 ..

문제정수배열 nums에서 LIS의 길이를 찾는 함수를 작성하세요.제약조건• nums는 최대길이 1,000의 정수 배열입니다.• nums의 각 요소는 -1,000 이상 1,000 이하의 정수입니다. 입출력 예numsreturn[1, 4, 2, 3, 1, 5, 7, 3]5[3, 2, 1]1   풀이 및 코드LIS(Longest Increasing Subsequence)란?"최장 증가 부분 수열"이라고도 하며, 주어진 수열에서 엄격히 증가하는 가장 긴 부분 수열을 찾는 문제이다.부분 수열은 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들만 선택한 수열을 의미한다. 예를 들어, `[1, 4, 2, 3, 1, 5, 7, 3]` 에서 LIS는 `[1, 2, 3, 5, 7]`이다. 동적 계획법 (Dynamic..

문제이미 정렬이 완료되어 있는 두배열 arr1, arr2을 받아 병합정렬하는 Solution()함수를 구현하세요. 제약조건 arr1과 arr2는 각각 길이가 1 이상 100, 000 이하 입니다.• arr1과ar r2는 각각오름차순으로 정렬되어있습니다.  입출력 예arr1arr2result[1,2,3][4,5,6][1,2,3,4,5,6][1,3,5][2,4,6][1,2,3,4,5,6]풀이 및 코드병합정렬이므로, 이미 정렬 된 arr1과 arr2를 index0부터 값을 비교하여 채워넣으면 된다. import java.io.*;import java.util.*;public class Main { private static long bfs(int n, int target){ if(n == t..

문제인자로 받은 문자열s를 계수정렬로 정렬하여 반환하는 solution() 함수를 구현하세요. 제약조건• string `s`의 길이는 1 이상 10,000 이하입니다. • `s`는 알파벳 소문자로 이루어져 있습니다.  입출력 예sreturnhelloehlloalgorithmaghilmort  풀이 & 코드계수 정렬 또는 카운팅 소트(counting sort):컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것.쉽게 말하자면, 정렬된 어떠한 키에따라 빈도를 저장하는 정렬 알고리즘이다. 시간복잡도는 `O(n)`때문에 키가되는 숫자를 알고있어야 하고, 키의 범위가 너무 크지 않아야한다. 위 문제에서는 a~z를 키로하고, String s에 나오는 문자의 빈도를 계산하면 ..

문제9 x9 스도쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 solution()함수를 작성하세요.해는 유일하지 않을 수 있습니다. 스도쿠의 조건에 맞다면 맞는 해라고 생각하시면 됩니다.스도쿠의 규칙은 아래와 같습니다.가로줄, 세로줄에는 1부터 9까지의 숫자가 한번씩 나타나야 합니다.9x9 보드를 채울 9개의 작은 박스(3 x3크기)에도 1부터 9까지의 숫자가 한번씩 나타나야합니다.  제약조건문제에 주어지는 board 중 스도쿠를 완성하지 못하는 board는 없다고 가정합니다.예를들어, 특정행이나 열에 같은 숫자가 있는 경우는 없습니다.   입출력 예시boardresult [[5, 3, 0, 0, 7, 0, 0, 0, 0],[6, 0, 0, 1, 9, 5, 0, 0, 0],[0, 9, 8, 0, 0,..

문제정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 solution() 함수를 작성하세요  제약조건• 백트래킹을 활용해야 합니다.• 숫자조합은 오름차순으로 정렬되어야 합니다.• 같은 숫자는 한번만 선택할 수 있습니다.• N은 1이상 10이하인 정수입니다.  입출력 예Nresult5[[1,2,3,4],[1,4,5],[2,3,5]]2[]7[[1,2,3,4],[1,2,7],[1,3,6],[1,4,5],[2,3,5],[3,7],[4,6]]문제 풀이1. 오름차순으로 정렬되어 있어야 하므로 1부터 순차적으로 탐색한다.2. 백트래킹을 활용해야 하므로 백트래킹 조건을 설정한다.      ㄴ 숫자 조합 합이 10 이상인 경우 백트래킹한다.3. 만약 숫자 조합 합이 10이 되면 ..