Study-Note

문제 전체 스테이지(N) 사용자가 현재 멈춰있는 스테이지 번호 (stages) 결과 5 [2, 1, 2, 6, 2, 4, 3, 3] [3,4,2,1,5] 입출력 예 #1 1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다. 1 번 스테이지 실패율 : 1/8 2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다. 2 번 스테이지 실패율 : 3/7 마찬가지로 나머지 스테이지의 실패율은 다음과 같다. 3 번 스테이지 실패율 : 2/4 4번 스테이지 실패율 : 1/2 5번 스테이지 실패율 : 0/1 각 스테이지의 번호를 실패율의 내림..

풀이 입력된 수, num은 1 이상 8000000 미만인 정수라고 주어지는데, 이때 num을 int로 받으면 범위가 벗어남. long num으로 받아서 풀어야한다. int 범위: 부호 있는 정수 (32 bits) -2147483648 ~ 2147483647 long 범위: 부호 있는 정수 (64 bits) -9223372036854775808 ~ 9223372036854775807 코드 public class 콜라츠_추측 { public static void main(String[] args) { // Test case long num = 626331; solution(num); } public static int solution(long num) { int answer = 0; while(num != ..

문제 전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요. 풀이 반복문 없이 풀고 싶어서 Collections 사용 Collections.nCopies를 통해 4자리를 제외한 번호의 길이만큼 *를 생성하고, 문자열을 대치한다. 코드 import java.util.Collections; public class 핸드폰_번호_가리기 { public static void main(String[] args) { // Test case String phone_number = "01033334444"; solution(phone_number); } static String solution(Str..

스택 (Stack) 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 Stack stack = new Stack(); * 스택의 연산 pop(): 스택에서 가장 위에 있는 항목을 제거한다. push(item): item 하나를 스택의 가장 윗 부분에 추가한다. peek(): 스택의 가장 위에 있는 항목을 반환한다. isEmpty(): 스택이 비어 있을 때 true를 반환한다. * 관련 메서드 push(Object item): 해당 item을 Stack의 top에 삽입 pop(): Stack의 top에 있는 item을 삭제하고 해당 item을 반환. 스택이 비어있을 때는 EmptyStackException 발생 peek(): Stack의 top에 있는 i..

스택 사용하기 10828. 스택 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class BOJ_10828 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); Stack stack = new Stack(); for(int i=0; i

그리디(탐욕) 알고리즘 각 단계에서 최선책만을 선택하며 다음 단계로 이동하는 일고리즘 최적의 해를 구하는 알고리즘이 아니다. 최적의 해에 근사 해를 구하는 알고리즘 동적 프로그래밍이 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘. 동적 프로그래밍을 대체하는 것은 아니며 서로 보완해서 사용할 수 있다. 각 단계에서 최선책만을 선택하기 때문에 현재의 결과에 의해 다음 선택이 변하는 경우 적합한 알고리즘이 아니다. 각 단계에서 최선의 선택만을 하지만 결과는 최선이 아닐 수 있다. * 예제 위의 그림에서 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 ..

큰 문제를 풀기위해 작은문제를 풀어 큰문제를 풀어가는 방법 기존 재귀함수를 이용하여 피보나치 수열을 구하기 위해서는 많은 연산이 중복된다. 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다. 계산된 값을 버리지 말고 저장한다는 뜻이다. 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다. 이렇게 저장되는 배열을 캐시라고 한다. 배열 f를 캐싱용으로 하나 만들어 둔다. 이 배열 내부를 -1로 모두 초기화 시키고, 만약 -1이라면 결과값이 저장되어 있지 않으므로 계산을 실행한다. * 기존 재귀함수 사용 재귀함수는 Top-Down 방식이다. int fibo(int n) { if (n == 0) return 0; if (n == 1) r..

원소간 비교하지 않고 각 원소가 몇개 등장하는지 갯수를 세서 정렬하는 방법. 모든 원소는 양의 정수여야 한다. 시간복잡도는 O(n+k) 로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다. 정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나. 총 2개의 별도 배열을 필요로한다. O(n+k) 의 공간복잡도를 가진다. * 카운팅 정렬 단계 배열 안에 있는 원소 종류만큼의 새로운 배열을 생성하고 0으로 초기회시킨다. 만약 배열에 [0, 1, 3, 1, 3]이 있다면 0~3 크기의 배열 생성 각 원소의 갯수를 계산하여 배열 안에 담는다 0은 1개이므로 c[0]=1, 1은 2개이므로 c[1] = 2, 2는 존재하지 않으므로 0 누적합을 이용하여 계산한다. (배열에 값이 들어갈 위치를 선정하는 것) 따..

(1) 힙정렬 * 힙(heap) 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조 * 완전이진트리 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리 * 힙의 종류 부모노드의 키값이 자식노드의 키값보다 항상 큰 '최대 힙' 부모노드의 키값이 자식노드의 키값보다 항상 작은 '최소 힙' * 완전이진트리 배열로 구현하기 한 노드를 알면 그 노드의 부모, 자식들을 인덱스로 바로 접근 가능 노드 i의 부모 노드 인덱스 : i/2, (단, i > 1) 노드 i의 왼쪽 자식 노드 인덱스 : 2 x i 노드 i의 오른쪽 자식 노드 인덱스 : (2 x i) + 1 * 최대힙에서 힙 정렬하기 최대힙 직계관계에서는 무조건 부모는 자식(..

그리디(탐욕) 알고리즘 응용하기 11047. 동전 0 동전 개수의 최소값을 찾아야하므로 최선의 선택은 가장 큰 금액에서부터 빼는 것 import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_11047 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); int N = Integer.parseInt(input[0]); int K = Integer.parseIn..