✔ 동전 1[백준 2293]코드 구현하기/* * 문제 분석하기 * : 주어진 금액을 만들기 위해 동전들을 조합해 만드는 방법을 모두 세도록 함 *//* * 손으로 풀어보기 * 1. 1원부터 K원까지를 만들 때, 하나의 동전을 사용할 수 있는 경우와 여러 동전을 사용해야 하는 경우에 따른 경우의 수를 세도록 함 * 2. 금액 K를 만드는 모든 방법의 수를 출력 *//* * 2293) 동전_1 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N, K; static int[] coins; // coins(동전들을 담은 배열) sta..
✔ 최소 회의실 개수[백준 19598]코드 구현하기/* * 문제 분석하기 * : 우선순위 큐를 이용해 시작 시간이 빠른 회의부터 시작하며 * 이번 회의가 시작하기 전에 이전 회의가 끝났다면 이전 회의를 삭제 * 그렇지 않다면 이번 회의를 우선순위 큐에 넣도록 하여 회의실의 개수를 늘려줌 * 모든 회의를 진행한 후 우선순위 큐의 개수를 출력하도록 함 *//* * 손으로 풀어보기 * 1. 우선순위 큐를 이용해 시작 시간이 빠른 회의부터 저장 * 2. 이번 회의가 시작하기 전에 이전 회의가 끝났다면 이전 회의를 삭제 * 3. 그렇지 않다면 이번 회의를 우선순위 큐에 넣도록 하여 회의실의 개수를 늘려줌 * 4. 모든 회의를 진행한 후 우선순위 큐의 개수를 출력 *//* * 19598) 최소_회의..
✔ 나무 위의 빗물[백준 17073]코드 구현하기/* * 문제 분석하기 * : 더 이상 물이 움직이지 않을 때는 리프 노드에 모두 물이 쌓이게 되므로 * 리프 정점에 고인 물의 양을 리프 노드의 개수로 나누어주면 됨 *//* * 손으로 풀어보기 * 1. 트리를 탐색하며 리프 노드의 개수를 찾도록 함 * 2. 리프 정점에 고인 물의 양을 리프 노드의 개수로 나누어주어 평균으로 출력 *//* * 17073) 나무_위의_빗물 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N, W; static ArrayList[] tree; // ..
✔ 중앙값 구하기[백준 2696]코드 구현하기/* * 문제 분석하기 * : 중앙값과 중앙값보다 큰 값을 저장할 우선순위 큐와 작은 값을 저장할 우선순위 큐를 생성한 후 * 값을 저장하고 교환하며 중앙값을 찾도록 함 *//* * 손으로 풀어보기 * 1. 중앙값과 중앙값보다 큰 값을 저장할 우선순위 큐와 작은 값을 저장할 우선순위 큐를 생성 * 2. 두 우선순위 큐의 크기가 같다면 큰 값을 저장하는 우선순위 큐에 걊을 저장 * 3. 두 우선순위 큐의 크기가 다르다면 작은 값을 저장하는 우선순위 큐에 값을 저장 * 4. 큰 값을 저장하는 우선순위 큐의 최소값과 작은 값을 저장하는 우선순위 큐의 최대값을 비교 * 5. 작은 값을 저장하는 우선순위 큐의 최대값이 더 클 경우, 이 값으로 중앙값이 갱신되므로 ..
✔ 데이터 체커[백준 22942]코드 구현하기/* * 문제 분석하기 * : 모든 원의 중심 좌표는 x축 위에 존재하므로 중심 좌표 기준으로 반지름의 길이를 활용해 맨 앞의 점과 맨 뒤의 점을 인덱스와 함께 저장 * 이후 좌표 순으로 정렬하여 스택에 넣으며 같은 원의 점 끼리 모두 짝이 맞아 스택이 비었다면 YES * 아니라면 원 사이에 다른 점이 있는 것이므로 NO를 출력 *//* * 손으로 풀어보기 * 1. 중심 좌표 기준으로 반지름의 길이를 활용해 맨 앞의 점과 맨 뒤의 점을 인덱스와 함께 저장 * 2. 좌표 순으로 정렬하여 스택에 넣으며 같은 원의 점 끼리 모두 짝이 맞는지 확인 * 3. 모두 짝이 맞아 스택이 비었다면 YES, 아니라면 원 사이에 다른 점이 있는 것이므로 NO를 출력 */..
✔ 사회망 서비스(SNS)[백준 2533]코드 구현하기/* * 문제 분석하기 * : 자식 노드부터 탐색하며 자신이 얼리 어답터가 아닐 경우와 얼리 어답터일 경우를 나누어 구하며 * 필요한 최소 얼리 어답터의 수를 구하도록 함 *//* * 손으로 풀어보기 * 1. 자식 노드부터 탐색하며 자신이 얼리 어답터가 아닐 경우와 얼리 어답터일 경우 나누어 구함 * 2. 자신이 얼리 어답터가 아닐 경우(0), 자식 노드가 모두 얼리 어답터여야 함 * 자신이 얼리 어답터일 경우(1), 자식 노드들은 얼리 어답터일 수도 있고, 아닐 수도 있음 * 3. 루트 노드까지 이를 구한 후, 필요한 최소 얼리 어답터의 수를 출력하도록 함 *//* * 2533) 사회망_서비스(SNS) */public class Ma..
✔ 전화번호 목록[백준 5052]코드 구현하기/* * 문제 분석하기 * : 트라이 자료구조를 사용해 모든 전화번호 목록을 저장한 후 접두사가 일치하는지 확인 * 또는 문자열을 정렬한 후 완전탐색으로 모든 문자열을 비교 *//* * 손으로 풀어보기 * 1. 트라이 자료구조에 모든 전화번호 목록 저장 * 2. 저장해둔 트라이 자료구조를 통해 각 전화번호를 입력하여 해당 전화번호가 다른 전화번호의 접두사로 포함되는지 확인 * 3. 만약 현재 입력된 전화번호의 끝 부분이 다른 전화번호에 포함되는 부분이라면 일관성이 있지 않으므로 false를 출력 * 4. 모두 일관성 있다면 true를 출력 *//* * 5052) 전화번호_목록 */public class Main { static BufferedR..
✔ 네트워크 연결[백준 1922]코드 구현하기/* * 문제 분석하기 * : 모든 컴퓨터를 연결할 수 있는 최소 신장 트리를 찾도록 함 *//* * 손으로 풀어보기 * 1. 크루스칼 알고리즘을 수행해 사용하지 않은 엣지 중 가중치가 가장 작은 간선을 선택 * 2. 선택한 간선을 연결했을 때 사이클이 발생하는지 판단 * 3. 간선을 더한 횟수가 정점의 개수 - 1이 될 때까지 이를 반복 * 4. 모든 컴퓨터를 연결하는데 필요한 최소 비용 출력 *//* * 1922) 네트워크_연결 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N, M; ..
