순간을 기록으로

문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 예시 분석 좋은 수가 되려면 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있어야 한다. 예를들어 N이 3이고 1 2 3을 입력받는다고 가정하자. 3은 다른 두 수 1과2의 합으로 나타할 수 있으므로 좋은 수라고 할 수 있다. 로직을 생각한다면 갯수 N을..

문제 수 N개가 주어졌을 때 , i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하세요. 입력 첫째 줄에 수의 개수 N과 구해야 하는 횟수 N이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지의 합을 출력한다. 분석 데이터 갯수는 10만 개이고, 구간 합을 구해야 하는 횟수도 최대 10만 번이다. 즉 최악의 경우 시간 복잡도는 O(n^2). 연산이 10만^2번, 100억이 되어 100초가 걸린다. 제한시간이 0.5초이므로 단순히 이중 for문으로 문제를 풀 수 없다. 이 문제를 풀기 위해서는 구간합 알고리즘을 이용해야 ..

안녕하세요 luminous13입니다. 이번에는 백준 수정렬하기1 2750번 문제를 풀어보도록 하겠습니다. 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 데이터를 오름차순으로 정렬하는 문제입니다. 사실 정렬을 Arrays.sort()를 이용하여 쉽게 정렬할 수 있지만 이번에는 직접 정렬을 구현하면서 문제를 풀어보도록 하겠습니다. 여러 정렬 알고리즘 중 하나를 선택해야 합니다. 데이터 크기를 보니 최대 1,000이 올 수 있습니다. 데이터 크기가 크..

분석 * 이번 문제는 수 나열에서 부분 합을 여러번 구하는 문제다. * 배열의 구간 합을 구해야 될때에는 합 배열을 이용하면 시간복잡도를 O(n)에서 On(1)로 줄일 수 있다. * 합 배열 공식:S[i] = S[i-1] + arr[i] * [i,j] 구간 합 공식: S[j] - S[i-1] * 배열의 사이즈를 1 추가하여 인덱스가 1이 첫 번째 원소로 설정해야 합배열 첫 번째 원소도 규칙있게 구할 수 있다. * * 이번 문제에서 만약 합 배열을 이용하지 않고 이중 for문을 사용하면 수의 갯수*횟수이 연산횟수가 된다. * 100,000*100,000 = 10,000,000,000 이다. 즉 100억번 연산을 하게되고 시간은 100초가 소요될것이다. * 따라서 합배열을 사용해야하는 문제다. 수도코드 * ..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 후기 2차원 배열까지 접근하는 건 알겠는데 도저히 정렬을 어떤 식으로 해야 되는지 감이 안 왔다. Arrays.sort() 메소드의 경우 기본적으로 인자로 1차원 배열만 인자로 받기 때문이다. 다행히 Compartor를 이용해서 해결할 수 있었다. import java.io.*; import java.util.Arrays; import java..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 목표 평균 값을 구할 수 있다. 중앙값을 구할 수 있다. 최빈값을 구할 수 있다. 최댓값과 최솟값을 구할 수 있다. 푸는 순서: 1.문제 읽기 --> 2.수도코드 작성하기 --> 3.코드 작성하기 --> 4.테스트케이스 만들기. 맨 처음에 각 구하는 값을 함수 별로 담에서 구하려 했다. 하지만 생각보다 코드가 중복되는 걸 확인하고 함수로 분리하는 게 오히려 좋지 않을 수 있다는 생각이 들어 리팩토링 했다. 수도..