처음부터 차근차근

문제 : https://www.acmicpc.net/problem/10773 필자는 해당 문제를 배열로 풀고 정답이라 나왔는데, 다른 사람들 풀이 보니까 stack을 쓰는 사람이 많아서 stack공부도 할겸 업로드하게 되었다. 문제에서 사용하는 개념Stack 클래스https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html함수명반환 형식기능push(item)void스택에 요소 추가.pop()item스택의 맨 위 요소를 제거하고 반환peek()item스택의 맨 위 요소를 반환하나, 제거하지 않음.empty()boolean스택이 비어 있는지 여부를 반환. 비어있으면 false, 아니면 true   문제 풀이import java.util.*;import ja..

문제 : https://www.acmicpc.net/problem/11650 Arrays.sort함수는 1차원 배열 뿐만아니라 2차원 배열도 정렬 가능하다.단, Comparator 객체를 써서 커스텀 해줘야한다. 문제에서 쓰인 개념Arrays.sort로 2차원 배열 정렬.Arrays.sort(dots, new Comparator() { // 이차원 배열 정렬 @Override public int compare(int[] one, int[] two) { if (one[0] == two[0]) { return one[1] - two[1]; // y좌표 오름차순 } else { return one[0] - two[0]..

문제 : https://www.acmicpc.net/problem/2775 제한 시간이 0.5초로 아주 짧다.이 문제를 봤을 때 처음 떠올렸던 방식이 아예 처음에 2차원 배열을 초기화 시키는 방식이었다.그러나 최대 층수도 안정해져있고, for문을 돌리기에는 제한 시간이 너무 적어서 다른 방법을 고안해냈다.그러다 떠올린 방법이 재귀함수를 이용하는 방법이었다.어차피 k층 n호 사람 수 = k-1층 1~n호 사람 수의 합 이니까 재귀 함수를 통해서 구현할 수 있다고 생각했다. 문제 풀기전 계획k층 sum(n호 사람 수) = k-1층 sum(1호 ~ n호 사람 수) arr[15] = { 1....14}a(int k층, int n호){ if (k == 0) { return arr[n]; } else { int..

문제 : https://www.acmicpc.net/problem/2751 해당 문제를 Arrays.sort 써서 했더니 실버5 문제임에도 불구하고 정답이 나와버려서 너무 허무했다.그래서 다른 풀이 방법을 찾아봤다.이 문제는 Collections.sort()를 쓰면 더 빠르게 풀수있다. 문제에서 사용하는 개념함수알고리즘평균 시간복잡도최악 시간복잡도Arrays.sort()dual-pivot QuicksortO(nlogn)O(n2) Collections.sort()hybrid sorting algorithm (= Timsort) (Timsort = 합병정렬 + 삽입정렬)합병정렬 : O(nlogn) 삽입정렬 : O(n) 합병정렬 : O(nlogn) 삽입정렬 : O(n2)   https://docs.oracle..

문제 : https://www.acmicpc.net/problem/2609 이 문제에서 필요한 개념유클리드 호제법최대공약수를 구하는 알고리즘.큰 수를 작은 수로 나누어 떨어지게 한 뒤, 수를 반복적으로 수행하여 나머지 0이 될때까지 작동함.public static int gcd(int num1, int num2) { if (num2 == 0) return num1; return gcd(num2, num1 % num2);}위와 같이 재귀방식으로 최대공약수를 구한다.여기서 주의할점은 큰수를 num1로, 작은수를 num2로 둬야한다는 점. 안그러면 무한루프에 빠지게 된다... 최소공배수 = (두 수의 곱) / 최대공약수  문제 풀이import java.util.*;import java.io.*;pu..

문제 : https://www.acmicpc.net/problem/2108 최빈값 구하는데 시간이 너무 오래걸렸었다.입력값으로 음수가 들어와서 최빈값 구할 때 배열을 하나 더 만들었어야 했었고,여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력하라는 조건도 있어서 로직이 복잡했다ㅠㅠ결국 최빈값 부분은 해답을 보고 풀었었는데, 코드를 짧고 간결하게 잘짠 사람들이 많아서 대단하게 느껴졌다...  문제에서 사용한 개념Math.round(소수) : 소수점 첫번째자리에서 반올림 하여 정수를 리턴함. 가장 가까운 정수를 리턴한다고 생각하면 편함.리턴 형식매개변수longround(double a)intround(float a) 공식 문서 : https://docs.oracle.com/javase/7/docs/..

문제 : https://www.acmicpc.net/problem/1920이 문제는 시간 제한이 1초로 굉장히 짧다.그래서 이분탐색(이진탐색) 알고리즘을 사용해야 한다.정말 놀라운 사실이.. 자바에는 이분탐색 함수가 이미 만들어져 있다!!!그래서 손쉽게 풀 수 있었다. 문제에서 사용되는 개념이분탐색(이진탐색)정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.예시){1, 2, 3, 4, 5} 배열이 있고, 찾고자 하는 값은 2 이다.가장 먼저 가운데 3을 찍어서 2가 3보다 큰지 작은지 같은지 비교하고, 3보다 작으면 왼쪽으로, 크면 오른쪽으로 가서 찾는다. Arrays.binarySearch(arr, key) https://docs.oracle.com/javase/8/docs/..

문제 : https://www.acmicpc.net/problem/1676 문제의 최댓값인 500!은 자릿수만 1135자 가까이 돼서 일반적인 int문으로 데이터를 담는것이 불가능하다.그래서 BigInteger을 써야한다.  문제에서 사용되는 개념 BigInteger 타입범위기본형/참조형저장 위치int-2,147,483,648 ~ 2,147,483,647기본형(value type)StackBigInteger무한 (Infinity)참조형(reference type)Heap 선언 방법import java.math.BigInteger;BigInteger num = new BigInteger("1");  연산num.subtract(BigInteger.valueOf(2))num.multiply(BigInteger..