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 |
현재 알고리즘 공부를 하고있는데 계속 시간초과가 나서 Scanner를 못쓰게 됐다...
앞으로 많은 문제들이 이러한 제약을 갖고있을 듯 하여 이제서야 공부하게 됐다.
1920번 수 찾기 자바로 풀어 본 짧은 글
1920번 수 찾기 1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주
spody.tistory.com
정렬과 이분탐색 모두 사용하는데 시간도 얼마 없는 문제.... 여기서 막혀버렸다
때문에 공부 조금 하고 정리할 겸 올리는 글....
사전준비
1 2 3 4 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; | cs |
1 | public static void main(String[] args) throws NumberFormatException, IOException{ | cs |
main에는 이렇게 IOExcption을 해줘야한다.
BufferedReader는 Scanner에 비해서 속도가 훨씬 빠르다.
이유는 입력된 데이터가 버퍼를 거쳐 전달돼서 데이터 처리 효율이 올라간다.
때문에 데이터가 많이 들어갈 때는 이 클래스를 활용해서 해결해야한다.
또 StringTokenizer를 사용하는 이유는 BufferedReader는 한 줄씩 입력을 받는 readLine을 사용하게 되는데
"10 5 3 1 10" 등 값을 띄어쓰기로 구분 해 입력받는다 이러한 한 줄을 처리하기 위해 String을 token간격으로 끊어 사용한다는 의미의
StringTokenizer를 사용해 해당 값을 처리해준다.
기본적으로 StringTokenizer을 사용하면 띄어쓰기 별로 10 5 3 1 10 이 값에서 nextToken()메소드를 사용할 때마다
순차적으로 꺼낸다.
ex)
1 2 3 4 5 6 7 8 9 10 11 | import java.io.BufferedReader; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] a = new int[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); } | cs |
input : 5
10 5 3 1 10
이 경우
a[0] = token(10)
a[1] = token(5)
a[2] = token(3)
a[3] = token(1)
a[4] = token(10)
이런 식이다.
형태를 잘 기억해두자.
| 우테코 프리코스 6기 1주차 숫자야구 회고 (0) | 2023.10.26 |
|---|---|
| 자바의정석 ch14 람다와 스트림 (0) | 2023.09.18 |
| nextInt()입력 후 nextLine()사용 시 주의점 (0) | 2022.12.18 |
1920번 수 찾기
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
첫째줄 n입력
둘째줄 n갯수 입력
셋째줄 m입력
넷째줄 m갯수 입력
m이 n에 있는지 탐색 후 1(true) 0(false)출력
일단 그냥 구현했을 때 실패했음 원인은 시간초과
알고리즘쪽 보니까 이분탐색하는 부분이 있더라...
이분탐색 구현해보고있는데 배열로 탐색하는 버전은 너무 어색하더라...
내일 for문으로 다시 구현해봐야할듯
for문 통해서 이분탐색 했는데 nextint로는 속도가 안나옴. 또 첫 구현에서는 탐색하는 수들도 전부 배열로 넣어서그런지
시간이 압도적으로 부족한 느낌이 들었음...
때문에 결국 bufferedReader, StringTokenizer를 사용해서 입출력속도를 많이 올렸다.
이제부턴 무조건 써야하나... 타입에 익숙해져야할듯
실버 4 문제인데 이틀을 썼다... 그래도 풀었을 때 상당히 기뻤음.
시간초과 -> 출력초과 -> 틀렸습니다 무한반복... 이분탐색 구현에 자꾸 빼먹는게 생겨서 그런가 참 힘들었다...
반례찾는것도 어렵고... 본인이 반례를 생각하려 노력해야하는데 쉽지않음
탐색이 주 문제니까 sort는 그냥 array.sort를 사용했고, 탐색을 직접 구현해봤다. 이분탐색 어려워징징징
--------
hint
이분탐색을 잘 구현해내면 된다.
내가 헷갈린 부분은 시간이 중요하니까
처음엔 배열 두개를 만들었는데
두개 만들 필요가 없는 걸 잘 생각해서 하면 될듯
--------
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 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); long[] a = new long[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(a); int m = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); int left; int right; int center; long key = 0; int isTrue = 0; for(int i = 0; i < m; i++) { key = Integer.parseInt(st.nextToken()); left = 0; right = a.length - 1; center = right / 2; isTrue = 0; while(left <= right) { if(a[center] == key) { System.out.println("1"); isTrue = 1; break; } else if(a[center] > key) { right = center - 1; center = (left + right) / 2; } else if(a[center] <key) { left = center + 1; center = (left + right) / 2; } } if(isTrue == 0) { System.out.println("0"); } } } } | cs |
실행시간 - 1272ms (이거맞냐....) 자바라 봐준거같은데 sort 직접 구현했으면 시간초과 걸렸을듯
약 2일 소요.... ㅜㅜㅜㅜ 실버가 이런데 더 올라갈 수 있을까...
| 백준 2164번 카드2 자바로 풀어 본 짧은 글 (0) | 2023.03.18 |
|---|---|
| 24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글 (0) | 2023.02.04 |
| 1427번 소트인사이드 자바로 풀어 본 짧은 글 (1) | 2023.01.08 |
| 백준 2563번 색종이 자바로 풀어 본 짧은 글 (0) | 2023.01.05 |
| 백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글 (0) | 2022.12.29 |
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 | class StationList{ public String name; public int next; } public class Main { 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 예제 java (0) | 2023.01.19 |
| 정렬 기본 예제 소스 O(N^2) (0) | 2023.01.08 |
| 이진 탐색 (0) | 2023.01.07 |