https://st-lab.tistory.com/108?category=857114 [백준] 2108번 : 통계학 - JAVA [자바] www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net.. st-lab.tistory.com *해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다. 여기서도 그냥 Arrays.sort()를 썼었는데 역시나 선생님은 시간 복잡도를 고려해서 카운팅 정렬을 쓰셨다. O(n)과 O(nlogn)은..

https://st-lab.tistory.com/107?category=857114 [백준] 10989번 : 수 정렬하기 3 - JAVA [자바] www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. ww.. st-lab.tistory.com *해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다. 제출 코드 (통과는 함) import java.io.BufferedReader; import java.io.IOException; im..

https://st-lab.tistory.com/106?category=857114 [백준] 2751번 : 수 정렬하기 2 - JAVA [자바] www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이.. st-lab.tistory.com *해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다. 역시나 선생님이 예상하신대로 나는 Arrays.sort를 썼지만 dual-pivot Quicksort에서 평균 시간 복잡도가 O(nlon..

[백준] 2750번 : 수 정렬하기 - JAVA [자바] www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 st-lab.tistory.com *해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다. 1. 선택정렬 첫 번째 인덱스부터 시작해서 뒤의 인덱스들과 값을 비교하여 최소값들을 앞 순서로 보내는 방법. 시간 복잡도는 O(n²)이다. import java.io.BufferedReader; import java.io.IOExcepti..

[백준] 9020번 : 골드바흐의 추측 - JAVA [자바] https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때 st-lab.tistory.com *해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다. 선생님(모르는 제자가 하나 생기신)이 저번에 알려주신 골드바흐의 추측이 문제로 나왔다. 댓글에 나랑 비슷하게 생각하신 분이 계셨다. 진짜 나는 여기서 한 번 더 배워간다. 선생님은 천재다. import java.io.BufferedReade..

에라토스테네스의 체 에라토스테네스가 발견한 소수를 찾는 방법! 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 위에서는 2~120 구간에서 소수를 구하니..

알고리즘 알고리즘의 효율성을 판단하는 기준은 다음과 같다. 시간 복잡도(time complexity) : 얼마나 빠르게 결과를 출력하는가? (연산을 할 때 거치는 단계의 수) 공간 복잡도(space complexity) : 메모리를 얼마나 사용하는가? 효율성을 판단하는 표기법은 총 세 가지이다. 1. 빅오 표기법 "이것보단 더 나쁠 순 없어"와 같이 최악일 때의 성능을 판단해서 평균과 가까운 성능으로 예측한다. (상한) 2. 빅오메가 표기법 "이것보단 더 좋을 순 없어"와 같이 최상일 때의 성능을 판단해서 예측한다. (하한) 3. 빅세타 표기법 평균적인 성능을 판단한다. 왜 Big-O 표기법을 사용할까? 시간 복잡도를 읽기 쉽고 빠르게 파악할 수 있게 해주기 때문이다. 어떤 알고리즘을 선택해야 할 때 알..

[백준] 2839번 : 설탕 배달 - JAVA [자바] https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만 st-lab.tistory.com *해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String..

[백준] 2869번 : 달팽이는 올라가고 싶다 - JAVA [자바] https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, st-lab.tistory.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..