순간을 기록으로

안녕하세요 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초가 소요될것이다. * 따라서 합배열을 사용해야하는 문제다. 수도코드 * ..