돌고 돌아 기본

프로그래머스 12978번 - 배달 요구사항 1. N개의 마을 중 K 시간 이하로 배달이 가능한 마을의 개수를 반환하라. 2. 서로 다른 마을 간에 이동할 때는 도로를 지나야 합니다. 3. 도로를 지날 때 걸리는 시간은 도로별로 다르며, 두 마을을 연결하는 도로는 여러 개가 있을 수 있습니다. 요구사항 분석 및 풀이과정 1. 전형적인 최단경로 알고리즘 문제입니다. 2. 주어진 도로 정보들로 그래프를 구축하여 최단경로 알고리즘 중 편한 알고리즘을 사용하면 됩니다. 3. 저는 다익스트라 알고리즘을 사용하도록 하겠습니다. 4. 1번 마을에서 각 마을(1번 마을 포함)까지의 최단 배달 시간을 구한 후, K 이하인 마을의 개수를 세어줍니다. 소스코드 작성 import java.util.ArrayList; impor..

프로그래머스 70129번 - 이진 변환 반복하기 요구사항 1. 0과 1로 이루어진 문자열이 "1"이 될 때까지 계속해서 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 반환하라. 2. 0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환은 다음과 같이 정의합니다. 1단계 : x의 모든 0을 제거합니다. 2단계 : x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다. 요구사항 분석 및 풀이과정 1. 이진 변환에서 중요한 점은 1단계도 중요하지만, 결과적으로 1단계를 거친 결과의 길이가 중요합니다. 그 길이는 다음과 같습니다. 1단계를 거친 결과의 길이 = c = 문자열 x의 길이 - 0의 개수 2. 1단계를 거친 결과의 길이 c..

프로그래머스 1844번 - 게임 맵 최단거리 요구사항 1. 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 반환하라. 2. 검은색 부분은 벽이며, 벽으로 막힌 칸은 지나갈 수 없습니다. 3. 게임 맵을 벗어난 칸은 갈 수 없습니다. 4. 캐릭터는 (1, 1) 위치에 있으며, 상대 팀 진영은 (n, m) 위치에 있습니다. 요구사항 분석 및 풀이과정 1. 이 문제와 같은 방법으로 풀면 됩니다. 2. 다른 점은 그래프(또는 트리)로 구성된 것이 아니라 배열로 구성되어있다는 점입니다. 3. 게임 맵을 벗어나지 않고, 벽으로 막힌 칸은 지나갈 수 없는 점을 고려하여 4방향으로 BFS 탐색을 진행하면 됩니다. 4-1. 각 칸에 처음 도착했을 시점에 지나온 칸의 개수가 캐릭터의 시작 점에..

프로그래머스 43105번 - 정수 삼각형 요구사항 1. 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 최댓값을 반환하라. 2. 단, 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 요구사항 분석 및 풀이과정 1. 주어진 삼각형은 시각적인 표현이고, 삼각형을 배열로 보면 다음과 같습니다. 2. 시각적으로 표현된 삼각형 기준으로 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽이기 때문에, 위 모양을 기준으로는 아래 방향 또는 우측 하단 대각선 방향으로만 이동이 가능합니다. 3. 2번을 경유해오는 칸을 도착하는 칸을 시점으로 보면 왼쪽 상단 대각선 방향 또는 위쪽 방향에서 올 수 있습니다. 그림으로 표현해보면 다음과 같습니다. 4. 3번..

프로그래머스 42898번 - 등굣길 요구사항 1. 물에 잠기지 않은 지역을 통해 학교로 가려고 합니다. 단, 오른쪽과 아래쪽으로만 움직일 수 있습니다. 2. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1, 000, 000, 007로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. 오른쪽과 아래쪽으로만 움직일 수 있다는 뜻은 특정 지역을 기준으로 해당 지역으로 들어오는 방향이 왼쪽과 위쪽밖에 없다는 것을 의미합니다. 2. 따라서 집에서 각 지역까지 갈 수 있는 최단경로의 개수를 dp[지역]이라고 하면 다음과 같습니다. dp[지역] = dp[왼쪽 지역] + dp[위쪽 지역] 3. dp[지역]을 코드로 옮기기 위하여 지역을 좌표 정보로 표현하여 점화식을 정리하면 다음과 같습니다. 단, 집의 위치는..