분류 전체보기

[백준] 1253번 '좋은 수' 구하기

문제설명 더보기 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 문제풀이 시간복잡도 N의 최대 개수가 최대 2000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간복잡도는 N^2보다 작아야 한다. 따라서 알고리즘의 시간 복잡도는 최소 O(nlongn)이어야 한다. 따라서 투 포인터 알고리즘을 사용하면..

[백준] 1940번 주몽의 명령

문제설명 더보기 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 재료의 개수 N(1 ≤..

[백준] 2018번 연속된 자연수의 합 구하기

문제설명 더보기 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 입력 첫 줄에 정수 N이 주어진다. 출력 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오 문제풀이 package doit_java; import java.io.Buffered..

[알고리즘] Two Pointers 알고리즘이란?

투포인터 알고리즘이란? 투포인터 알고리즘 또는 슬라이딩 윈도우라고 부른다. 1차원 배열이 있고, 배열에서 각자 다른 원소를 카리키고 있는 2개의 포인터를 조작하면서 원하는 값을 얻는 방법이다. 설명 1. 포인터 2개를 준비 , start_index , end_index 2. 항상 start_index

[알고리즘]Prefix sum 알고리즘이란?

누적합(Prefix sum)란? 나열된 수의 누적된 합을 말한다. 배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해준다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있다. 설명 1차원 배열 arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. 활용법 arr의 i항부터 j항 까지 합을 S(i,j)라고 하자. 이때 S(ij) = sum[j] - sum[i-1]이다. S(2,4) = S[4]=S[1]이다. 쉽게 생각하면 참고문제) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 ..

[백준] 11660번 구간 합 구하기-2

문제설명 더보기 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표..

[백준] 11659번 구간 합 구하기

문제설명 더보기 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 문제풀이 public class doit_3_구간합구하기 { public static void main(String[] args) throws IOException { // suNO(수의 개수) QuizNo ..

[JAVA] BufferedReader와 StringTokenizer 사용법

BufferedReader란? JAVA에서 입력방식은 Scanner와 BufferedReader가 있다. Scanner를 통해 입력을 받을경우 Space Enter를 모두 경계로 인식하기에 입력받은 데이터를 가공하기 매우 편리하다. 하지만 BufferedReader는 Enter만 경계로 인식하고 받은 데이터는 String으로 입력을 받기 때문에 가공을 해야하는 작업이 필요하다. 하지만 작업속도 차이가 많이 나기 때문에 BufferedReader를 이용하여 입력 받는 것이 훨씬 효율적이다. BufferedReader사용법 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..