프로그래머스 : 혼자 놀기의 달인 (Kotlin) 문제 문제 확인하기 풀이 cards의 길이는 총 상자의 개수이며, cards의 값에는 1부터 cards의 길이까지의 숫자 카드가 존재한다. 그리고 문제를 다시 확인해보자. 그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다. 이 부분은 DFS 알고리즘을 통해 구현할 수 있다. 상자의 번호를 cards 배열의 인덱스로, 상자안의 값을 cards 배열의 값으로, 상자가 열렸는지 여부는 방문 여부를 체크하는 새로운 배..

프로그래머스 : 마법의 엘리베이터 (Kotlin) 문제 문제 확인하기 풀이 storey 층에서 0층으로 내려가야 한다. 내려가는 방법은 -10^c or +10^c (c >= 0) 중에서 선택해야 한다. 우선 storey로 한 자리 숫자가 주어졌을 때를 생각해보자. 3이 주어졌다고 할 때 단순히 -1 버튼을 3번 눌러서 0층으로 가는 것이 가장 빠르다. 7이 주어졌다고 해보자. 이 때는 -1을 7번 누르는 것 보다 +1을 3번 눌러서 10층으로 이동하고 -10 버튼을 눌러 0층으로 가는 것이 가장 빠르다. 5가 주어지면 어떨까? 5가 +1을 5번 누르고 -10을 한 번 누르는 것 보다는 단순히 -1을 5번 누르는 것이 더 빠르게 이동할 수 있다. 이번에는 storey가 두 자리 숫자가 주어졌을 때를 생각해..

프로그래머스 : 멀쩡한 사각형 (Kotlin) 문제 문제 확인하기 풀이 가로 3, 세로 4 크기의 직사각형이 주어졌다고 하자. 이 직사각형을 대각선 양 끝 꼭짓점을 기준으로 자르는 것을 좌표상에 표시하면 아래와 같이 표현할 수 있다. 양 끝 꼭짓점([0, 0]과 [3, 4])을 서로 이었을 때 나오는 대각선은 y = (4/3) * x 방정식으로 표현할 수 있다. 우리는 이 대각선을 기준으로 우측에 있는 삼각형에 몇 개의 1 * 1 크기의 정사각형이 존재하는지 세고, 이 값의 2배를 정답으로 반환하면 된다. 여기서 1 * 1 크기의 정사각형이 몇 개가 존재하는지 어떻게 셀 수 있을까? 먼저 x 좌표의 범위가 0 ~ 1인 부분을 보자. 여기는 정사각형이 존재하지 않는다. 다음 x 좌표의 범위가 1 ~ 2인 ..

