적자 생존 (Write, Survive!)

Coin Change - LeetCode문제 파악coins에는 현재 가지고 있는 동전이 들어있다. amount는 만들어야 하는 금액인데, 주어진 동전들로 이 금액을 만드는 문제 amount가 0이면 0, 주어진 동전들로 만들 수 있는 금액이 아니라면 -1을 반환한다. (coin이 0인 경우는 없다.)접근 방법0원부터 11원까지 만들 수 있는 동전의 최소 필요 수를 dp에 저장한다.11원을 만들려면? 3가지 선택지가 있음. 10원 + 1원, 6원 + 5원, 9원 + 2원이 된다.이 중에서 동전이 최소로 드는 경우를 찾는다.dp에는 필요한 최소 동전 수가 저장되어있다.점화식으로 나타내면 $dp(i) = min(dp(i-coin) + 1)$ 이 된다. 내가 처음에 실수한 포인트는 쪼개면서 amount에서 바로..

Climbing Stairs - LeetCode문제 파악계단을 오를 수 있는 칸수는 1과 2이다.이를 이용해서 자연수 n (1~45)칸을 오르기 위한 방법 수를 구하는 문제 1칸을 오르기 위해서는 1로 1가지, 2칸을 오르기 위해서는 1+1, 2로 2가지이다.3칸을 오르려면 1+1+1, 2+1 인데 2칸을 오르는 경우가 2가지이므로 총 3가지이다.접근 방법우선 1칸과 2칸을 오르는 경우가 주어져있기 때문에 기본값으로 추가한다.그리고 3의 경우를 보면 1칸을 오르는 방법 + 2칸을 오르는 방법의 수를 더한 값이다.이를 명확하게 확인하기 위해서 4칸을 보면 2칸을 오르는 3+1 , 2+2 로 구할 수 있다.3칸을 오르는 경우 3가지 + 2칸을 오르는 경우 2가지를 더하면 총 5가지가 된다. 즉, n칸을 오르..

Keys and Rooms - LeetCode문제 파악각 방에는 다음 방으로 갈 수 있는 열쇠가 있음.모든 방을 탐색하면 true, 그렇지 않으면 false를 반환하는 문제 입출력 예시Input: rooms = [[1],[2],[3],[]]Output: true 설명:0번 방을 방문해서 1번 열쇠를 획득1번 방 방문후 2번 열쇠 획득2번 방 방문 후 3번 열쇠를 획득3번 방 방문을 마지막으로 방 탐색 종료, 모든 방 탐색을 마쳤으므로 true 반환 접근 방법다음 방으로 넘어가고 탐색하는 것은 BFS/DFS로 쉽게 구현할 수 있지만 모든 방을 탐색했을 때 확인하는 것이 까다로운 문제이다.그래서 기존 방식처럼 배열 형태가 아닌 HashSet을 이용해서 방문처리를 하여 모든 방을 방문했을 경우 HashSet의..

https://leetcode.com/problems/two-sum/문제 파악숫자 배열이 주어지고 배열에서 두 수의 합이 target이 되는 숫자들의 인덱스를 구하는 문제접근 방법반복문으로 하나씩 처리메모이제이션나는 메모이제이션으로 처리함.해시테이블에 숫자와 타겟에서 숫자를 뺀 값을 저장반복문에서 nums[i]가 해시테이블의 값에 들어가있으면 인덱스 반환→ 문제점… 해시테이블 안의 숫자의 인덱스를 구할 방법이 없음해결방안숫자와 인덱스를 해시테이블에 저장필요한 숫자가 해시테이블의 key 에 저장되어있으면 해당 value = 인덱스 정보를 호출해당 인덱스와 현재 인덱스를 배열로 반환코드 구현class Solution { public int[] twoSum(int[] nums, int target) { ..

House Robber - LeetCode문제 파악인접한 두 집을 털면 신고가 들어감.즉, 떨어져 있는 집을 털어야 하는데 이 금액이 최대가 되어야 하는 문제접근 방법dp[0]에 n/2까지 반복하는걸로 초기화 해야하나..? → 굳이 할 필요가 없음.dp[i]는 i번 째까지 털 수 있는 최대 금액을 저장dp[0] = nums[0]dp[1] = max(nums[0], nums[1]) 첫번째, 두번째 집에서 털 수 있는 값을 저장i-1번째와 i-2번째와 i번째의 금액을 더한 것을 비교해서 더 큰 값으로 갱신 → 인접할 수 없기 때문에 i-1까지의 값과 비교값이 0이거나 하나일 경우에 예외처리dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])코드 구현class Solution..

https://leetcode.com/problems/path-with-maximum-probability 문제 파악무방향 그래프가 주어지고, 각 간선에는 가중치가 확률로 주어져있다.시작 노드와 끝 노드가 주어지고, 끝 지점에 도달하는 최대 확률을 구하는 문제 입출력 예시Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2Output: 0.250000.5 * 0.5 이기 때문에 최대 확률은 0.25가 된다.접근 방법가중치 그래프이기 때문에 다익스트라 알고리즘을 사용한다.최소 비용이 아닌 최대 확률이기 때문에 우선순위는 큰 수부터 나오도록 설정해야 한다. 구현 순서인접리스트 초기화무방향이므로 둘 다 연결..

https://leetcode.com/problems/minesweeper/description/ 문제 파악클릭하는 좌표가 주어지고 맵에 있는 지뢰를 찾는 문제지뢰를 클릭하면 'X'로 바꾸고 종료, 지뢰가 아니라면 지뢰가 근처에 있을 때 '1', 근처에 없다면 'B'로 맵을 바꾸게 된다.암시적 그래프의 탐색 문제이지만 최단거리를 찾는 문제는 아니다.그래도 BFS 탐색이 더 편해서 BFS로 진행하였다.접근 방법지뢰를 클릭하면 바로 종료탐색을 하면서 방문하면 'B'로 바꾼다.만약에 인접 노드가 지뢰라면 '1'로 표기지뢰를 체크하기 위해서 지뢰 카운트를 따로 체크하고, 체크가 되었을 경우에만 바꾸도록 지시한다.탐색을 마치면 최종 배열을 반환코드 구현import java.util.*;class Solution ..