![]()
문제강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의..
![]()
배열의 개념배열은 데이터를 저장하고 관리하는 방법 중 하나로 동일한 타입의 데이터를 연속적인 메모리 공간에 저장하는 방법을 사용합니다. 쉽게 이야기하여 배열은 같은 종류의 물건이 담긴 상자가 순서대로 나열되어있는 형태라고 생각할 수 있습니다.예를 들어, 과일가게 주인은 수박 여러 개 를 상자에 하나씩 담아 번호를 붙여 순서대로 나열해두었습니다.여기서 가게 주인은 상자에 번호를 매길때 첫 번째 상자를 기준으로 첫 번째 상자로 부터 떨어진 거리를 붙여 두었습니다 즉, 첫 번째 상자의 번호는 0, 두 번째 상자의 번호는 1 로 이 같은 방식을 사용하여 여러개의 상자를 나열하였습니다. 위 같은 번호 방식을 사용하면 두 번째 상자의 번호 '1'은 첫 번째 상자로 부터 1만큼 떨어진 위치에 존재한다는 것을 유추 할..
![]()
문제한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.이 편집기가 지원하는 명령어는 다음과 같다.초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되..
![]()
문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력예제와 같이 요세푸스 순열을 출력한다. 예제 입력내 제출import java.io.BufferedReader;i..
![]()
문제다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입력첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. 출력첫째 줄에 필요한 세트의 개수를 출력한다. 예제 입력내 제출import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import ja..
![]()
문제두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다.한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다.두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거..
![]()
문제세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오. 예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다. 입력첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. 출력첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 1부터 9까지의 숫자가 각각 몇 ..
![]()
문제정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 큐에 들어있는 정수의 개수를 출력한다.empty: 큐가 비어있으면 1, 아니면 0을 출력한다.front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.입력첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에..
![]()
문제한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.이 편집기가 지원하는 명령어는 다음과 같다.L커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)B커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로 인해..
![]()
문제스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.입력첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. ..
![]()
문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이..
![]()
문제문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.출력각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.예제 입력입력출력2 I am happy today We want to win the first prizeI ma yppah yadot eW tnaw ot niw eht tsrif ezirp내 제출import java.io.BufferedReader;im..
![]()
문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.입력첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다...
문제N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.예제 입력입력출력31 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1내 제출import java.util.Scanner;public class Main { static int[] arr; static boolean[] visited; static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); ..
![]()
📃 제출import java.util.Scanner;public class Main { static int[] arr = {1, 2, 3}; static int N; static int answer; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for (int i = 0; i = N) { if (sum == N) { answer++; } return; } for (int i : arr) { ..
![]()
📃 제출import java.util.Scanner;public class Main { static int answer = 0; static int N; static int S; static int[] nums; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); S = sc.nextInt(); nums = new int[N]; for (int i = 0; i ✏ 풀이핵심 아이디어:각 원소를 포함하거나 포함하지 않는 두 가지 선택을 가지면서, 모든 가능한 부분수열을 탐색합니다.재귀적으로 각 원소를..
![]()
📃 제출import java.util.Scanner;public class Main { static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); arr = new int[M]; dfs(N, M, 0, 0); } public static void dfs(int N, int M, int index, int depth) { if (depth == M) { for (int i : arr) { ..
![]()
📃 제출import java.util.Scanner;public class Main { public static boolean[] visited; public static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); visited = new boolean[N]; arr = new int[M]; dfs(N, M, 0); } public static void dfs(int N, int M, int depth) { ..
![]()
📃 제출import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for (int i = 0; i document = new LinkedList(); for (int j = 0; j priority = new LinkedList(); for (int j = 0; j ✏ 풀이문서와 중요도를 관리하는 큐를 선언한 후, 각 문서의 중요도..
![]()
📃 제출import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..
![]()
Lower Bound & Upper Bound 이진 탐색 알고리즘은 정렬된 배열에서 특정 값을 빠르게 찾는 데 사용된다. 이진 탐색의 개념을 확장하여, Lower Bound와 Upper Bound를 이용하면 정렬된 배열에서 특정 값의 위치를 보다 정밀하게 찾을 수 있다. Lower BoundLower Bound는 배열에서 주어진 값 이상인 첫 번째 위치를 찾는 알고리즘이다, 즉, 주어진 값이 처음으로 나타나는 인덱스를 반환하는 알고리즘이다. 동작 방식초기화:low를 0으로 초기화한다.high를 배열의 길이로 초기화한다.이진 탐색:low 반복 중 mid를 (low + high) / 2로 계산한다.배열의 중간 값 arr[mid]와 target을 비교한다.arr[mid] >= target: 배열의 mid 위치..
덱(Deque) 이란?덱(Deque)은 "Double-ended Queue"의 약자로, 양쪽 끝에서 삽입과 삭제가 가능한 큐이다.일반적으로 큐(Queue)는 한쪽 끝에서 데이터를 삽입하고 다른 쪽에서 데이터를 삭제하는 방면, 덱은 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 구조를 가지고 있다.이로 인해 덱은 스택과 큐의 특성을 모두 가져 다양한 응용이 가능하다. 덱의 장점덱은 양쪽 끝에서 요소를 추가하거나 제거할 수 있어, 큐와 스택의 기능을 모두 제공한다.덱의 삽입 및 삭제 연산은 양쪽 끝에서 모두 상수 시간(O(1))에 수행할 수 있다. 앞쪽과 뒤쪽 모두에서 데이터 처리 및 조작을 할 수 있어, 특정 알고리즘이나 데이터 구조를 구현하는 데 유용하다. 덱의 단점구현이 복잡할 수 있으며, 적절한 인덱스..
![]()
📃 제출import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new O..
![]()
📃 제출import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new O..
![]()
선택 정렬이란?선택 정렬이란 정렬 알고리즘 중 하나로, 배열을 정렬하는 간단한 알고리즘이다.선택 정렬 알고리즘은 가장 작은 원소를 찾아서 배열의 맨 앞에 놓고, 다음으로 작은 원소를 찾아서 두 번째 위치에 놓는 방식으로 정렬을 진행하며 이 과정을 배열 끝까지 반복하여 정렬된 배열을 생성한다.선택 정렬의 동작 방식동작 과정 : 기준 원소 선택: 현재 위치의 원소를 기준으로 삼는다.가장 작은 원소 찾기: 기준 원소 이후의 배열에서 가장 작은 원소를 찾는다.교환: 찾은 가장 작은 원소를 현재 위치에 배치합니다.반복: 배열의 모든 위치에 대해 위 과정을 반복합니다. 동작 과정 설명: 1. 현재 위치의 원소를 기준으로 삼는다. 2. 기준 원소 이후의 배열에서 가장 작은 원소를 찾는다. 3. 찾은 가장 작은 원소를..
![]()
📃 제출import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new O..
![]()
서론카운팅 정렬(Counting Sort)은 정수 기반의 데이터를 정렬하기 위해 설계된 효율적인 정렬 알고리즘이다.이 알고리즘은 각 원소의 등장 횟수를 계산하여 정렬을 수행하며, 특정 조건에서 매우 빠르게 동작할 수 있다.이 글에서 카운팅 정렬의 개념과 동작 방식, 장점 및 단점을 정리하고자 한다.카운팅 정렬이란카운팅 정렬은 입력 데이터의 범위가 상대적으로 좁을 때 효과적인 정렬 알고리즘이다. 이 알고리즘은 각 원소가 등장하는 횟수를 기록하고, 이 빈도 정보를 바탕으로 정렬된 결과를 빠르게 생성한다. 카운팅 정렬의 주요 아이디어는 데이터를 직접 정렬하는 대신, 각 값의 출현 빈도를 계산하여 원래 배열의 정렬을 수행하는 것이다.카운팅 정렬 동작 과정 카운팅 정렬은 다음과 같은 단계로 이루어진다.최댓값 찾기..
![]()
📃 제출import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.stream.Collectors;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..
![]()
📃 제출 코드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.stream.Collectors;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere..
![]()
서론이진 탐색(Binary Search) 은 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘이다.이 알고리즘은 탐색 범위를 절반으로 줄여 나가면서 목표 값을 찾기 때문에 매우 빠르고 효율적으로 값을 찾을 수 있다.이 글에서는 이진 탐색의 개념과 구현 방법, 그리고 시간 복잡도를 다뤄보려고 한다.이진 탐색이란?이진 탐색은 정렬된 배열에서 원하는 값을 찾기 위해 사용되는 알고리즘이다.탐색 범위를 절반으로 줄여나가며 목표 값을 찾기 때문에, 탐색 속도가 매우 빠르다.하지만 이진 탐색을 사용하려면 배열이 정렬되어 있어야 한다는 점이 중요하다. 이진 탐색 동작 과정 이진 탐색은 다음과 같은 단계로 진행된다:중간값 계산:배열의 중간값을 계산하여 현재 탐색 범위의 중간 인덱스를 구한다.목표 값 비교:중간값..
