[Java] 완전탐색: 순열, 조합, 부분집합

1. 순열 public class Permutation { static char[] arr; static int R; // 만들 순열의 길이 static int[] selected; // 고른 값들의 인덱스를 저장하는 배열 (길이: R) /** * 중복 허용하는 경우 */ static void perm1(int r) {// r: 현재까지 고른 개수 if (r == R) { for (int i = 0; i < R; i++) System.out.print(arr[selected[i]]); System.out.println(); return; } for (int i = 0; i < arr.length; i++) { selected[r] = i; perm1(r + 1); } } /** * 중복 허용하지 않는 경..

• format_list_bulleted TIL/Java
• · 2023. 3. 16.
• textsms

[Java] API 이용한 정렬

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; // Comparator 클래스 상속 (Comparator -> Interface) class testComparator implements Comparator { @Override public int compare(String a, String b) { return a.charAt(0) - b.charAt(0); // charAt(0): 가장 앞에 있는 문자 } } public class sortTest { public static void main(String[] args) { // 1. Array.so..

• format_list_bulleted TIL/Java
• · 2023. 3. 15.
• textsms

[Java] 정렬 - 퀵, 병합

1. 퀵 정렬 Quick sort pivot 값을 기준으로 pivot의 앞과 뒤에 더 작거나 큰 값을 모으는 방식으로 재귀를 이용하여 완성 - 시간복잡도: O(n²) / O(nlogn) // 두 값의 자리를 바꾸는 함수 public static void swap(int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static int partition(int[] arr, int start, int end) { int pivot = start; int left = start + 1; int right = end; while (left = end) return; // divide int mid = (sta..

• format_list_bulleted TIL/Java
• · 2023. 3. 14.
• textsms

[BOJ] 17608. 막대기 (python / Java)

백준 17608 막대기 파이썬 자바 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net # 파이썬: 단순 계산 - sys 안 쓰고 input으로 처리하면 시간 초과! 주의 import sys N = int(sys.stdin.readline()) L = list(int(sys.stdin.readline()) for _ in range(N)) ans = 1 max = L[-1] # 오른쪽부터 하나씩 최대값 변경해가면서 탐색 for x in range(N - 1, -1, -1): if L[x] > max: max = L[x]..

• format_list_bulleted Algorithm/BOJ
• · 2023. 3. 14.
• textsms

[BOJ] 10986. 나머지 합 (Java / Python)

백준 10986: 나머지 합 (자바/파이썬) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이걸.. 내가 풀었다고 해도 되나요? 1. 모듈러 연산 이용하기(A + B) % M = ((A % M) + (B % M)) % M - 이 문제에서 찾아야 하는 것(A - B) % M = 0 - 그렇다면 이용해야 하는 것(A % M) - (B % M) = 0(A % M) = (B % M) 누적합의 나머지를 구한 후모듈러 연산을 이용할 수 있는, 즉 같은 나머지를 가진 2개 ..

• format_list_bulleted Algorithm/BOJ
• · 2023. 3. 12.
• textsms

[BOJ] 12933. 오리 (python)

백준 12933. 오리 (파이썬) 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net # [BOJ] 12933. 오리 2023-03-09 S = input() ans = 0 A = [] L = ['0', 'q', 'u', 'a', 'c', 'k'] for i in range(len(S)): s = S[i] if L.index(s) == 1: # q가 나온 경우 t = 1 for j in range(len(A)): if L.index(A[j][-1]) == 5: A[j] += s t = 0 break if t == 1: A.append(s..

• format_list_bulleted Algorithm/BOJ
• · 2023. 3. 10.
• textsms