My Tech Blog (Algorithm/Programmers_Best)

📑 1. 문제설명💡 2. 접근방식 풀이방법1. dp[][] 배열 선언 2. 첫 번째 줄 값 채우기 (dp[0][0] = triangle[0][0])2. 왼쪽 첫번째 열인 dp[i][0] 값은 이전 줄의 첫 번째 값끼리 더해서 입력한다. (dp[i][0] = dp[i-1][0] + triangle[i][0]) 3. 그 외의 값들은 위쪽과 왼쪽에서 오는 값을 비교하여 최대값을 더하기(dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]) 즉, 위쪽에서 오거나 왼쪽 위에서 온 값 중 더 큰 값에 현재 triangle[i][j] 값을 더한다. dp[][] 배열 선언나처럼 수학을 어려워하는 사람들을 위해 배열을 눈으로 보기 쉽게 시각화 해 보았다.코..

📑 1. 문제설명계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다.  가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항격자의 크기 m, n은 1 이상 ..

📑 1. 문제설명💡 2. 접근방식자료 만들 생각에 벌써부터 피곤하다. 하하하 문제 풀이에 앞서, 명색이 그래프 문제인 만큼 그래프에 대해 간략히 설명하고자 한다.2-1. 그래프의 구조노드: 원(circle)으로 표시하고, 숫자로 번호를 적는다.간선: 노드를 연결하는 선(segment)으로, 모든 간선이 양방향임을 보여주기 위해 화살표 없이 직선으로 그린다.return 하고자 하는 값은 1번 노드에서 가장 멀리 떨어진 노드의 수 이다.즉 1번 노드에서 다른 노드들로 이동하는 최단 거리를 계산해서 최단 거리가 가장 먼 노드들이 몇 개인지를 구해야 한다. 2-2. 해결 방법(1) 인접 리스트로 그래프 만들기 List> graph = new ArrayList(); 예를 들어 문제에서 제시된 vertex ..

📑 1. 문제설명💡 2. 접근방식n명의 선수가 있을 때, 각 선수는 모든 다른 선수와 경기를 하여 n-1번의 승패를 기록한다.즉, 전체 승패 결과만 있으면 각 선수의 상대적 위치를 정확히 판단해서 순위를 확정 할 수 있다. 승패를 통해 순위를 결정하는 방법은 간단히 말하면 모든 선수들 간의 직접적인 경기 결과를 반영하는 것이다. 예를 들어, 선수 i와 선수 j가 경기를 하여 승패가 결정되면, 그 결과를 기록한다.  플로이드 워셜(Floyd-Warshall) 알고리즘모든 쌍 최단 경로(all-pairs shortest path)를 구하는 알고리즘으로 그래프의 모든 노드 쌍에 대해 가장 짧은 경로를 찾는 알고리즘이다. 이 알고리즘을 사용하면 그래프의 모든 노드에 대해 다른 모든 노드로 가는 최단 경로를 ..

📑 1. 문제설명💡 2. 접근방식동적계획법(Dynamic Programming)이란?동적 계획법을 아주 쉽게 설명하자면, '이미 계산한 건 기억해 두었다가, 다시 하지 말자'는 전략이다.동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 동일한 하위 문제를 다시 계산하지 않도록 하는 알고리즘 설계 기법이다. 주로 최적화 문제나 조합 문제를 효율적으로 해결할 때 사용된다. 동적 계획법에는 Top-Down 방식인 메모이제이션과 Bottom-Up 방식인 테이블링이 있다.  Top-Down (메모이제이션)재귀를 사용하여 문제를 해결. 하위 문제의 결과를 저장하여 중복 계산 방지Bottom-Up (테이블링)작은 문제부터 차례대로 해결..

📑 1. 문제설명💡 2. 접근방식이 문제는 너무 어려워서 스스로 풀기 힘들어서 검색의 도움을 받음.주어진 문제는 그래프 이론의 최소 신장 트리(MST, Minimum Spanning Tree) 문제이다. 이 문제를 풀기 위해 필요한 전제지식- Union-Find(유니온 파인드) 자료구조- Kruskal's Algorithm (크루스칼) 알고리즘 Kruskal's Algorithm (크루스칼 알고리즘)크루스칼 알고리즘은 위에 말한 최소신장트리(MST)를 구하는 알고리즘이다. 문제의 분류 답게 greedy알고리즘으로 결정의 순간마다 최선의 결정을 함으로서 최종적인 답을 구하는 방식으로 모든 정점을 최소 비용으로 연결할 수 있게 해준다.크루스칼 알고리즘의 핵심은 모든 간선을 가중치 기준(여기서는 다리 개설..

📑 1. 문제설명💡 2. 접근방식입출력 예로 주어진 route 배열을 막대그래프로 그려 봤다. 최소한의 카메라를 배치해야 하므로 구간 종료 위치를 기준으로 오름차순 정렬 차량이 구간에서 카메라를 단 한 번만이라도 만나면 됨종료 지점에서 다음 구간과 겹치게 되므로 최소한의 카메라를 배치가능카메라 배치는 도로의 가장 왼쪽 끝부터 탐색하며 시작된다.입출력 예시에서 MIN_VALUE인 -20 지점부터 오른쪽으로 가며 종료구간과 시작구간이 겹치는 부분에 카메라가 배치된다.구간 중 가장 처음으로 만나는 종료 위치는 -15이다.따라서 이 위치에 첫 번째 카메라를 설치한다. 그리고 -13지점에서 현재 구간과 다음 구간이 만나지만 이미 해당 구간에는 카메라가 설치 완료 되었으므로 스킵한다. 그리고 다음 구간인 [-..

📑 1. 문제설명💡 2. 접근방식 문제 제한조건1. 한 번에 최대 두명까지 보트에 태울 수 있음2. 몸무게 합이 `limit` 이하여야 함 따라서 최소보트를 사용하는 전략을 짜려면 배열을 정렬하여 가장 가벼운 사람 + 가장 무거운 사람 조합을 짝지어야 함.가장 큰 몸무게를 가진 사람을 최대한 빨리 처리하면서도 보트 사용을 줄일 가능성이 높기 때문이다.만약 두 사람의 몸무게 합이 limit 이하라면, 한 보트에 태울 수 있다. 합이 limit을 초과한다면, 무거운 사람을 반드시 한 명만 보트에 태워야 한다.이렇게 하는 것이 남은 사람들을 효율적으로 처리하기 위한 최선의 선택이다. ⭐ 3. 정답코드import java.util.*;class Solution {    public int solution(i..