[13~15일차] TIL 및 회고
지금은 알고리즘 위주라서 알고리즘을 풀기 위한 개념 이해 + 문제 풀이로 구성되어 있다.
13일차
순열
for 중첩
- for를 중첩해서 순열을 구현하면 nPr에서 n은 랜덤이 가능하지만, r은 고정될 수 밖에 없다.
- 시간복잡도 : 중복순열(nTTr) -> n^r
재귀로 푸는 방법
- 초기화: P(0) or P(r-1) 상관이 없다 (bottom -> up인지 top -> down인지를 결정하는 것이기 때문)
- 기저(중단) 조건
- 0 ~ r-1 까지 (0 < r)
- r~1 ~ 0 까지 (r-1 > -1)
- 시간 복잡도가 오래 걸릴 때는 공간 복잡도로 해결할 수 있다.
boolean[] visitedvisited 배열을 생성해서 기본값으로 false (사용 x, 중복 x)를 둔 뒤, true (사용 O, 중복 O)가 되면 visited 배열에 저장한다.
이렇게 되면 시간복잡도가 r^2에서 1로 바뀐다. (-> boolean 배열이 true / false 중 어느 것인지 확인만 하면 되니까)
=> 시간복잡도는 n^(r-중복제거) 가 된다
순열 시간복잡도 한계치
- 일반재귀 : 9P9
- swap, n, p : 10P10
- DP : 11P11 이상
+ 시간복잡도 총 정리
순열과 관련된 문제 (풀 수가 없어서 알고리즘 정도만 기록해 뒀다)
SWEA 6808 규영이와 인영이
1~18까지의 합 최대 총합 171
⇒ 86+86정도이기 때문에 무승부는 사실상 없음
- 두 카드의 총합은 (18*19)/2 = 171이므로 무승부는 나오지 않음. 이기거나 지는 상황만 체크한다.
- 입력
- 규영이의 카드가 입력으로 들어오고, 순서는 고정
- 인영이의 카드를 규영이가 선택하지 않는 카드로 선택한다.
- 18개 카드 중 규영이 카드 빼고 선택해야 함
- 규영이 카드를 입력 받으면 boolean 배열에 규영이 카드 기록 (카드번호가 index)
- boolean의 false인 index를 인영이의 카드로 사용하기
- 순열 만들기
- 순열을 다 만든 후에 반복문을 통해 전체 카드에 대한 승패를 결정
비트마스크
- 정수의 이진수 표현을 자료구조로 활용하여, 각 비트의 상태를 통해 집합이나 여러 상태를 효율적으로 표현하고 처리하는 기법
- 비트연산자 : &, |, shift, XOR
- 0 양수 / 1 음수 로 이루어져 있다.
비트마스크를 구하는 방법 (2, 3번 중요!!)
1. 공집합과 꽉 찬 집합 구하기
* A = 0; //32개의 원소가 모두 0이므로 공집합
* n = 10; //10개인 원소 (1111111111)
* A = (1<<n)-1; //꽉 찬 집합
0000000001 << 10 ==>10000000000
10000000000 -1 = 1111111111
2. 특정 위치에 1이 있는지 check로 & 사용
* &, and : 연산하려는 두 비트가 모두 1일때 1이고 나머지는 0
특정 위치에 1이 있는지 체크 용도로 사용, data & 0 => 0으로 초기화
int a1 = 0b1000;
int b1 = 0b0010;
int c1 = 0b1110;
3. 원소 추가 : k번째 위치에 원소를 추가(1로 마스킹)하기
* A |= (1<<k)
* k번째는 뒤에서 부터 세기 (0번째 부터~)
c1 |= (1<<k);
System.out.println(Integer.toBinaryString(c1));
SWAP 순열
- 원소의 위치를 바꿔가면서 새로운 순열을 만들어주는 것이다
- 시간을 많이 단축할 수 있다 (n!)
1. depth ~ R-1 까지 swap을 반복한다 (for문)
2. depth 전 index는 고정이다 (확정)
2-1. 기존의 원소 위치만 교체하므로 중복 검사를 할 필요가 없다.
⇒ depth=R까지 반복
특징
- 배열의 첫 원소의 위치부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 한다.
- depth를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고 depth 이상의 인덱스들만 swap을 진행한다.
- 순열을 따로 구하지 않아도 된다 -> 원본 배열을 그대로 사용한다
- nPn, nPr 모두 됨. 단 nPr시 전체 배열에서 앞에 r개만 사용
- 단점: 순열이 사전순(오름차순)으로 나오지 않는다. 수행속도 9P9 8ms 안전 10P10 34ms 안전
만약 R = 3인 경우)
- R ≥ 3 일 때는 마지막은 결국 자기 자신 교체이기 때문에 depth = R까지 갈 필요 없음 (R-1까지만 가면 된다)
- R ≤ 2 일 때는 depth = R까진 가야 됨
public static void main(String[] args) {
input = new int[] {1,2,3};
N = input.length;
R = input.length;
long start = System.currentTimeMillis();
permutation(0); // 0번째 원소부터 뽑기
long end = System.currentTimeMillis();
System.out.printf("순열 수: %d 반복횟수:%d 수행시간: %dms %n ", tc, count, end-start);
}
// swap 함수
private static void swap (int i, int j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
/**
* @param depth : 순열 배열의 index
**/
private static void permutation(int depth) {
if (depth==R){
tc++;
return;
}
// depth 이전 인덱스는 고정, depth부터 swap 하기
for (int i = depth; i < N; i++) { // i = depth이고, i = 0이 아니기 때문에, depth부터 하기 때문에 시간이 빠름!!!!!
count++; // 반복 횟수 세기
// 두 수를 swap해서 새로운 순열을 만든다.
swap(i, depth);
permutation(depth+1);
// 다음 순열을 만들기 위해서 원복
swap(i, depth); // 이렇게 해도 바뀜
// swap(depth, i);
}
}
조합
- 서로 다른 N개의 원소에서 R개를 중복없이, 순서를 고려하지 않고 선택하는 것 (ex. 로또 뽑기)
- 특징: 첫번째 인덱스 숫자 < 두번째 인덱스 숫자 < … < n번째 인덱스 숫자
-> 항상 첫 < 둘 이렇게 숫자가 더 커짐
=> 중복 없이, 순서를 고려하지 않기 때문에 조합의 특징이 뒤에 있는 원소의 index는 항상 앞에 있는 원소의 index 보다 커야된다.
package combination;
import java.util.Arrays;
public class CombinationTest1 {
static int tc; // test case
static int n, r;
static int[] numbers;
static int[] input;
public static void main(String[] args) {
input = new int[] {1,2,3};
n = input.length;
r = 2;
numbers = new int[r];
combi(0,0);
}
/**
* @param depth 조합을 뽑아놓은 배열의 index
* @param start 조합을 시작할 index
* */
private static void combi(int depth, int start) {
if (depth == r) { // 기저조건
tc++;
return;
}
for (int i = start; i < n; i++) { // 반복조건
numbers[depth] = input[i];
combi(depth+1, i+1);
}
}
}
+ 조합 관련 문제
- 백준 2309 일곱난쟁이 (해결)
package 코드공유.BOJ;
import java.util.Arrays;
import java.util.Scanner;
public class Main_2309_일곱_난쟁이_김주희 {
static int n, r;
static int[] numbers;
static int[] input;
static int total;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
input = new int[9];
n = input.length;
r = 7;
numbers = new int[r];
for (int i=0; i < n; i++) {
input[i] = sc.nextInt();
}
combi(0,0);
}
private static void combi(int depth, int start) {
if (depth == r) {
if (total == 100) {
Arrays.sort(numbers);
for (int num : numbers) {
System.out.println(num);
}
System.exit(0);
}
return;
}
for (int i=start; i < n; i++) {
numbers[depth] = input[i];
total += input[i];
combi(depth+1, i+1);
total -= input[i];
}
}
}
14일차
문제 푸는 데 집중해서 기록해둔게 없다... 아마 조합 문제를 엄청 고민했던 것 같다 ㅜ
공포의 수영장 ..
이후 프론트 대면반 단체 회식이 있어서 대면반 사람들과 친해지게 된 계기가 되어서 너무 좋았고 알찼던 시간이었다.
프로젝트 때문에 맘 편히 즐기진 못했지만 .. ㅜㅡㅜ
15일차
알고리즘 고수가 되면 풀어 볼 문제
1. 백준 1062 가르침 (비트마스킹)
2. 프로그래머스 42820 후보키
자료구조
선형
- 데이터와 다음 데이터가 연결된 것 (1개씩 맵핑된다)
스택
- 먼저 들어간 값이 가장 나중에 나오는 구조 (LIFO)
- 주로 괄호 검사기 문제에 주로 활용된다.
큐
- 먼저 들어간 값이 가장 먼저 나오는 구조 (FIFO)
- 요세푸스 문제가 큐 문제이다.
관련 문제
백준 10799 쇠막대기 (stack)
- 괄호 짝이 맞으면 레이저를 쏴서 현재 레이저를 쐈을 때 앞에 짝이 안 지어진 '('의 갯수를 세는 문제이다.
- 현재 괄호 바로 전 괄호의 모양에 따라서 pop을 할 지, total에 값이 쌓이게 될 지 결정된다.
- 문제를 해석하는 데 정말 오래 걸렸다.. 그래도 해석만 하면 어느 정도 풀리는 문제였다.
package 코드공유.BOJ;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main_10799_쇠막대기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
String line = br.readLine();
int total = 0;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < line.length(); i++) {
char c = line.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
stack.pop();
if (line.charAt(i - 1) == '(') {
total += stack.size();
} else {
total++;
}
}
}
System.out.println(total);
}
}
백준 1158 요세푸스 문제 (queue)
- 문제 자체는 쉬웠지만, 풀기 어려웠던 문제
- K번째 해당하는 숫자를 poll() 하고 그 값을 offer()를 통해 queue 뒤로 삽입한 뒤, poll()한 값을 result 리스트에 담아서 결과를 출력하는 문제이다.
- 출력 방식 자체도 독특했다.
package 코드공유.BOJ;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main_1158_요세푸스_문제 {
int N;
int K;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
Queue<Integer> q1 = new LinkedList<>();
for (int i = 1; i <= N; i++) {
q1.offer(i);
}
List<Integer> result = new ArrayList<>();
while(!q1.isEmpty()) {
for (int j = 0; j < K-1; j++) {
int var = q1.poll();
q1.offer(var);
}
result.add(q1.poll());
}
System.out.print("<");
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i));
if (i != result.size() - 1) {
System.out.print(", ");
}
}
System.out.print(">");
}
}
회고
드디어 순조부가 끝났나?? 싶긴 한데.. 문제들이 너무 어렵고 헷갈려서 하염없이 문제만 쳐다봤던 날이 많아서 아쉬운 것 같다.
프로젝트가 생각보다 늦게 끝나고 너무 빠듯해서 주말에도 알고리즘 공부할 시간이 없었어서 너무 아쉬웠다 ㅜㅜ
얼른 백엔드 파트 전에는 끝내서 백엔드 때는 진도에 맞춰서 잘 따라갈 수 있도록 해야겠다.
하~~ 지긋지긋한 프로젝트 빨리 끝내고 싶다 이번주 내로 끝내버려야지 .......... 아마도....
그래도.. 유레카 덕분에 규칙적인 삶을 살 수 있어서 약간 갓생 사는 느낌 나서 좋긴 하다 ^^^^
사실 이번 프로젝트하면서 백엔드 공부의 중요성을 약간 깨닫게 되어서 빨리 알고리즘 끝내고 백엔드 배워 보고 싶긴 하다
그리고 이번 주 개꿀인 점 : 하루 휴강 🥳🥳🥳🥳🥳
그리고 너무 기대된다 !!!!! 새로운 지식 많이 얻을 것 같다