hansjour 개발일지

문제 파악-주어진 k부터 n까지 최소 거리를 구하는 문제-다익스트라 함수 구현하기-가중치 = 시간접근 방법-Edge, Entry 클래스로 구조체형태 만들기-우선순위 큐를 활용해 거리가 짧은 노드들부터 순회-큐에 들어간 원소를 전부 비워낼 때까지 while문 돌며 distance가 최소거리인지 체크-(+) 그와 연결 된 노드들과의 거리도 최소거리인지 체크-절대적인 최솟값 거리를 저장하는 distances 배열 통째로 리턴⇒ 왜? 특정 노드 n까지의 최소거리가 아니라, 모든 노드를 순회할 때의 최솟값이기 때문.(순서가 있는 그래프가 아니므로 n까지 != 최댓값임)-리턴받은 최솟값 모음 배열을 돌며 가장 그 중 가장 오래 걸린 시간을 찾는다.(max)코드 구현import java.util.*;class Sol..

문제 파악-dp활용  제한 사항1 1 0 접근 방법-0~n까지 현재 금액 누적해가기(for문)-금액 도달 전까지 누적해가며 dp 수행, 수행하면서 대상 값을 업데이트해가며 돌려줌(amount-coin)-완전탐색으로도 구현이 가능하나 효율성에서 문제 발생!!-메모이제이션 활용) n번째 계단처럼, n번째 값까지의 최소값을 하나하나 메모해두고계산하지 않은 것만 dp수행, 이미 계산된 것은 배열 안에서 골라서 result값 갱신하기코드 구현import java.util.*;class Solution { public int solution(int[] coins, int amount) { int[] memory = new int[amount+1]; Arrays.fill(memory,I..

문제 파악-dp를 이용해 구현한다.Constraints:2 0 접근 방법-bottom-up 방식으로 구현한다.-n(cost.length) 계단까지 최소비용을 구하기 위해 최소비용 배열 선언하여 메모하기-마지막 계단에 해당하는 최소 비용 리턴코드 구현import java.util.*;class Solution { public int minCostClimbingStairs(int[] cost) { //memoization initialization int[] dp = new int[cost.length+1]; for(int i=2;i배우게 된 점처음에 첫 계단 혹은 둘째 계단에서 시작할 수 있으므로 둘 다 비용 계산 의미 없음고로 2번째 계단에서부터 ..

문제 파악-저번 실습으로 나온 문제. 각 방을 돌며 최초의 좌석 찾고 그로부터 되는 방향을 나아가며 거리가 2 이내에 좌석이 발견되면 false리턴places의 행 길이(대기실 개수) = 5places의 각 행은 하나의 대기실 구조를 나타냅니다.places의 열 길이(대기실 세로 길이) = 5places의 원소는 P,O,X로 이루어진 문자열입니다.places 원소의 길이(대기실 가로 길이) = 5P는 응시자가 앉아있는 자리를 의미합니다.O는 빈 테이블을 의미합니다.X는 파티션을 의미합니다.입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.return 값 형식1차원 정수 배열에 5개의 원소를 담아서 return 합니다.places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로..

문제 파악-주어진 2차원 배열은 서로 간선으로 연결 된 관계-주어진 그래프에서 최대 거리에 있는 노드 갯수를 구하기노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.접근 방법💡 -각 노드와 연결관계를 파악하고 인접리스트 형태로 변환하여 진행-bfs 를 이용하여 해당 그래프의 순회 거리를 구하고 최대 거리의 노드 갯수 구하기-방문 노드는 제외하고 큐 순회를 한다.-간선 별로 몇번 째로 순회하는지 세기 위한 cnt와 직관적으로 보기 편한 리스트 구현하기 코드 구현import java.util.*;class Solution { public ..

문제 파악-서로 이어져있는 그래프의 간선을 ‘하나’ 끊었을 때, 두 개로 나누어진 그래프를 각각 순회-순회 시 방문 노드를 카운트하여 리턴하고, 각 순회가 끝났을 때 두 그룹의 카운트 차를 비교-최솟값을 갱신하여 최종 리턴n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.1 ≤ v1 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.접근 방법💡 -BFS를 이용하여 각 노드를 순회 -그래프를 둘로 쪼갤 때 ⇒ 간선을 순회하며 하나씩 다 삭제해보기(O(n))-인접리스트 형태로 ..

https://leetcode.com/problems/number-of-islands/ 문제 파악-2차원 배열이 주어지고, 1이 상하좌우로 있는지 체크하여 섬이 총 몇 개 있는지 센다. (분기체크)m == grid.lengthn == grid[i].length1 grid[i][j] is '0' or '1'.접근 방법-0은 물, 1은 섬. 물 만나거나 범위 벗어나지 않는 이상, 섬 한 덩어리로 본다.-1이면 계속 순회하며 visit 체크(무한 루프 방지)-처음 기준 노드는 ‘1’ 나오면 시작. 타고 가서 상하좌우 dfs 체크⇒ 막히면 return되고, 다른 방향으로 탐색 시작-If 0이거나, 벽이면 순회 끝(base case)코드 구현import java.util.*;class Solution { p..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/문제 파악-방향을 탐색하는 문제-최소 거리를 구하는 BFS문제n == grid.lengthn == grid[i].length1 grid[i][j] is 0 or 1 접근 방법💡 -좌표 (x,y) -큐에서 poll()하여 방향에 따라 더하거나 뺀다.-8방향은 0,0 기준점을 기준으로 둘러싼 방향-8방향을 2차원 배열로 미리 선언해두어 for문으로 조회하고 현재 값에 더한다.1)시작점 혹은 끝점이 0이 아니거나,2) 끝점까지 가는 명확한 길이 없다면 즉, 큐 순회가 끝날 때까지 끝점에 도달하지 못하고 가는 길이 끊긴다면⇒ -1 리턴 코드 구현class Solution { ..

문제 파악-시작점(1,1)에서 도착점(n,m)까지 최단 거리를 구하기maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.접근 방법💡 -배열은 (0,0)부터인데 지문은 (1,1)이기 때문에 일관성있게 0based index유지해야함-(첫트) DFS : Integer.MAX_VALUE로 최대한 큰 값 넣어..

문제 파악-시작점에서 도착지점까지 한 칸씩 이동하며 카운트하기-레버 만나야 도착지점으로 갈 수 있음5 ≤ maps의 길이 ≤ 1005 ≤ maps[i]의 길이 ≤ 100maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.S : 시작 지점E : 출구L : 레버O : 통로X : 벽시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.  접근 방법-시작점 S가 어디에 있는지 먼저 찾아서 거기서부터 각 방향으로 갈 수 있는지 유효성 검사(isValid)-갈 수 있는 방향 따라 가면서 큐에 가능한 경로 좌표 담기-bfs를 활용해 도착지점까지 최소거리 구하기(큐에 담을 때는 x..