문제 링크 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 - 정렬 후 투 포인터 로직 수행 - 시간 복잡도 : O(NlogN) - 배열 순차적으로 순회하여 기준 값과 나머지 영역에서 투 포인터로 두 값을 정하고 다 더했을 때 0에 가까운 최대 값을 구하면 됨 참고 [BOJ 2470] 두용액 (Java, 투 포인터) [BOJ 1253] 좋다 (Java, 투 포인터) 제출 코드 - 입력 배열 A 의 데이터 타입을 lon..

문제 링크 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 - 알파벳(26자) 카운팅 배열을 활용하여 투포인터 문제 풀이 - 시간복잡도는 O(N) *알파벳 인덱스 구하기 int index = TEXT.char(i) - 'a'; 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, CNT; static String TEXT; static int[] ALPHABET ..

문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 - 두 용액 문제 풀이 방법을 응용하여 풀이 - 시간 복잡도 O(NlogN) - 순차 조회하면서 해당 값을 다른 두 수의 합으로 만들 수 있는지 확인 (이때 탐색과정에서 자기자신의 경우 제외, targetIdx) 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] A; static void input..

문제 링크 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 - 투 포인트 기법과 카운팅 배열을 활용하여 1 ~ N 까지의 모든 경우의 수 합을 더하면 됨 - 시간복잡도 O(N) 이때 최대값의 경우 1 2 3 ... 100,000 1 2 3 ... 100,000 1 ~ 100,000까지의 합을 나타내기 때문에 100000(99999) / 2 = 대략 50억이기 때문에 long으로 풀이 해야 함 L = 1인 경우 100,000 L = 2인 경우 99..

문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 - 투 포인터 문제 - 시간 복잡도 O(N) - 정답의 최대 길이는 100,000 , 구하려는 S의 최대는 10^9 이므로 Integer로 풀이 가능 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, S; static int[] NUMBERS; static void input()..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 - 투 포인터로 문제 풀이 (이진탐색으로 풀이 가능하나 개념적으로 조금 어려움) - 두 용액을 더 했을 때 0에 가까운 두 수를 구하는 문제 - 양 끝에서 투 포인터를 시작해서 서로를 향해 이동 - sum 의 값이 양수인 경우 R을 감소, 음수인 경우 L을 증가 0 1 2 3 4 -99 -2 -1 4 98 -99, 98 = -1 이므로 L증가 -2..

문제 링크 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - long 타입 변수를 사용해야 하는 경우 있음 뒤집은 문제 용량(ml) 을 정했을 때, 친구(K)명에 막걸리를 골고루 분배 가능한가 ? 이때 용량(ml)는 최대인가? 부등호 헷갈리는 경우 주전자(N) 1개 이고 그 안에 21억ml가 담겨 있고, 친구(K) 100만명 있을 때 - 1000ml 로 나눌 경우 주전자에 1..

문제 링크 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 굴다리 길이 N (1 ≤ N ≤ 100,000) 일 때 0번 위치에 가로등 한 개 세울 경우 H는 100,000(최대)이 되야 모두 비추는게 가능하므로 Integer로 연산가능 뒤집은 문제 가로등 높이 H일 때 굴다리 길이 N을 모두 비추는게 가능한가? 가능한 경우 가로등 높이 H는 최소 높이인가? 예제 입력 1 5 ..

문제 링크 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 은행 인출(mid) 하고 cnt = 1 한 초기 상태에서 일별 사용금액을 차감하면서 부족할 경우 추가 은행 인출(cnt += 1) - (100, 400), (300,100), (500), (101), (400) 형태가 최대값 만약 N일이 10만이고, 각 금액이 1만이면 최대 10^9이 되야 1번(M)번에 처리가 가능 =..

문제 링크 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 - 이진탐색 (매개변수 탐색) 으로 풀이하면 되는 문제 - 시간 복잡도는 O(NlogN) 범위 지정시 (L, R) L 의 경우 100,000개의 강의(N)를 100,000 개의 블루레이(M)에 담는다 할 때 (각 강의 길이 또한 최대 10,000분) 최소 10,000분이 되야함. 10,000분 이하는 담을 수가 없기 때문에, 최소 10,000분이 기준이 됨 L 은 고로 주어진 배열에서 가..

