코린이의 소소한 공부노트

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 두 소수의 순서만 다른 것은 같은 파티션이다. 1. 입력 - 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. 2. 출력 - 각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다. 3. 예제 4. 코드 import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 ..

1. Problem - 한 문자열(A)에 다른 문자열(B)이 포함되어 있는지 단순 비교, KMP, 라빈-카프 알고리즘 3가지를 이용해 확인해 보자.. 1) 단순 비교: A의 맨 앞에서부터 B가 있는지 확인한다. 2) KMP(Knuth-Morris-Pratt): 접두사(prefix)와 접미사(suffix), pi[]를 이용해 비교 연산량을 줄인 알고리즘 - pi[i]에는 B의 부분 문자열 B[0]~B[i]에서 길이가 부분 문자열보다 짧은 것 중 접두사와 접미사가 같은 것을 찾은 후 가장 긴 값을 저장한다. - pi[3]==1이라면, B[0]~B[3]에서 접두사와 접미사의 공통부분의 길이가 1이라는 것이다. 3) 라빈-카프(Rabin-Karp): 문자열을 해시(hash) 기법을 이용해 데이터를 단순하게 바꿔..

1. Input 1) int num 2. Output 1) num의 각 자리 숫자들끼리 다음 조건에 따라 순서를 바꿨을 때 만들 수 있는 가장 큰 숫자를 반환 - 짝수는 짝수끼리, 홀수는 홀수끼리 자리를 바꿀 수 있다. - num의 각 자리 숫자가 ‘홀짝짝홀’이었다면, 순서를 바꾸고 만든 숫자도 ‘홀짝짝홀’이어야 한다. 3. Constraint 1) 1 0){ int n = num%10; num /= 10; if(n%2==0) even.add(n); else odd.add(n); } odd.sort(Comparator.naturalOrder()); even.sort(Comparator.naturalOrder()); int a = 0, b = 0; StringBuilder sb = new StringBui..

1. Input 1) int[] nums (0-indexed) 2. Output 1) nums에서 인덱스가 홀수인 것과 짝수인 것을 나눠서 정렬한 결과를 반환 - 인덱스가 홀수인 것 끼리는 내림차순으로 정렬한다. - 인덱스가 짝수인 것 끼리는 오름차순으로 정렬한다. 3. Constraint 1) 1

1. Input 1) int[] cost - cost[i] = i번째 사탕의 가격 2. Output 1) 모든 캔디를 사는 데 필요한 최소 비용을 반환 - 캔디를 a, b 2개 사면 3번째 사는 캔디는 무료이다. - 이때 무료로 살 수 있는 캔디의 가격은 a와 b의 가격 이하여야 한다. 3. Constraint 1) 1

1. Input 1) String[] words1 2) String[] words2 2. Output 1) words1과 word2에 공통적으로 나타나는 단어 중 각 배열에 1번씩만 나타나는 단어의 수를 반환 3. Constraint 1) 1

1. Input 1) int n - 그래프의 노드의 개수 - 노드에는 0번부터 n-1번까지의 번호가 붙어 있다. 2) int[][] edges - edges[i] = [u_i, v_i]. u_i번 노드와 v_i번 노드가 연결되어 있다. 3) int source 4) int destination 2. Output 1) 주어진 그래프에서 source에서 destination으로 가는 경로가 있다면 true, 없다면 false를 반환 3. Constraint 1) 1

1. Input 1) String s 2. Output 1) s를 fancy string으로 만든 결과를 반환 - fancy string이란 같은 문자가 연속으로 3개 이상 나오지 않는 문자열을 말한다. - 이때 s를 fancy string으로 만들기 위해 삭제한 문자의 개수가 최소가 되어야 한다. 3. Constraint 1) 1 Output: "aabaa" Input: s = "aab" -> Output: "aab" 5. Code 1) 첫 코드(2023/06/21) class Solution { public String makeFancyString(String s) { StringBuilder sb = new StringBuilder(); int i = 0; while(i

1. Input 1) int[][] ranges - ranges[i] = [start_i, end_i] 2) int left 3) int right 2. Output 1) [left, right] 범위의 정수가 모두 ranges에 담겨 있다면 true, 아니면 false를 반환 3. Constraint 1) 1