Java

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 사용한 알고리즘 : 정렬 풀이전략 문제 자체는 어렵지 않은데 JAVA에서 최적화된 정렬방법 및 입출력을 사용하지 않으면 시간초과가 나오는 문제였다. 문자열을 출력할 때, 한 줄 한 줄 출력을 하기보다 StringBuilder를 사용하는 것이 더 효율적이었다. StringBuilder는 출력해야할 문자열들을 하나로 묶어줬다가 한번에 출력시키는 역할 수행한다. 또한 정렬에서 Array..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 사용한 알고리즘 : 세그먼트 트리 풀이 전략 세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조로 위와같은 구조를 가진다. 최댓값을 저장하는 트리 초기 설정 코드 static int max_init(int arr[], int node, int nodeLeft, int nodeRight){ if(nodeLeft==nod..

https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹, 백트래킹 ※ 풀이 전략 1. 학생 개인이 풀 수 있는 문제를 2진수로 나타낸다. 풀 수 있는 문제는 1, 풀 수 없는 문제는 0으로 표기한다. ex) 예로 1번 학생이 총 5문제 중 2, 3, 5 번을 풀 수 있다고 한다면 10110 (2) = 22 이다.(오른쪽부터 1번 문제이고, 맨 왼쪽 비트가 5번 문제를 나타낸다.) 2. 백트래킹을 기법을 이용..

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 입력한 숫자를 2진수로 생각하고, 해당 2진수 안에 있는 1의 개수가 K개 이하가 될 때까지 1씩 더한다. (비트 1의 개수가 곧 물병의 개수를 의미하기 때문이다.) ex ) 000000001 = 1L 물병 1개 => 총 물병의 개수 : 1 000000010 = 2L 물병 1개 => 총 물병의 개수 : 1 000001010 = 8L 물병 1개, 2L 물병 1..

https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 기본값을 2^20으로 두고 비트마스크를 통해 승객을 태우거나 하차시킨다. default=Math.pow(2,20) 최초 기차의 상태는 00000 00000 00000 00000 이다. 여기서 비트 마스킹에 사용할 값인 default를 1 00000 00000 00000 00000 로 두고 아래 명령에 따라 변화하는 기차 상태값을 살펴보자. ..

https://www.acmicpc.net/problem/17419 17419번: 비트가 넘쳐흘러 🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶 DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다! N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException{ BufferedRe..