개발로그

코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 주어진 정수형 배열을 더하거나 빼면서 index가 numbers의 길이에 도달했을 때, 연산 결과와 타겟을 비교한다. DFS로 풀었다. class Solution { public int cnt = 0; public void dfs(int[] numbers, int index, int now, int target) { if (index == numbers.length) { if (now == target)..

문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치하고자 한다. 또한 배치 과정에서 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 한다. 병사에 대한 정보가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하시오. 풀이 문제에서는 전투력이 강한 순서대로 세웠지만 이를 반대로 약한 순서대로 세워도 문제 없다. 약한 순서대로 오름차순으로 봤을 때, 해당 문제는 최장 증가 부분 수열 문제로 볼 수 있다. [Algorithm] 최장 증가 부분 수열 (LIS) 최장 증가 부분..

문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일 째 되는 날 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡아달라고 부탁했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡았다. 각각의 상담은 완료하는데 거리는 시간 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다. 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 구하시오. 풀이 1. 시간은 흐르기 때문에 앞에서부터 계산하기보다, 마지막 날부터 최고의 금액을 계산하면서 1일차로 오는 것이 좋다고 생각했다. 2. 1일부터 N일까지의 업무 중 X일 차에 수행할 업무가 걸리는 시간 Tx가 있을 때, X + Tx가 N일을 넘기..

문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택해 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중 하나만 선택할 수 있다. 풀이 금광 문제와 마찬가지로 최대를 저장하는 2차원배열은 선언한다. 금광은 모든 2차원 배열을 탐색하면서 지나갔지만, 위 문제는 범위에 대한 조절만 잘 하면 된다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ..

문제 n x m 크기의 금광이 있다. 금광은 1x1 크기의 칸으로 나누어져있고, 각 칸은 특정한 크기의 금이 들어있다. 채굴자는 첫번째 열부터 금을 캐기 시작한다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있다. 이후 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하시오. 풀이 n x m 크기의 배열을 새로 생성한다. 해당 배열 (i, j)에서는 현재까지 가져갈 수 있는 최대의 금을 저장하도록 한다. 먼저, 0열의 값들을 초기화 한다. (각 자리의 값이 최대이기 때문) 그리고 1열부터는 직전 열의 왼쪽, 왼쪽 위, 왼쪽 아래의 값과 해당 칸의 합이 가장 큰 값을 저장하도록 한다. 마지막 m-1열에 저..

문제 도현이의 집 N개가 수직선 위에 있다. 각 집의 좌표는 같은 좌표를 가지지 않는다. 언제 어디서나 와이파이를 즐기기 위해 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 설치하려고 한다. 공유기 C개를 N개의 집에 적당히 설치해서 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램 작성하시오. 풀이 해당 문제는 공유기가 설치되는 거리를 찾아야 한다. 1. 공유기 설치되는 집을 조합으로 뽑아 각각의 거리를 확인한다? 2. 공유기 설치되는 거리를 줄여나가면서 몇개가 설치되는지 확인한다? 1번보다는 2번을 알고리즘으로 푸는데 효율적으로 보인다. (조합하고, 연산..

문제 고정점이란 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 원소가 오름차순으로 정렬되어 있다. 이 수열에서 고정점이 1개 존재할 때, 고정점을 출력하시오. 없다면 -1을 출력하시오. 풀이 완전 탐색으로 풀 수 있지만, 정렬되어있는 수열에서는 이진검색트리를 사용하는 것이 효율적이다. 해당 문제는 중간값과 중간 인덱스를 비교해 같은 값이라면 고정점으로 출력한다. 만약 아니라면 중간값 > 중간인덱스 일 때, 중간보다 뒷 부분 (start = mid + 1)을 탐색하고, 반대의 경우 앞 부분 (end = mid)을 탐색하도록 한다. 중간 값이 1이고, 중간 인덱스가 2인 경우 1보다 앞 선 값들은 1보다 작은 값인데, 인덱스는 0과 1..

문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이 때, 이 수열에서 x가 등장하는 횟수를 계산하시오. 풀이 입력되는 수열이 오름차순이고, 완전 탐색으로 몇개인지 셀 수 있지만, 시간복잡도에서 O(N)의 시간 복잡도를 가지게 된다. 이보다 이진검색트리를 사용하면 O(logN)의 시간 복잡도로 해결할 수 있다. 먼저, x보다 큰 수의 인덱스를 찾는다. 그리고 x보다 크거나 같은 수의 인덱스를 찾아 빼면 갯수를 확인할 수 있다. 왼쪽 인덱스는 타겟과 크거나 같은 수의 인덱스를 찾는다. public static int leftIndex (int start, int end) { while (start < end) { int mid = (start + end) / 2; if (arr[mid]..

문제 정렬된 두 묶음의 숫자 카드가 있을 때, 각 묶음의 카드의 수를 A, B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B번 비교를 해야 한다. 매우 많은 숫자 카드 묶음이 책상 위에 있다. 이들을 두 묶음씩 골라 서로 합쳐나가면 고르는 순서에 따라서 비교 회수가 달라진다. N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지 구하는 프로그램을 작성하시오. 풀이 먼저 각 묶음마다 몇개 인지 적힌 배열을 정렬했다. 그리고 앞에서부터 합하면서 계산했다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ..

문제 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이 중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총합이 최소가 되도록 설치하려고 한다. 집들의 위치 값이 주어질 때 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오. 풀이 주어지는 집들의 위치를 정렬시키고, 집 들 중 가운데 위치한 집에 설치하는 것이 가장 효율적이다. 정렬된 리스트에서 (길이 - 1) / 2 인덱스를 가진 값을 출력한다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.next..