문제 링크https://www.acmicpc.net/problem/1300 1300번: K번째 수세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 Bwww.acmicpc.net2차원 배열을 1차원으로 이렇게 구할 수도 있다니 또 하나 배운다 :) 풀이 - N (최대 10만), K (10만 ~ 10억)- N * N 2차원 배열을, 1차원 배열로 변환 후 정렬했을 때 K번째 있는 임의 수를 구하는 문제 - N이 최대 10만이기 때문에 1차원 배열로 변환시 10^10 = 100억이 되어서 메모리 초과, 시간 초과 발생 가능 아래와 같은 연산..

문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이진탐색 (매개변수 탐색) 풀이하면 되는 문제 문제 지문 K개 랜선이 있을때 필요한 랜선 N개를 만들기 위한 최대 랜선 길이 H를 구하시오. 뒤집은 지문 (매개변수 탐색*) 임의 길이 H로 랜선을 K개를 자를때, 필요한 랜선 N개를 만들 수 있는가? 이때 최대 랜선 길이 H는 얼마인가? 시간 복잡도 O(NlogN) 최대값 랜선의 길이 최대값이 2^31 ..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 매개변수 (paramatrix search) 탐색 문제 (그리디 포함) 문제 지문 C 개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리(Dmax) 를 구하시오. 뒤집은 지문 두 공유기 사이의 거리 (D)를 라 할때, C개의 공유기를 설치 가능한가(yes/no)? 이때 설치 가능한 최대 거리(Dm..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 반복문을 통해 left = 1 ~ N 까지 조회할 때 - arr[left + 1 ... N] 사이에 값들 중 -arr[left] 이상이면서 가장 왼쪽에 있는 값을 찾아야 함 - N 이 최대 10만일때 O(N^2) = 10^10 시간초과 발생가능 - 이진탐색으로 풀이시 O(NlogN) 시간 복잡도 가짐 투 포인터로 풀 경우 좀 더 쉽게 풀이 가능 주..

문제 링크 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 풀이 - 첫째줄에 점 N개가 주어지고, 다음 라인 부터 N개만큼 "위치 색깔" 형태로 입력이 주어짐 - 같은 색깔에 p와 q점에 대해 직선 화살표로 연결하려 할 때, 가장 가까운 거리의 점이여야 함 (만약 가까운 점이 두 개 이상이면 둘중 아무거나 선택) - 모든 점에 대해 같은 색깔을 가진 다른 점이 항상 존재 ( 2

Primitive type - 총 8가지의 기본형 타입을 자바에서 제공함 - 기본값을 제공하기 때문에 Null이 존재하지 않음. 만약 기본형 타입에 Null을 넣고 싶은 경우 Wrapper class를 활용해야함 - 실제 값을 저장하는데, 이때 Stack(스택) 메모리에 저장됨 타입 할당 메모리 크기 데이터 표현 범위 논리형 boolean 1byte false, true 정수형 byte 8bit (1byte) -128 ~ 127 short 16bit (2byte) -32,768 ~ 32,767 int 32bit (4byte) -2,147,483,648 ~ 2,147,483,647 long 64bit (8byte) -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 - 길이가 N인 계단 수를 구하는 문제 (45656 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라 부름) - '이때 0으로 시작하는 수는 계단수가 아니다' 는 조건이 있음 점화식 - 2차원 DP배열에서 i, j 에 의미 부여 후 점화식 세워 문제 풀이하는 방법을 따라함 - 직접 했을 때는 식을 못 찾고, 설명을 찾아보고 다시 그렸을 때야 이해가 되었음 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1] - 이때 DP[i][j] 에서 i는 자릿수(길이), j는 끝 숫자..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 - bottom-up 방식으로 품 // SUCCESS const input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); const n = Number(input[0]); const dp = new Array(n+1).fill(0); for(let i = 2; i