1. 문제 설명 📌문제 링크벨만 포드 알고리즘 공부하고 한 번 써보라는 견본 문제이다.주어지는 간선 정보는 모두 단방향이다.2. 구현 방법 🗃️KEY WORD: BELLMAN-FORD ALGORITHM0️⃣ 형태로 모든 간선을 저장, 최소 비용 배열인 dist [] 선언.(N: 정점의 수, M: 간선의 수, dist 배열은 Long.MAX_VALUE로 초기화)1️⃣ 출발지를 1로 설정하고, N-1만큼 모든 간선을 돌면서 다음 구문을 실행한다.1️⃣-1) 현재 조회중인 간선의 출발지를 A, 도착지를 B, A➜B의 가중치를 C라고 할 때,dist[A] != ∞︎︎ && dist[B] > dist[A] + C이면, dist[B] = dist[A] + C로 최신화 해준다.2️⃣ 위 과정을 끝낸 후, 벨만 ..

1. 문제 설명문제 링크서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다. 2. 접근 방식인접 리스트 형태로, 노드와 연결 정보를 저장한다. 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다. 따라서 BFS를 돈 횟수만큼 군집체가 존재하는 것이므로, BFS를 실행한 횟수를 반환하면 된다.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int n, int[][] computers) { ..

1. 문제 설명문제 링크(1) 일거리의 시작 시간, 끝 시간, 일을 끝냈을 때의 이익 이 주어진다.(2) 시작 시간과 끝 시간의 범위가 겹치는 일은 같이 하지 못한다. 반면 어떤 일이 끝나자마자 다른 일은 시작할 수 있다.예를 들어, job A의 끝 시간이 3시 이고 job B의 시작시간이 3시이면 두 일 거리는 연달아 할 수 있다. 반면 job C가 3~5시이고 job D가 4~6시이면 두 일은 일의 시간 범위가 겹치므로 같이하지 못한다.(3) 이때, 겹치지 않게 일을 해서, 최대 이익을 얻으려고 한다. 주어진 일거리들 중에서 가질 수 있는 최대 이익은 몇인가?2. 접근 방식KEY WORD: DP(1) 주어진 문제가 시작시간, 끝시간, 이익을 따로 따로 주기에 이를 하나의 일(job) 단위로 하나로 묶..

1. 문제 설명문제 설명2. 접근 방식KEY WORD : BACK-TRACKING(0) 사전 세팅1차원 배열(arr)을 n의 크기만큼 만들고 배열의 index = 행 , 배열의 value = 열로 생각한다.예를 들어 배열이 다음과 같을 때, 그림으로 나타내면 이렇게 된다.index(행)0123value(열)1302(1) 만약에 arr[i] = j 라고 한다면 2차원 배열 [i] [j] 에 퀸을 두겠다는 소리이다. 이게 가능한지 체크한다. 체크하는 방법은0 ~ i-1 까지의 배열 값을 이용해, 이전에 놔둔 퀸의 공격 경로와 겹치는지 확인하면 된다. 확인법은 다음과 같다.(1-1) 좌하단 확인대각선이 일치하는 값들은 모두 행+열의 합이 같다. 이를 이용한다. 우리의 경우는 index가 행이고 value가 열..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: 브루트 포스(1) 문자열로 받은 숫자를 한 자릿수가 되게 나누어서 배열에 저장한다.(2) 전체 숫자가 n개라면 그 중 k개를 뽑아서 나열한다. (순열, k = 1 ~ n )(3) 나열된 k개의 수를 합쳐서 하나의 숫자로 만들고, 소수 판별한다. (소수 판별법 이용)(4) 소수 판별이 확정되면 해당 수가 이전에 나왔는지, hashSet으로 체크한다. 없으면, 소수의 개수를 +1 올린다.  ※추신※(1)나는 한자리 수를 합치는 것을 원래의 수 * 10 + 새로 들어온 한 자리 수로 그때 그때 바로 했다.(2)소수 판별법을 모른다면, 정리 잘 한 사람 링크를 보고 오기 바란다. 해당 링크에서는 왜 n의 제곱근까지만 나눠서 확인하면 되는지 나와있다.(3)소..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: 이분 탐색무엇을 기준 으로 이분탐색을 해야할까?이분 탐색 문제를 풀 때, 제일 어려운 부분이다. 어려운 문제일수록 무엇을 기준으로 이분 탐색을 해야할지 감이 서지 않는다. 나 또한 그랬다. 그래서 다른 사람의 풀이 아이디어까지 봤다. 분명 1년 전에 같은 문제를 백준으로 풀었는데, 안 떠올라서 좀 좌절 했다 ㅜ(1) 기준 : M 시간 당 각 심사대에서 처리하는 사람의 수내 기준에서 어려웠던 점은 규칙 - 심사대가 비더라도, 사람은 다른 심사대가 빌 때까지 기다렸다가 들어갈 수 있다. 였다. 이 자율성 때문에, 문제의 유형을 생각하지 못한 것 같다. 하지만 기억해야할 점은, 무엇을 이분 탐색 해야할지 모르겠을 때는, 반환하는 답을 기준으로 탐색할 것이..

1. 문제 설명문제 링크2. 접근 방식이건 뭐 Priority Queue 쓸 줄 아냐고 묻는 문제였다.PQ를 만든다. (default로 오름차순 정렬이니 건들일 것이 없다.)문제에서 제공하는 Order에 따른다. (0이면 출력, 나머지면 저장)3. 코드 분석import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PriorityQueue pq = new PriorityQueue(); ..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: GREEDY문제 설명 그대로 Queue 두 개를 만든다.총합이 큰 쪽의 queue.peek()을 poll 해서 다른 쪽 큐에 추가한다.2번 종료 후 두 큐의 총합이 같은지 검사한다.만약 같으면, 2번을 행한 횟수를 출력한다. 만약 두 큐의 총 길이 + 1 만큼 해도 두 큐의 합이 같지 않으면 -1을 출력하고 종료 한다.두 큐의 총 길이 + 1 만큼 반복해야 하는 이유는 뒤에서 설명.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int[] queue1, int[] queue2) { ArrayDeque a = new ArrayDeque()..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: Sorting, HashMap음악 객체를 만든다. ( 멤버 변수: 자신의 고유번호, 장르, 플레이 횟수 )입력 값들을 전부 음악 객체로 바꿔서 ArrayList에 추가한다.HashMap을 만든다. Key = 장르 , value = 장르에 해당하는 곡들의 플레이 총합2번에서 만든 ArrayList를 정렬한다. 정렬 기준은 문제 그대로다. -> Comparator를 단순화한 Lamda 식을 이용해 구현답변용 ansList를 만들고, 답변에 장르별로 몇 번 들어갔는지를 나타내는 genreAddedCount라는 HashMap도 하나 더 만든다.genreAddedCount는 Key = 장르, value = 장르 별로 답변 List에 나온 횟수 이다. .get..

1. 문제 설명문제 링크2. 접근 방식부분 문자열은 크기 1부터 N/2까지만 생각하면 된다. (N = 문자열의 길이)왜냐하면, 부분 문자열의 크기가 절반 이상이면 반복이 불가하므로, 세는 의미가 없다. 1번에서 정한 문자열 크기만큼 처음부터 자른다. 이 행위는 0 ~ N - i 까지만 반복한다. 부분문자열을 구하는 substring(startIndex, endIndex)에서 endIndex가 배열의 범위를 넘어가면 예외가 발생한다. 우리는 substring(startIndex, startIndex+i)만큼 항상 할 것이므로, endIndex가 배열의 범위를 넘어서지 않도록 반복의 범위를 위와 같이 정한다.최초 자른 부분 문자열은 중복 체크가 불가하므로 이전 문자열(이하 prev)에 저장한다.이전 문자열과..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: Brute forcekey=String, value=Integer인 map에 문자로 표현한 숫자 =int형 숫자로 1~9까지 모든 숫자를 저장한다.포인터를 하나 사용하여 해당 포인터가 가르키는 값을 word 란 StringBuilder에 저장한다.(1) word의 길이가 3이상이면 map에 해당 값을 key로 가지는 값이 있나 계속 확인(2) 있으면 해당 수를 숫자로 바꾸어 답변이 되는 ans에 저장하고 word를 비운다.(3) 없으면 포인터를 한 칸 이동하여 word를 또 채운다.(4) 만약 숫자라면 ans에 값 저장하고 바로 건너 뛰기.3. 코드 분석import java.io.*;import java.util.*;class Solution { ..