프로그래머스 : 게임 맵 최단거리 (Java) 문제 문제 확인하기 풀이 (1, 1) 위치에서 출발해서 우측 하단 좌표인 (n, m) 위치까지 몇번의 이동이 걸리는지 구하는 문제이다. BFS를 통해 문제를 해결할 수 있다. BFS에 대한 설명은 아래 링크에서 확인할 수 있다. BFS 확인하기 아래는 자바로 작성한 코드이다. class Solution { // 맵 세로 크기 private static int rowSize; // 맵 가로 크기 private static int colSize; // {x, y} 형식으로 큐에 삽입 private static Queue queue = new LinkedList(); public int solution(int[][] maps) { int answer = 0; ro..

프로그래머스 : 택배상자 (Java) 문제 문제 확인하기 풀이 문제의 핵심만 간단하게 요약해보겠다. 컨테이너 벨트를 통해 1번부터 n번까지 상자가 오름차순으로 전달되며 컨테이너 벨트의 맨 앞에 있는 상자만 내릴 수 있다. 주어진 순서 배열 order에 맞게 k번 상자를 트럭에 실어야 한다. order 배열의 인덱스가 순서이고 값은 상자의 번호이다. 현재 컨테이너 벨트의 맨 앞에있는 상자가 트럭에 실을 순서가 아니면 보조 벨트를 이용한다. 보조 벨트는 입구와 출구가 동일한 Stack 형태이다. 보조 벨트에 적재하거나, 보조 벨트에서 상자를 꺼내 트럭에 싣는다. 보조 벨트를 이용해도 order 순서대로 상자를 싣지 못하면 종료한다. 컨테이너 벨트를 통해 상자가 도착했을 때, 상자가 트럭에 실을 순서와 일치하..

프로그래머스 : 테이블 해시 함수 (Java) 문제 문제 확인하기 풀이 문제의 요구사항에 따라 알고리즘의 흐름을 작성해보자. 테이블(배열)을 정렬한다. col번째 컬럼을 기준으로 오름차순 정렬한다. 같은 값은 첫번째 컬럼인 기본키를 기준으로 내림차순 정렬한다. 각 튜플에 대해 아래 내용을 반복한다. 각 컬럼을 현재 튜플의 순서(i)로 나눈 나머지를 구한다. 나머지들의 합을 S_i로 구한다. 각 튜플의 순서를 i라고 할 때, row_begin

프로그래머스 : 전력망을 둘로 나누기 (Java) 문제 문제 확인하기 풀이 송전탑의 개수 n이 주어지고 송전탑끼리 이어진 전선들의 정보 wires가 주어진다. wires를 통해 이어진 전선들은 하나의 트리 형태를 이룬다고 한다. 따라서 전선들 중 하나를 끊으면 하나로 묶인 트리가 두 묶음으로 나누어진다. 문제에서 요구하는 것은 전선들 중 하나를 끊어 송전탑 묶음을 두 개로 나누었을 때, 양 묶음의 송전탑의 개수 차이가 최소가 되도록 하는 것이다. 먼저, 전선을 끊는다는 것은 전선들의 정보 wires 중 하나를 무시하는 것으로 볼 수 있다. wires를 이용해서 각 송전탑과 연결된 테이블을 만들 때, wires 중 하나를 건너뛰고 만들면 된다. 전선의 개수는 n-1개라고 했다. 여기서 n은 2 이상, 10..

프로그래머스 : 피로도 (Java) 문제 문제 확인하기 풀이 던전의 최대 개수는 8개이다. 던전의 개수가 최대, 즉, 8개일 때, 모든 던전을 탐험하는 경우의 수는 8!으로 40320개이다. 따라서 완전 탐색으로 정답을 찾을 수 있다. 완전 탐색을 위해 DFS를 이용하였다. 모든 경로를 탐색해보기 위해 DFS 메서드 내에서 반복문을 이용했다. 남은 피로도로 현재 던전을 탐험할 수 있다면 해당 던전을 탐험처리하고 다음 던전을 선택하도록 한다. 반복을 통해 가능한 모든 경로를 탐험한다. 문제에서 요구하는 것은 유저가 탐험할 수 있는 최대 던전의 수이다. DFS 메서드는 탐험 가능한 최대 던전의 수를 반환해야 한다. DFS 메서드가 현재 탐험 가능한 던전의 수를 반환하도록 하면, 가장 깊은 곳의 DFS 메서드..

프로그래머스 : 양궁대회 (Java) 문제 문제 확인하기 풀이 과녁은 0 ~ 10점까지 총 11가지의 점수가 있다. 이 11가지의 점수 중 획득할 수 있는 점수들의 조합은 2^11(2048)이므로, 우리는 완전 탐색을 통해 문제를 해결할 수 있다. 여기서 점수를 획득할지 안할지 기록하기 위해 비트마스킹 기법을 활용하였다. 획득 가능한 점수들의 조합을 반복문으로 돌면서 해당 점수를 얻을 때 사용한 화살 개수가 문제에서 주어진 화살 개수 n보다 작거나 같을 때에만 라이언이 획득한 점수와 어피치가 획득한 점수를 계산하도록 하였다. 현재 확인하고있는 점수들의 조합을 얻기 위해 n발의 화살보다 크다면 불가능한 경우의 수이기 때문이다. 현재 확인하고 있는 점수들의 조합이 라이언이 쏠 수 있는 경우의 수라면, 어피치..

백준 문제 풀이 : 부분수열의 합(1182번)(Java) 문제 문제 확인하기 풀이 n개의 정수들을 원소로 갖는 수열 arr이 있을 때, arr의 부분 집합의 총 원소의 합이 s인 경우가 몇개인지 구하는 문제이다. n의 최대값, 그러니까 수열 arr의 최대 길이는 20이므로, 완전 탐색을 이용하여 문제를 해결할 수 있다. 단순히 모든 경우를 고려하면 된다. n이 4인 수열 {1, 2, 3, 4}가 주어졌다고 가정하자. 이 수열의 부분 집합은 {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 2, 3, 4}가 존재한다. 이 부분 집합들을 하나씩 찾으면서 해당 부분 집합의 ..