합병 정렬 개념 리스트를 두 개의 균등한 크기로 분할하고 분할된 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하기를 반복하면서 전체를 정렬한다. 분할 정복 기법 알고리즘 중 하나이다. 분할 정복 기법 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각 문제를 해결 후, 결과를 모아서 원래의 문제를 해결하는 전략 구체적인 알고리즘 합병 정렬은 다음 3가지 단계를 반복하며 정렬을 한다. 분할(Divide) : 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 충분히 작아질 때까지 분할을 반복한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 통합한다. 부분 리스트의 크기가 1개가..

알고리즘 퀵 정렬은 기준값(pivot)을 선정해 해당 값도가 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 평균적인 시간 복잡도는 O(nlogn)으로 다른 O(nlogn)의 알고리즘 중 가장 빠르다고 평가 된다. 구체적인 내용 기준점을 정하고 기준점을 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 이동 시키며 정렬을 진행 한다. 이때 기준점이 되는 레코드는 한 번 정렬이 완료되면 더 이상 자리가 바뀌지 않는다. partition 함수를 통해 피봇을 기준으로 왼쪽, 오른쪽을 나누게 된다. 최종적으로 피봇의 위치는 low가 higt보다 커지는 순간으로 결정된다. 이렇게 피봇을 기준으로 한 번 정렬된 리스트는 다시 왼쪽, 오르쪽 리스트로 쪼개져 partition 함수를 호출하며 리스..

알고리즘 손 안의 카드 정렬을 하는 것과 유사하다. 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입! 왼쪽 리스트에 정렬이 완료된 요소를 1개, 2개 점점 개수를 늘려가면서 정렬이 완료된다. 구체적인 알고리즘 1. 인덱스 1부터 시작한다. 2. 현재 삽입될 요소인 i번째 요소를 key 변수에 복사 3. i-1번째 부터 역순으로 조사 4. j가 0보다 작아지거나 key값보다 정렬된 배열에 있는 값이 크면 5. j번째는 j+1번째로 이동한다. 6. j를 하나 감소한다. 7. j번째 정수가 key보다 작으므로 j+1번째가 key값이 들어갈 위치이다. 코드 // 정렬 - 삽입 정렬 int i,j; for(i= 1; i=0&&num..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 접근방법 어떻게 하면 최솟값을 구할 수 있을까 생각을 했을 때, 누적시켜 더하는 특징에서 앞에 나오는 값들이 작을 때 최소가 될 것이다 생각을 했다. 그래서 오름차순 정렬을 이용하기로 하였다. 풀이 입력 입력의 수가 최대 1001개 이므로 비교적 구현이 쉬운 스캐너로 구현하였다. // 입력 받기 Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int [] num =..

문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근법 N은 최대 10자리 숫자로 매우 큰 메모리 공간을 차지함. 하지만 이 문제는 자릿수의 숫자들을 뽑아 정렬하는 것이므로 String 객체로 입력을 받아 쪼개 Int형 배열로 만드는 것이 효율적이라 생각이 들었다. 그 후 최대 10개의 숫자를 정렬하는 것은 아무 정렬법이나 쓰면 된다. 풀이 코드 public class Main { public static void main(String[] args) throws IOException { // 문자열로 입력 받기 Scanner..

알고리즘 개념 인접한 2개의 레코드를 비교하며 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환 1회전이 돌때 마다 정렬이 완료된 레코드가 가장 오른쪽에 1개씩 추가됨 코드 - Java // buble sort for(int i = N-1; i >=0 ; i--) { int chage = 0; for(int j=0; j arr[j+1]) { chage++; int tem = arr[j]; arr[j] = arr[j+1]; arr[j+1]= tem; } } if(chage == 0) break; } 시간 복잡도 분석 비교 횟수 (n-1) + (n-2) .. 2 + 1 = (n * (n+1)) / 2 시간 복잡도: O(n^2) 최선, 평균, 최악 모두 같다. 이동 횟수 최악의 ..

선택 정렬 개념 제자리 정렬 (in-place sorting)이다. 입력 배열 외에는 추가 메모리를 요구하지 않는 정렬이다. 정렬된 해당 요소가 넣어질 위치가 정해져 있다. 자료 이동 횟수가 미리 결정된다. → n-2번 구체적인 설명 선택 정렬이란 첫 번째 위치부터 차례대로 정렬이 안된 요소 중 가장 작은 것(큰 것)을 선택하여 위치를 교환하여 점점 정렬을 완료해나가는 기법이다. 첫번째 루프일 때 첫번 째 요소를 두번 째 요소부터 마지막 요소까지 비교하여 가장 작은 값을 찾으면 해당 요소와 교환한다. 두번 째 루프일 때 두번 째 자료를 세번 째 요소 부터 마지막 요소까지 비교하여 가장 작은 요소를 찾으면 해당 요소와 교환한다. 이렇게 n-1 요소까지 반복한다. 시간 복잡도 비교 횟수 (n-1) + (n-..

https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 버블 정렬 알고리즘을 빠삭히 알고 있어야 풀 수 있는 문제였다. 나는 못 풀었다. 핵심은 정렬이 완료된 시점을 찾아 내는 것! 우선 나의 알고리즘 풀이 생각은 다음과 같았다. 버블 정렬은 한 번 루프가 돌면 마지막 리스트 자리에는 정렬이 완료된 요소가 1개씩 추가된다. 이를 이용하여 정렬 전과 정렬 후를 비교해 정렬이 되지 않은 요소의 개수를 찾아내면 되지 않을까! 생..

쓰던 것이 있었으나 날아간 관계로... 중요한 것만 다시 쓴다.. 문제 발생 이번에 발생된 문제는 기본 사진에 All-in JPEG 사진이나 인터넷에서 다운 받은 사진을 넣으면 아예 이미지가 손상되어 보이지 않는 문제가 발생했다. 이미지 손상은 이때까지의 경험으로 정말 1~2 바이트의 오차만 있어도 깨지는 것을 봐왔기 때문에 우선 내 코드의 문제인지를 확인 하기 위해 어디가 잘못 된것인지를 다 뜯어 봐야 했다.. 내 코드 내가 봐도 이해하기 어려워서 계속 뜯어 고치고 고치고를 반복 했다. 덕분에 한결 깨끗해졌다! ㅎ 사진 데이터 분석 아무튼 내 코드를 다 뜯어 본 결론은 코드를 잘못 짠 것은 없었다. 이제 이게 구조상의 문제인지를 확인해야 했다! 손수 마커들의 종류와 위치를 확인해보고 일반 사진과 All..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 수의 개수가 1000개이고 시간 제한이 1초이므로 O(n^2)써도 충분한 문제이다. 그러므로 구현이 간단한 정렬 중 하나인 버블 정렬을 선택하여 풀었다. 입력 // 입력 Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int [] nums = new int[N]; for(int i=0; i< N;i++){ nums[i] = sc.nextInt..