문제 풀이 과정N개의 추가 주어질 때 측정할 수 없는 최소 무게를 구하는 문제이다. 주어진 무게들을 오름차순으로 정렬한 다음 누적합을 구해 다음 추의 무게가 누적합 + 1보다 크면 누적합 + 1이 만들지 못하는 최소 무게가 된다. 왜 이 풀이가 정답을 보장하는 것일까? 예를 들어보자.정렬된 추의 무게가 다음과 같다고 가정하자.[1, 1, 2, 5, 11] 1단계 추 무게: 1조건 확인: 0(sum) + 1 >= 1(현재 추 무게)sum: 0 -> 1만들 수 있는 무게 범위: 1설명: 무게가 1인 추 1개로 1을 측정가능 2단계추 무게: 1조건 확인: 1(sum) + 1 >= 1(현재 추 무게)sum: 1 -> 2만들 수 있는 무게 범위: 1 ~ 2설명: 무게가 1인 추 2개로 1~2까지 측정 가능..
Algorithm
문제 풀이 과정N x N 크기의 2차원 배열이 주어진다. 물에 잠기지 않는 안전영역의 최대개수를 구하는 문제이다. 문제 해결 아이디이 문제는 DFS 탐색을 통해 효과적으로 해결할 수 있다.DFS는 현재 노드에서 갈 수 있는 경로를 따라 계속 깊이 들어가 탐색한 뒤, 더 이상 갈 수 없으면 되돌아와 다른 경로를 탐색하는 방식이다. 문제 접근1. 높이 0부터 최대 높이까지 전체탐색을 시작한다.2. 현재 높이 h에서 물에 잠기지 않는 영역만을 대상으로 DFS 탐색 수행한다.3. DFS 탐색이 끝날 때마다 안전영역의 개수를 +1 카운트 한다.4. 모든 높이에 대해 반복한 뒤 최대 영역의 개수를 구한다. 1. 입력 받으면서 최대 높이 구하기입력을 받으며 최대 높이를 구한다.for (int i = 0; i ..
문제 풀이 과정문제 이해이 문제는 주어진 서로 다른 알파벳 C개가 있을 때 L자리의 암호를 만드는 문제이다.암호를 만들 때 규칙이 존재한다.암호는 최소 1개의 모음이 포함암호는 최소 2개의 자음이 포함암호는 정렬된 형태를 가진다.abc => 가능bca => 불가능3번째 규칙을 고려했을 때 알파벳의 모든 조합을 구하는 문제이다.사전순으로 출력하기 위해 주어진 알파벳들을 정렬하여 조합을 구한다.조합을 구하고 1, 2 규칙을 어기는 수열은 출력에 제외하도록 문제를 풀어나가면 해결할 수 있다. 종료 조건depth는 현재 암호의 개수이다.vCount는 모음의 개수, cCount는 자음의 개수이다.현재 모음의 개수가 L개가 되면 암호 출력을 준비한다.1번 2번 규칙에 위배되는 암호는 출력에서 제외한다. if (de..
문제 풀이 과정백트래킹을 이용해서 이 문제를 해결할 수 있다. 종료조건day는 현재날짜를 저장하는 변수이다.sum은 지금까지의 수익이다.day가 N(남은 퇴사일) 이상이면 sum을 활용하여 최대값을 갱신하고 리턴if (day >= N) { MAX = Math.max(MAX, sum); return;} 상담할 경우상담이 가능하다면 즉, day + T[day]가 N이하라면, day에서 현재 T[day]를 더해서 다음 상담 날을 구하고, 현재 수익에 추가된 수익을 더해 재귀호출한다. if (day + arr[day][0] 상담하지 않을 경우해당 날에 상담을 하지 않을 경우 현재 날에 +1을 해주고, 현재 수익을 그대로 넘겨 재귀호출한다. dfs(day + 1, sum); 코드public class..
문제 풀이 과정문제 이해길이가 N인 수열과 각 숫자들과 연산자를 이용해 모든 가능한 식의 결과를 계산그 중 최대값, 최솟값을 구하는 문제숫자의 순서는 고정, 연산자는 순서가 바뀔 수 있다. 모든 연산 순열을 탐색하는 문제이므로 백트래킹을 이용해 해결할 수 있는 문제이다. 문제 풀이종료조건depth는 현재까지 몇개의 숫자를 사용했는 지이다.num은 현재까지 계산된 결과이다. 모든 숫자를 사용했으면 계산 결과를 가지고 max와 min을 갱신한다.if (depth == N) { MAX = Math.max(MAX, num); MIN = Math.min(MIN, num); return;} 연산과 반복operator 배열은 연산자 개수를 저장한 배열이다.연산자는 총 4가지 종류이므로 operator..
문제풀이 과정이전에 풀었던 N과 M (1) 문제와 유사한 문제이다.https://soonmin.tistory.com/145 이번 문제는 (1)과 달리 수열을 구성할 때 같은 숫자를 선택해도 된다.하지만 "각 수열은 비내림차순이어야 한다" 라는 조건을 충족해야 한다.비내림차순은 "오름차순 OR 같다" 를 의미한다.[1, 1] => 가능[1, 4] => 가능[5, 4] => 불가능(1) 풀이와 다르게 반복문의 시작 지점을 위한 start 변수가 필요하다. 중복을 허용하므로 다음 인덱스의 위치를 현재 인덱스 위치로 지정하여 재귀호출 한다. 코드public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(Sy..
문제 풀이 과정이전에 풀었던 N과 M (1)과 유사한 문제이다.https://soonmin.tistory.com/145 이번 문제는 (1)과 달리 같은 숫자를 여러번 선택해도 되는 문제이다.(1, 1) => 가능 (1)에서는 중복 숫자를 제거하기 위해 visited 배열을 사용하였고 방문 여부에 따라 수열에 숫자를 대입했었다.이번 문제는 중복을 허용하므로 방문여부와 상관없이 수열에 숫자를 대입해주면 해결할 수 있는 문제이다. 코드public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(..
문제 풀이 과정이전에 풀었던 N과 M (1) 문제와 매우 유사한 문제이다.https://soonmin.tistory.com/145 (1)과 달리 이번 문제는 각 수열이 오름차순이어야 한다.(1, 4) => 가능(4, 1) => 불가능즉, 이 문제는 모든 조합을 구하는 문제이다.1 ~ N까지 자연 수 중 모든 조합을 구하여 출력하는 문제이다. 조합 예시[1, 2, 3, 4] 수열에서 2개를 뽑는 조합은?[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4] 문제 풀이N과 M (1) 문제와 유사한 문제로 모두 백트래킹으로 알고리즘으로 해결하는 문제이다.(2)는 (1)과 달리 다음 반복문에서 시작할 인덱스 번호를 지정하기 위한 변수 start가 필요하다.다음 반복문에서 start..
문제 풀이 과정이 문제는 1 ~ N 자연수 중에서 중복없이 M개를 고른 모든 수열을 사전 순으로 출력하는 문제이다. 백트래킹 알고리즘으로 해결할 수 있는 문제이다. 백준 단계별로 알고리즘을 풀고있다면 이전에는 브루트포스 알고리즘을 다루어 보았을 것이다. 백트래킹과 브루트포스 알고리즘의 차이는 브루트포스는 모든 경우의 수에 모두 탐색하는 알고리즘이다.그와 달리 백트래킹 알고리즘은 탐색 과정에서 조건을 통해 유망성을 판단하여 탐색 범위를 줄여나가는 알고리즘이다. 문제 풀이현재 선택한 숫자의 개수(depth)가 M에 도달하면 출력그렇지 않으면,visited 배열을 통해 유망한 노드인지 검사한다. 자식 노드의 방문상태를 변경다음 자식 노드 방문을 위해 재귀호출자식 노드의 방문이 끝나면 방문 상태를 원래 상태로 ..
문제풀이 과정이 문제는 서로 다른 9개의 숫자 중에 7개의 숫자를 선택해 합이 100이 되는 숫자를 오름차순 정렬하여 출력하는 문제이다.9개의 숫자 중 7개를 선택하는 모든 경우의 수를 고려하는 문제이므로 브루트포스로 해결 할 수 있다. 처음에는 7개의 숫자를 선택하는 모든 경우의 수를 구하여 100이 되면 문제면 정렬하여 출력하는 방식으로 문제를 접근했었다.하지만 이 방식은 중첩 반복문이 7개가 필요하다는 것에 말이 안된다고 생각했다. 위 방식을 반대로 생각하면, 9개의 숫자 중 2개만 선택하는 접근 방식이 옳다고 생각했다.(반복문 7개 => 반복문 2개)먼저 9개의 숫자 합을 구한 뒤 2개의 숫자를 선택하여 빼준 결과가 100이 된다면 조건에 부합한다.(예시) 140(합) - 15 - 25 = 10..
