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: DATA STRUCTURE(0) 현재 조회 중인 수를 value, 출력해야 하는 수를 now라고 해보자.(1) value (2) stack의 top과 now를 비교한다.(3) top이 크면 어떤 방법을 써도 수열을 만들 수 없다. NO를 출력하자.(왜냐하면, 수열은 무조건 stack에서 pop되는 값으로 만들어야 하기 때문이다. stack에는 오름차순으로 값이 저장되기에, 현 stack의 top 값이 크다고 새로 push를 받으면 더 큰 값밖에 들어오지 않는다. stack의 top이 now보다 작을 때는 같은 값이 들어올 때까지 기다리면 되는 것과 상반된다.)(4) top == now 이면 stack에서 pop해서 값을 뺀다.Stack은 진짜 sta..

1. 문제 설명2. 접근 방식KEY WORD: BFS, IDEA해당 문제는 문제를 풀기 위한 IDEA만 생각해낸다면 간단한 BFS 문제이다. 문제에 대한 접근 방식은 다음과 같다.(1) 입력받은 좌표의 변두리 부분도 페인트를 칠할 수 있다. 가령파란색으로 칠한 부분을 봐라. 만약 입력 좌표 그대로 2차원 배열을 만든다면, 해당 변두리 부분은 배열을 벗어나게 되어, 페인트를 칠할 때 골치가 아파진다. (자칫 잘못하면 OutOfArrayIndex 에러가 나기 때문이다!!)따라서 우리는 해당 좌표도 배열 내에서 받을 수 있도록 2차원 배열을 테두리까지 넉넉하게 만들고, 여기에 입력받은 좌표값들을 집어넣는다.int [][] map = new int [row+2][col+2]그러면 이렇게 받을 수 있다. 파란색으..

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(); ..