문제문제 바로가기풀이Back Tracking을 이용하여 해결Stack을 사용하여 구현현재 위치에서 이동 가능한 위치가 있으면 Stack에 추가만약 이전에 방문한 적이 있는 위치이면 추가 XSet을 사용하여 이전에 방문한 위치 기록Stack에서 Pop한 위치를 탐색만약에 pop하여 얻은 위치에서 이동 가능한 경로가 없으면 다시 pop위 과정을 Stack이 비어있거나, 목적지에 도착할 때 까지 반복코드import java.util.*;import java.io.FileInputStream;class Solution{ public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in);..
문제문제 바로 가기문제 풀이문제 조건중 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다. 라는 조건 덕에, 복잡한 케이스 고려X사다리 맨 마지막의 도착지로부터 역으로 추적현재 이동 방향을 표시하는 direction변수를 사용하여 유동적으로 방향 전환현재 방향이 위로 향하는 경우위로 향하던 도중, 양 옆에 길이 있으면 그 길로 빠져야함가로선이 다른 막대를 가르는 경우는 없기 때문에, 왼쪽 또는 오른쪽 길이 발견되면 바로 그쪽 길로 향하면 됨update direction옆의 길이 발견되지 않으면 계속 위로 이동현재 방향이 오른쪽으로 향하는 경우현재 위치의 오른쪽에 길이 있으면 계속 오른쪽으로 이동길이 막히면 위로 이동, update direction현재 방향이 왼쪽으로 향하..
문제문제 바로가기풀이처음에는 모든 경우의 수를 탐색하면서 Set에 추가하여 풀었지만 시간초과.문제는 최대 100가지 이므로, 경우의 수는 2^100 이고 당연히 시간 초과가 발생한다.DP를 사용하여 문제 해결각 배점을 탐색하면서 만들 수 있는 경우의 수를 DP에 기록해당 배점을 선택하기 이전까지 DP배열에 기록된 모든 값들 + 현재 탐색중인 배점을 DP 배열에 기록위의 방식대로 계속해서 배점 탐색최종적으로 DP 배열에 기록된 갯수를 출력코드import java.util.*;// dp로 탐색// 최대 점수만큼의 크기를 가지는 dp 배열 생성// 1. 한 문제씩 선택// 2. 해당 문제를 dp배열에 기록// 3. 지금 까지 기록된 dp배열에 선택된 문제를 더한 값도 dp에 기록// 4. 계속 문제 선택하면서..
문제 풀기문제 설명풀이DP(Dynamic Programming, 동적 프로그래밍)를 이용하여 해결 가능한 문제완전 탐색을 이용해서도 해결 가능해 보이지만, 그럴 경우 프로그래머스 효율성 검사에서 걸리지 않을까 싶다.피라미드 꼭대기에서부터 내려오면서, 거칠수 있는 최대값을 기록할 2차원 배열을 사용한다.위에서 생성한 배열을 사용하여, 꼭대기에서 부터 해당 위치까지의 최대값을 기록한다.여기서 윗줄의 값의 경우, 이미 꼭대기에서 부터 모든 최대 경우를 반영하고 있기 때문에 바로 윗줄의 케이스만 고려하면서 값을 채워나가면 된다.코드import java.util.*;class Solution { public int solution(int[][] triangle) { // dp 배열 초기화 ..
문제 설명제한 사항입출력 예문제 풀이while문으로 모든 작업이 배포될 때 까지 반복, 여기서 while문의 반복 한번은 하루를 의미while문 안에서 for문을 사용하여 각 작업 현황 업데이트for문을 반복할 때, 작업이 완료된 기능의 경우 바로 배포가 되지 못함, 앞의 작업이 완료 되어야 배포 가능)이미 배포 완료된 작업을 순서대로 기록해야, 현재 작업이 배포 가능한지 확인 가능Stack을 사용하여 배포 완료한 작업을 기록(지금 생각해보면 그냥 int변수로 마지막에 배포한 작업만 기록해도 되지 않을까 싶음)마지막에 기록한 작업 다음이 자신의 차례이면 배포, 이때 배포 횟수 기록. 여기서 배포 횟수는 while문을 돌 때마다 초기화 됨for문을 다 돌고 나서, 배포 횟수가 1번 이상이면 리스트에 기록코..
* 우테코 코딩테스트 준비로 인해, 자바로 문제 풀이문제 설명선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.예를 들어 A가 B에게 선물을 5번 줬고, B가 A에게 선물을 3번 줬다면 다음 달엔 A가 B에게 선물을 하나 받습니다.두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.선물 지수는 이번 달까지 자신이 친구들에게 ..
