BOJ

큐(queue)란? 앞서 배운 스택은 FILO 구조였다. 가장 먼저 들어간 것이 가장 나중에 나온다는 의미이다. 큐(queue)는 비슷하지만 반대되는 개념인 FIFO(First In First Out) 구조를 지닌다. 가장 먼저 들어간 것이 가장 먼저 나온다. 또한 스택은 한쪽에서 삽입과 삭제가 모두 일어나지만, 큐는 한쪽은 삽입 연산만 일어나고 다른 한쪽은 삭제 연산만이 이루어진다. 놀이공원에서 놀이기구를 타기 위해 줄을 서는 것이나, 도로의 터널에서 자동차가 지나가는 것을 생각해보면 이해하기 쉬울 것이다. 큐의 구현 백준에서 다음 문제를 통해 직접 큐를 구현해보자. https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘의 대표적인 유형이라고 한다. 이처럼 시간표를 최대한 많이 배정하거나 선택하는 문제를 활동 선택 문제(Activity Selection problem)라고 한다. 이런 문제들의 특징은 한 사람이 하나의 활동에 대해서만 작업할 수 있다는점이다. 따라서 서로의 활동은 독립적이다. 활동 선택 문제의 특징들을 기억하며 문제를 해결해보자. [코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 이번에는 서브태스크 문제이다. 문제가 상당히 길지만 읽어보면 규칙은 간단한 문제이다. 먼저, 아직은 Scanner가 익숙한지라 먼저 Scanner로 입력 받고 알고리즘을 짠 후 100점을 받지 못한다면 BufferedReader로 바꿔야지 했다. [코드] 1. Scanner 사용 import java.util.Scanner; public class N_13305 { public static void main(String[] args) { Scanne..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 동적 계획법으로 푸는 문제이다. 좀 더 까다로운 2차원 배열의 문제이다. 왼쪽이 arr 배열, 오른쪽이 dp 배열이다. 위처럼 n층의 입력된 숫자를 2차원 배열로 만들고, 더 누적합이 높은 경우의 수를 차례로 찾아가며 dp 배열을 채워주면 된다. [풀이] import java.util.Scanner; public class N_1932 { static int n; static int arr[][]; static int dp[][]; public static void m..

https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 동적 계획법을 활용하는 문제이다. 다른 동적 계획법 문제와 다르게 다소 까다로운 부분이 있었다. 양 옆으로 같은 색깔의 집이 오면 안된다는 규칙과, 집을 칠하는 비용의 최솟값을 구해야 했기 때문이다. 빨강, 초록, 파랑으로 시작하는 모든 경우의 수를 찾아나가야 했다. [풀이] import java.util.Scanner; public class N_1149 { static int[][] cost; static int[][] dp; public static void main(Str..

https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net [코드] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String numStr = sc.next(); int res = 0; for (int i = 0; i < n; i++) { res += numStr.charAt(i) - '0'; } System.out.print..

[코드] // 셀프 넘버 public class Main { public static void main(String[] args) { int n = 10000; boolean[] idx = new boolean[n + 1]; // index 10000 까지의 배열 생성 for (int i = 0; i < n + 1; i++) { if (d(i) < n + 1) { idx[d(i)] = true; // 셀프 넘버가 아닌 것 } } for (int i = 0; i < n + 1; i++) { if (!idx[i]) { System.out.println(i); } } } public static int d(int n) { int res = n; while (n != 0) { res += n % 10; n = ..

https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net [코드] import java.util.*; // 숫자의 개수 public class Main {` public static void main(String[] args) { Scanner sc = new Scanner(System.in); int number = (sc.nextInt() * sc.nextInt() * sc.nextInt()); String str = Integer.toString(number); // str = '17037300' sc..