본문 바로가기

알고리즘/PROGRAMMERS42

합승 택시 요금(Lv.3) 문제 설명 입출력 예시 요약 모든 지점을 하차지점으로 생각했을 때 각 지점에서 출발점(S), A, B 까지의 거리 중 최소값 구하기 풀이 접근 방식 1. 최소 비용 구하기 → 간선의 가중치가 1이 아니기 때문에 다익스트라 알고리즘을 통해 최소 비용 구하기 2. 하차지점 설정 → 합승을 했다면 반드시 하차지점이 생기고, 하차지점으로 부터 출발점, A도착점, B도착점까지의 거리를 계산한다. → 하차지점은 출발점(S)~하차지점, 하차지점~A, 하차지점~B 세 구간을 더한 값이 최소가 되는 노드로 설정한다. → 하차지점을 구하기 위해 모든 노드에 대해서 다익스트라 알고리즘을 실행한다. 코드리뷰 import java.util.*; // 인접 노드 번호와 간선의 가중치를 저장하기 위한 객체 클래스 class Nod.. 2024. 4. 16.
거리두기 확인하기(Lv.2) 문제 설명 입출력 예시 요약 대기실별로 맨해튼 거리가 2 이하인 응시자가 있는지 확인(단, 파티션이 막고 있는 경우 제외) 풀이 접근 방식 1. 응시자들의 맨해튼 거리가 1인 경우 → false 리턴 2. 응시자들의 맨해튼 거리가 2인 경우 → 같은 방향으로 두 칸 떨어져 있는 경우 응시자들 사이에 빈 공간(O)이 있다면 false → 대각선으로 떨어져 있는 경우 응시자의 (위쪽, 왼쪽) / (위쪽, 오른쪽) / (아래쪽, 왼쪽) / (아래쪽, 오른쪽) 위치에 빈 공간(O)이 있다면 false 코드리뷰 import java.util.*; class Solution { int N, M; String[][] maps; // 상하좌우 한 칸씩 탐색을 위한 배열 int[] dirY1 = {-1, 1, 0, 0}.. 2024. 4. 16.
리코쳇 로봇(Lv.2) 문제 설명 입출력 예시 요약 출발점(R)에서 부터 동서남북 각 방향에 대해 벽(D)에 도달하기 전까지 이동하면서 도착점(G)까지의 최단 거리 구하기 풀이 접근 방식 1. 맵 정보를 이차원 배열에 담는다. → 출발점(R)과 도착점(G)의 좌표를 변수에 저장 2. bfs를 통한 최단 거리 구하기 → 출발점에서 bfs 시작. 도착점까지 최단 거리 구하기 3. 도착하지 못하는 상황 → 미끄러지는 그림을 상상했을 때, 도착점(R)의 상하좌우 어느 한 곳에는 반드시 벽(D)이 있어야 도달 가능 코드리뷰 import java.util.*; // 위치 정보를 담을 객체 클래스 class Position { int row; int col; int cnt;// 거리가 아닌 움직인 횟수를 기록한다. public Positi.. 2024. 4. 16.
미로 탈출(Lv.2) 문제 설명 입출력 예시 요약 레버로 이동한 후 도착지점으로 이동하는 최단 거리 구하기 풀이 접근 방식 1. 맵을 구성하는 이차원 배열 만들기 → 출발지(S), 레버(L), 도착지(E)가 있는 좌표를 따로 저장 2. bfs를 활용한 최단 거리 구하기 → 출발지(S)에서 레버(L)까지 bfs시작 → 레버에 도달했다면 레버에서 도착지(E)까지 bfs 시작 → 도착지에 도달했다면 S~L 거리와 L~E 거리 합 리턴 코드리뷰 import java.util.*; // 현재 위치와 거리를 저장할 객체 클래스 class Position { int row;// y좌표 int col;// x좌표 int dist;// 거리 public Position(int row, int col, int dist) { this.row =.. 2024. 4. 16.
줄 서는 방법(Lv.2) 문제 설명 입출력 예시 요약 n명의 사람을 n!(factorial)만큼 가지수로 나열했을 경우 k번째 나열 순서 리턴 풀이 접근 방식 1. 각 인덱스의 숫자가 얼마의 반복 주기를 갖는지 확인 → n = 4의 경우 {1, 2, 3, 4} / {1, 2, 4, 3} / {1, 3, 2, 4} / {1, 3, 4, 2} / {1, 4, 2, 3} / {1, 4, 3, 2} / {2, 1, 3, 4} / ... → 첫 번째 숫자의 경우 6개, 두 번째 숫자의 경우 2개, 세 번째와 네 번째는 각각 1개의 반복 사이클을 갖는다. → n = 4의 경우 반복되는 사이클을을 배열로 나타내면 {(n-1)!, (n-2)!, (n-3)!, (n-4)!} 임을 확인 할 수 있다. 2. k를 통해 각 인덱스에 해당하는 숫자 구.. 2024. 4. 15.
배달(Lv.2) 문제 설명 입출력 예시 요약 1번 마을에서 출발해서 K 이하의 시간으로 배달 가능한 모든 마을의 개수 구하기 풀이 접근 방식 1. 방문 가능한 모든 경로 찾기 → 간선의 가중치(소요 시간)와 도착 마을의 번호를 담는 객체 클래스(Node) 생성 → graph라는 배열에 특정 마을의 인접한 마을의 Node리스트를 저장 → 마을을 잇는 간선은 방향이 없기 때문에 반대의 경우도 함께 저장 2. 최소 비용으로 마을 방문하기 → 다익스트라(dijkstra) 알고리즘을 통해 최소비용으로 방문하는 경우를 구한다. 3. 배달 가능한 마을의 개수 구하기 → K 이하의 비용이 드는 마을의 개수를 카운팅해서 리턴 코드 리뷰 import java.util.*; // 도착 지점의 번호와 간선의 가중치를 담는 Node 객체 클래.. 2024. 4. 11.

티스토리툴바