| 깃 인텔리제이에서 손쉽게 사용하기 (커밋메시지, 커밋삭제 등) (0) | 2023.07.07 |
|---|---|
| 서버란 무엇인가요? (0) | 2023.02.22 |
| 윈도우 단축키 관련 (0) | 2023.02.21 |
주로 쓸거같은 기능 + 모르는 것들만 따로 또 빼둠
비트와 바이트 문자인코딩 개념 정리
IP(Internet Protocol)주소알기
| 가상메모리 (0) | 2023.02.23 |
|---|---|
| 웹과 인터넷 개념 (0) | 2023.02.21 |
| 비트와 바이트 문자인코딩 개념 (0) | 2023.02.21 |
| DNS가 뭔가요? (0) | 2023.02.21 |
| 영상후기 - 생활코딩, 인터넷과 웹의 역사 (0) | 2023.02.21 |
Domain Network Service
| 가상메모리 (0) | 2023.02.23 |
|---|---|
| 웹과 인터넷 개념 (0) | 2023.02.21 |
| 비트와 바이트 문자인코딩 개념 (0) | 2023.02.21 |
| ip주소 (0) | 2023.02.21 |
| 영상후기 - 생활코딩, 인터넷과 웹의 역사 (0) | 2023.02.21 |
주로 쓸거같은 기능 + 모르는 것들만 따로 또 빼둠
| 깃 인텔리제이에서 손쉽게 사용하기 (커밋메시지, 커밋삭제 등) (0) | 2023.07.07 |
|---|---|
| 서버란 무엇인가요? (0) | 2023.02.22 |
| 인터넷은 어떻게 작동되나요? (0) | 2023.02.22 |
24060번 알고리즘 수업 - 병합정렬 1
24060번: 알고리즘 수업 - 병합 정렬 1 (acmicpc.net)
24060번: 알고리즘 수업 - 병합 정렬 1
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
www.acmicpc.net
진짜 미친문제.... 의사코드 따라해서 겨우한거같은데 또 이걸 제대로 하지도 못함...
이건 아직도 잘 모르겠다...
다른 알고리즘 책에서 병합정렬 배운거 그대로 구현해서 해봤는데 실패하고 아직 구조이해가 부족한듯?
의사코드 따라해도 안돼서 그냥 참고해서 마무리했다.
정말 머리가 못따라가나... ㅜㅜ
--------
hint - 의사코드가 도움되긴 함
--------
실패한 병합정렬
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | public class Main { static int[] buff = new int[500000]; static int count = 0; static int searchCount = 0; static int setResult = -1; static void merge_sort(int[] a, int left, int right) { // 그냥병합정렬 if(left < right) { int center = (left + right) / 2; int p = 0; int i; int j = 0; int k = left; merge_sort(a, left, center); merge_sort(a, center + 1, right); //1)배열의 앞부분(a[left] ~ a[center])을 //buff[0] ~ buff[center - left]에 복사합니다. //for문이 끝날 때 p의 값은 복사한 요소의 개수 center - left + 1이 됩니다. for(i = left; i <= center; i++) { buff[p++] = a[i]; } // 2)배열의 뒷부분(a[center + 1] ~ a[right])과 //buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 b에 저장합니다. while(i<=right && j < p) { if(buff[j] <= a[i]) { if(count == searchCount) { setResult = buff[j]; } System.out.println("현재 수 : " + buff[j]); a[k++] = buff[j++]; count++; } else { if(count == searchCount) { setResult = a[i]; } System.out.println("현재 수 : " + a[i]); a[k++] = a[i++]; count++; } } // 3)배열 buff에 남아있는 요소를 배열 a에 복사합니다. while(j < p) { if(count == searchCount) { setResult = buff[j]; } System.out.println("현재 수 : " + buff[j]); a[k++] = buff[j++]; count++; } } } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); int arrayN = Integer.parseInt(st.nextToken()); searchCount = Integer.parseInt(st.nextToken()); int[] array = new int[arrayN]; StringTokenizer st1 = new StringTokenizer(br.readLine()); for(int i = 0; i < arrayN; i++) { array[i] = Integer.parseInt(st1.nextToken()); } merge_sort( array, 0, arrayN-1); // 이게 진짜 병합정렬 bw.write(Integer.toString(setResult) + " "); bw.write(Integer.toString(count)); bw.flush(); bw.close(); } } | cs |
망했던 반례 :
8 9
1 2 3 4 5 6 7 8
solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int[] buff = new int[500001]; static int count = 0; static int searchCount = 0; static int setResult = -1; static void merge_sort(int a[], int p, int r) { if(p < r) { int q = (p + r) / 2; merge_sort(a, p, q); merge_sort(a, q + 1, r); merge(a, p, q, r); } } static void merge(int a[], int p, int q, int r) { int i = p; int j = q + 1; int t = p; while(i <= q && j <= r) { if(a[i] <= a[j]) { buff[t++] = a[i++]; } else { buff[t++] = a[j++]; } } while(i <= q) { buff[t++] = a[i++]; } while(j <= r) { buff[t++] = a[j++]; } i = p; while(i<= r) { a[i] = buff[i++]; if(++count == searchCount){ System.out.println(a[i-1]); System.exit(0); } } } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); int arrayN = Integer.parseInt(st.nextToken()); searchCount = Integer.parseInt(st.nextToken()); int[] array = new int[arrayN]; StringTokenizer st1 = new StringTokenizer(br.readLine()); for(int i = 0; i < arrayN; i++) { array[i] = Integer.parseInt(st1.nextToken()); } merge_sort( array, 0, arrayN - 1); // 이게 진짜 병합정렬 bw.write(Integer.toString(setResult)); bw.flush(); bw.close(); } } | cs |
실행시간 - 720ms
언젠가 재도전 해보자...
| 백준 11004번 K번째 수 자바로 풀어 본 짧은 글 (0) | 2023.03.25 |
|---|---|
| 백준 2164번 카드2 자바로 풀어 본 짧은 글 (0) | 2023.03.18 |
| 1920번 수 찾기 자바로 풀어 본 짧은 글 (0) | 2023.01.14 |
| 1427번 소트인사이드 자바로 풀어 본 짧은 글 (1) | 2023.01.08 |
| 백준 2563번 색종이 자바로 풀어 본 짧은 글 (0) | 2023.01.05 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | public class Main { public static void printArray(int[] a) { for(int i = 0; i < a.length; i++){ System.out.println(a[i]); } } public static int divideArray(int[] a, int head, int tail) { int left, right, temp; left = head + 1; right = tail; while(true) { while(left < tail && a[head] > a[left]) { left++; } while(a[head] < a[right]) { right--; } if(left >= right) { break; } temp = a[left]; a[left] = a[right]; a[right] = temp; left++; right--; } temp = a[head]; a[head] = a[right]; a[right] = temp; return right; } public static void sortArray(int[] a, int start, int end) { int pivot; if(start < end) { pivot = divideArray(a, start, end); sortArray(a, start, pivot - 1); sortArray(a, pivot + 1, end); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for(int i = 0; i < n; i++) { a[i] = sc.nextInt(); } //printArray(a); sortArray(a, 0, a.length - 1); printArray(a); } } | cs |
O(nlogn)의 속도가 평균적이고, 최악에는 O(n^2)의 시간복잡도가 나오기도 한다.
| LinkedList 예제 java (0) | 2023.01.19 |
|---|---|
| LinkedList 예제 (0) | 2023.01.11 |
| 정렬 기본 예제 소스 O(N^2) (0) | 2023.01.08 |
| 이진 탐색 (0) | 2023.01.07 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | class StationList{ public String name; public int next; } public class LinkedList { public static StationList[] list = new StationList[10]; public static int head; public static void initStationList() { for(int i = 0; i < list.length; i++) { list[i] = new StationList(); } list[0].name = "부산"; list[0].next = -1; list[1].name = "대전"; list[1].next = 3; list[2].name = "서울"; list[2].next = 4; list[3].name = "동대구"; list[3].next = 0; list[4].name = "천안아산"; list[4].next = 1; head = 2; } public static void printStationList() { int idx = head; while(idx != -1) { System.out.print("[" + list[idx].name + "] -> "); idx = list[idx].next; } System.out.println(); } public static void insertStationList(int insIdx, String insName, int prevIdx) { list[insIdx].name = insName; list[insIdx].next = list[prevIdx].next; list[prevIdx].next = insIdx; } public static void deleteStationList(int delIdx, int prevIdx) { list[prevIdx].next = list[delIdx].next; } public static void main(String[] args) { initStationList(); printStationList(); insertStationList(5, "광명", 2); printStationList(); deleteStationList(5, 2); printStationList(); } } | cs |
| 퀵정렬 예제소스 (0) | 2023.01.25 |
|---|---|
| LinkedList 예제 (0) | 2023.01.11 |
| 정렬 기본 예제 소스 O(N^2) (0) | 2023.01.08 |
| 이진 탐색 (0) | 2023.01.07 |