전체 글

백준 1517번 자바 ☆

문제 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 1. 버블소트를 가장한 머지소트 문제 문제 제목이 버블소트라고 버블소트로 풀었다 당연스럽게 시간초과로 틀렸다. 머지 소트로 풀어야 통과가 된다. https://ahlight.tistory.com/79 백준 2751번 자바 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000..

백준 2751번 자바

문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 병합정렬이란? - 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 - 평균 시간 복잡도는 O(nlogn)이다. - 예시 아래와 같이 정렬되지 않은 배열 A가 있다. 6 4 3 1 5 2 배열을 최소단위로 나눠준다.(값의 색은 구분단위) 6 4 3 1 5 2 인접 단위끼리 병합을 진행하며 정렬 4 6 1 3 2 5 4 6 1 2 3 5 1 2 ..

백준 11004번 자바 ☆

문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 처음엔 Arrays.sort를 이용해 쉽게 풀었다. Arrays.sort 의 정렬 방식이 dual pivot quick sort를 사용하기 때문에 가능하다고 판단했고 정답을 맞추긴 했다. 하지만 이번 문제에선 퀵정렬을 사용해 해결하는것이 핵심이었다. 2. 퀵정렬 개념자체는 어렵지 않다. pivot을 설정하고 pivot기준 이하 그룹, 이상 그룹으로 나누어 재귀로 배열을 정렬하면 된다. 단순 구현이라면 크게 어렵지 않았지만 해당 문제를 충족..

백준 11399번 자바

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 삽입정렬을 이용해 문제를 해결했다. 삽입정렬이란 예를들어 아래 파란식 글씨 부분들이 정렬된 부분이고, 빨간색 글씨부분이 현재 인덱스일때 현재 인덱스의 값을 정렬된부분에 삽입을 하는 것이다. 1 2 3 4 5 13 15 12 17 16 12는 13보다 작은 수이기때문에 가장 앞에 삽입되고 나머지 값들은 한칸씩 뒤로 이동이 된다. 3 1 2 4 5 12 13 15 17 16 값이 한칸씩 뒤로 밀려 저장되는 것만 주의하면..

백준 1427번 자바

문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 배열의 인덱스를 값으로 활용하는 방식을 잘 사용하지 못해 해당 부분에 주의를 기울여 보고자 한다. 2. 내가 작성한 코드는 정답이지만 최대값일 때 인덱스를 idx에 따로 저장을 해서 문제 해결을 했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main1427 { public static void main(String[] arg..