잡아랑 자바왕 잡아랑 자바왕

문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 접근법 이런 그래프 문제는 보통 인접 배열보단 인접 그래프로 푸는게 좋아서 인접 그래프를 사용했다. result 배열에는 각 마을까지 가는데 걸리는 시간들을 담겨있다. dfs를 통해서 풀었고 1번 마을은 무조건 배달이 가능하기 때문에 answer는 1로 초기화한 상태로 풀었다. 코드 import java.util.ArrayList;..

문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 접근법 처음에는 이중 포문을 사용해서 풀었는데 역시나 시간 초과가 났다. 고민을 오랫동안 했는데도 풀지 못해서 결국 다른 코드를 참고했다. 슬라이딩 윈도우 프로토콜 방식으로 풀어낼 수 있었다. 앞에서 부터 순서대로 보석들을 고르다가 중복된 보석이 나오면 시작 인덱스를 하나씩 밀어주는 방식을 사용했다. 자세한 설명은 코드에 주석을 포함하였다. 코드 import java.util.*; class Solutio..

문제 https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 접근법 백트래킹에서 가장 대표적인 예로 나오는 N-Queen 문제이다. 대표적인 백트래킹 문제임에도 풀기가 힘들었다. 처음에는 이차원 배열을 사용해서 풀려고 했는데 복잡했고 col이라는 일차원 배열을 만들어서 col의 값을 row 인덱스를 배열에 넣어주었다. ex) col = { 2, 4, 1, 3} 같은 라인 또는 대각라인에 여왕이 존재하면..

문제 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 접근법 효율성 문제였기 때문에 이분탐색으로 풀 생각 먼저 했다. 배열의 가장 작은 값과 가장 큰 값을 구하고 그 사이의 값을 이분탐색하면서 답이 될 수 있는 값 중에 가장 큰 값을 찾았다. 코드 class Solution { public int solution(int[] stones, int k) { int answer = 0; int min = getMin(stones); int max = getMax(stones); while(min = mid){ cnt = 0; /..

문제 https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대�� programmers.co.kr 접근법 하노이 탑이 재귀의 대표적인 예시임에도 풀기가 힘들었다. https://shoark7.github.io/programming/algorithm/tower-of-hanoi '하노이의 탑' 이해하기 '하노이의 탑' 문제를 이해하고 문제 해결을 위한 핵심 통찰을 살핀 뒤 코드로 작성합니다. 이후 탑의 개수에 따른 총 이동 횟수를..

문제 https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족 programmers.co.kr 접근법 문제는 쉬운 편이었다. 문제에서 말하는 최고의 집합이 되기 위해선 모든 집합의 숫자가 다 비슷해야한다. 무슨 말이냐 만약 n=3이고 s=10이라고 가정했을때 {3, 3, 4}가 최고의 집합이 된다. {2, 2, 6} , {2, 3, 7}, {4, 2, 4} 등등 어떠한 집합도 {3, 3, 4}보다 곱이 클 수가 없다. 그래서 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 접근법 처음에는 재귀로 모든 경우의 수를 찾고 k 번째 경우의 수에서 재귀를 멈췄다. 이런 방법으로 하면 k가 long으로 선언된 변수이므로 너무 많은 재귀가 돌아갔다. 그래서 찾은 방법은 k를 줄여나가는 방식이다. 숫자가 n 개인 경우에 정렬할 수 있는 모든 경우의 수 점화식은 dp[n] = dp[n-1] * n 이다. 숫자가 1개일 때는 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 접근법 야근지수의 최소값을 찾기위한 방법을 먼저 찾아야했다. 내가 생각한 방법은 works 배열에 있는 값들 중 남은 일의 작업량이 가장 많은 순으로 작업을 진행하는 것이다. 그렇기 위해서 남은 일의 작업량들이 역순으로 정렬이 되어있어야한다. 남은 일의 작업량의 역순을 유지하기 위해서 우선순위 큐를 사용했다. 우선순위 큐를 돌면서 최대값을 p..