전체 글159 [Java/백준/정렬] 2108 - 통계학 문제 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 코드 (틀렸습니다) 예제 테스트케이스는 통과한다. (아마 산술 평균에서 틀린거 같다. 이런 방법이 아니라 반올림을 사용했어야 했다) 최빈값은 -4000~4000 까지 담을 수 있는 int 형 배열을 선언한 뒤 숫자+4000 인덱스에 빈도수를 더하도록 했다. 아래 코드의 arr 배열과 처음 for문을 참고하면 된다. import java.io.BufferedReader; import java.io.IOException; impo.. 2020. 8. 24. [Java/프로그래머스] H-Index 문제 https://programmers.co.kr/learn/courses/30/lessons/42747# 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 코드 단순 이중 for문 이용 class Solution { public int solution(int[] citations) { int answer = 0; int paper_num = citations.length; for(int i=0; i=i) answer = i; } return answer; } } 정렬이 필요 .. 2020. 8. 23. [Java/백준/정렬] 2750 - 수 정렬하기 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net O(n^2)으로 풀어도 된다고 하니 맘 편하게 선택 정렬과 버블 정렬을 써볼까 한다. 코드 1 버블 정렬 (시간: 104 ms) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; .. 2020. 8. 20. [Java/백준/정렬] 10989 - 수 정렬하기 3 (using Counting Sort) 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamRe.. 2020. 8. 20. [Java/백준/정렬] 2751 - 수 정렬하기 2 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 시행착오 1 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있다길래, 병합정렬로 풀려고 했는데 시간초과가 생겼다. 아래 코드와 비슷한거 같은데 왜 시간이 더 걸리는 걸까ㅠ import java.util.Scanner; public class Main { private static void mergeSort(int[] arr) { int[] tmp = new int[ar.. 2020. 8. 20. [자료구조/C, Java] 계수 정렬(Counting Sort) https://www.youtube.com/watch?v=n4kbFRn2z9M 목소리가 특이하신 분...ㅎ 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다. 계수 정렬(Counting Sort)는 단순하게 '크기를 기준으로 개수를 세는' 알고리즘이다. 지금까지는 모든 데이터를 그 자체로 위치를 바꾸어가며 정렬하는 알고리즘이었다. 계수 정렬은 '크기를 기준'으로 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없다. 모든 데이터에 한 번씩만 접근하면 된다는 점에서 무척이나 효율적이다. 1. 결과 배열의 크기를 숫자의 크기 범위만큼 잡아준다. 2. 하나를 확인할 때마다 배열에 데이터를 한개씩 증가시켜준다. 3. 출력할 때는 단순하게 배열 원소의 숫자만큼 반복하면 된다. - 시간 복잡도 : O(N).. 2020. 8. 20. [자료구조/Java] 선택 정렬(Selection Sort) youtu.be/uCUu3fF5Dws 배열을 돌면서 작은 값부터 하나씩 앞으로 차곡차곡 옮기는 것 - 처음부터 끝까지 돌면서 가장 작은 값을 시작점의 숫자와 swap → 두번째부터 끝까지 돌면서··· - 시간복잡도 : O(n^2) 코드 public class Test{ private static void selectionSort(int[] arr){ selectionSort(arr, 0); } private static void selectionSort(int[] arr, int start){ if(start < arr.length-1){ int min_index = start; for(int i=start; i 2020. 8. 20. [자료구조/Java] 버블 정렬(Bubble Sort) youtu.be/YbsQiiubO74 앞에서부터 2개씩 비교해서 작은 것을 앞으로, 큰 것을 뒤로 보낸다. (제일 뒤부터 정렬된다) - 시간 복잡도 : O(n^2) 코드 public class Test{ private static void bubbleSort(int[] arr){ bubbleSort(arr, arr.length-1); } private static void bubbleSort(int[] arr, int last){ if(last > 0){ for(int i=1; i arr[i]){ swap(arr, i-1, i); } } bubbleSort(arr, last-1); } } private static void swap(int[] arr, int source, int target){ int .. 2020. 8. 20. [자료구조/Java] 병합정렬(Merge Sort) youtu.be/QAyl79dCO_k 1. 파티션이 낱개가 될 때까지 배열을 반으로 쪼갠다. 2. 두 배열을 잡아 작은 수부터 비교하고, 작은 것을 먼저 넣는다. 정렬이 완료되면 원래 배열의 자리에 복사한다. 3. (2의 반복) 정렬된 작은 배열을 병합한다. 과정) 각 배열의 가장 작은 수부터 비교하고 작은 것을 먼저 넣는다. n개만큼씩 logn번 돌기 때문에 시간복잡도는 O(nlogn) n번 호출, 1번 호출 당 검색해야 하는 데이터의 개수가 절반씩 줄어드니까 logn Merge Sort 는 실행시에 별도의 저장공간을 필요로 하기 때문에, 저장공간이 없다면 Quick Sort를 사용한다. 코드 public class Test{ private static void mergeSort(int[] arr){ .. 2020. 8. 19. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음