🔗 문제 링크 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 📖 풀이 과정 - 다익스트라 알고리즘 유형 문제입니다. - 다익스트라 알고리즘 개념을 이해하고 처음 접할 때 기본기를 익히기 좋은 문제입니다. - 따로 풀이는 작성하지 않겠습니다. 주석과 코드를 따라가시면 충분히 이해하실 수 있을 것이라 생각합니다 - 이번 문제는 코드만 봐주시면 좋을 것 같아요! 💻 코드 import java.io.BufferedReader; import java.io.IOException; ..
🔗 문제 링크 코딩테스트 연습 - 나머지가 1이 되는 수 찾기 자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항 입 programmers.co.kr 📖 풀이 과정 단순히 숫자를 확인하며 소수인지 판단하는 문제입니다. 아마 어렵지 않게 푸실 수 있을거라고 생각합니다. 💻 코드 class Solution { public int solution(int n) { int answer = 0; for(int i = 2; i < n; i++){ if(n % i == 1){ answer = i; break; } } return answer; } }
🔗 문제 링크 코딩테스트 연습 - 없는 숫자 더하기 0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. programmers.co.kr 📖 풀이 과정 - 단순한 구현문제입니다. - visited 배열을 이용하여 방문하지 않은 값을 확인합니다. - 방문하지 않았다면, 값을 계산합니다. 💻 코드 import java.util.*; class Solution { public int solution(int[] numbers) { int answer = 0; boolean[] visited = new boolean[10]; for(int i ..
🔗 문제 링크 코딩테스트 연습 - 방문 길이 programmers.co.kr 📖 풀이 과정 - 그래프 관련 유형의 구현 문제입니다. - 먼저, 단순히 문제를 풀려고만 하다보니 중복되는 부분도 많고, 깔끔하지 않습니다. 그렇기에 흐름?만 보시면 충분할 것 같습니다. - 중복되지 않고 방문한 곳의 최대 길이를 찾아야 합니다. - visited 배열은 4차원으로 만들어 현재 위치의 (x,y)와 이동해야할 곳의 (x,y)에 대해서 구분 지을 수 있도록 했습니다. - switch문을 통해 입력받는 알파벳에따라 각 해당하는 명령문을 수행하도록 했습니다. - 중복되는 부분이 여기서 발생하는데 해당 부분의 마지막에 중복을 없애도록 작성할 수 있을 것 같습니다. - isIn()메소드를 통해 범위 내부에 있는지 확인합니다..
🔗 문제 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 📖 풀이 과정 - BFS 유형의 문제입니다. - 특별한 조건 생각없이 하나씩 벽을 다 부숴보면서 해보려니 시간초과가 발생했습니다.(너무 문제를 안일하게 생각한 것 같습니다.) - 즉, BFS내에서 벽을 부수는 것에 대한 조건을 추가해야 합니다. - 그러므로, 내부 클래스 Point에 거리와 공사횟수에 대해 변수를 추가했습니다. - 기존에 저는 visited 2차원 배열을 boolean 타입으로 선언하여 방문을 체크했지만 이..
🔗 문제 링크 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 📖 풀이 과정 - 누적합과 다이나믹 프로그래밍 유형의 문제입니다. - 2차원 배열을 선언하여 입력 값을 할당합니다. - dp 2차원 배열을 선언하여 각 행, 열마다의 값을 누적하여 더하여 계산합니다. - 이 때, dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]의 식을 이용합니다. - 또한, 누적합을 이용하여 해당하는 범위의 값을 계산하려면, dp..
