기록방

👉 문제링크🔸 문제 분석 🔸N x M 직사각형 땅에 수영장을 만든다. 격자 속 숫자가 해당 땅의 높이이다.물을 채워야 하는데, 물은 상하좌우 높은 곳에서 낮은 곳으로만 흐르고 격자 밖으로는 무한정 흘러나가 버린다.채울 수 있는 물의 양의 최대값을 출력한다.🔸 문제 풀이 🔸상하좌우 인접 땅으로 흐르는 물의 이동을 구현하기 위해서 BFS를 사용한다.외각에 붙은 땅은 물이 고일 수 없으므로, 역방향 BFS를 통해 이어진 땅들을 모두 체크한다.물이 고일 수 있는 땅들에 물을 채우고 총합을 출력한다.물 높이의 최대값은 2가지 기준을 유의해서 정한다.해당 높이보다 높아지면 물이 흘러나가버리는 경우 : 최대값의 인덱스가 체크된 경우흘러나가지는 않지만, 땅이 높아서 조금 더 높이 물이 고이는 경우 : 최대값의..

👉 문제링크🔸 문제 분석 🔸1, 2, 3의 덧셈으로 n을 만들 수 있는 조합의 수를 출력한다.🔸 문제 풀이 🔸다이나믹 프로그래밍 문제로, dp[n]은 n을 만드는 조합의 수이다.중복을 제거하기 위해 1로 한바퀴, 2로 한바퀴, 3으로 한바퀴 각각 dp를 돌려야 한다.🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;public class Main { public static void main(String[] args) throws IOException {..

👉 문제링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🔸 문제 분석 🔸N*N 행렬에서 모든 칸의 숫자(시계)를 0(12시방향)으로 만들어야 한다.0 : 12시, 1 : 3시, 2 : 6시, 3 : 9시한 칸의 시계를 시계방향으로 돌릴 수 있고, 돌리면 상하좌우 인접한 시계도 함께 돌아간다.모든 시계를 12시 방향으로 만드는 최소 조작 횟수를 출력한다.🔸 문제 풀이 🔸여러 경우의 수를 따져봐야 하는데, BruteForce는 O(64^4)이므로 너무 크다.Greedy 접근으로 풀이할 수 있다.시계를 조작하는 순서는 상관 없으므로 위쪽에서 아래쪽 행으..

👉 문제링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🔸 문제 분석 🔸문제는 쿼리 명령에 따라 n x m 격자판에서 이동하는 공의 시뮬레이션 설명이 주어진다.쿼리에 따라 이동했을 때, (x, y) 위치에 도착하는 시작 위치의 개수를 출력한다.🔸 문제 풀이 🔸n, m의 최대값은 1억이고, 쿼리의 개수는 20만이기 때문에 BFS, DFS 등으로 구현하면 시간 초과 or 메모리 초과가 난다.첫 번째 풀이 포인트는 '역방향 탐색'이다.모든 인덱스에서 쿼리를 돌려 (x, y)에 도착하는지 확인하는 것이 아니라,(x, y)부터 시작해 역으로 쿼리를 돌려 도..

👉 문제링크🔸 문제 분석 🔸N개의 지역과 M개의 횡단보도가 있다.횡단보도는 입력 순서대로 0~M-1 초에 파란불이 켜져 건널 수 있다.1번 지역부터 출발해 N번 지역에 도착할 수 있는 최단 시간을 출력한다.🔸 문제 풀이 🔸N이 최대 10만, M이 최대 70만이므로 BFS로 최단시간을 구하면 시간초과가 난다. 따라서 Dijkstra(다익스트라) 알고리즘을 이용해 최단시간을 구한다.현재 지역에서 갈 수 있는 다음 지역을 건널 때 걸리는 시간을 계산하고, 기록 된 소요 시간보다 작다면 업데이트한다.🔸 코드 🔸import java.io.*;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.Queue;import ja..