[13일 차] 알고리즘 (Basic5)

---

25/02/12 (수)

순식간에 수요일입니다.

금요일 졸업식하고, 토요일 기사시험치면 또 일주일이 순삭입니다.

기사 범위가 넓어서 그런지 기출을 풀고 또 풀어도 모르는 문제가 한 두문제씩 계속 튀어나옵니다..

주짓수 가고싶은데 바빠서 못가고있습니다..

빨리 합격하고 마음 편하게 수업 듣고 복습하고싶네요.

---

1.  교재 강의

1.1. 강의

1) 분할 정복 알고리즘

 

2) 비트 마스크 연산

boolean type 정수 배열

 

& 연산

0000 0000 으로 시작

mask : 0000 1010 (두번째, 네번째 사용 중 index 중 1, 3 선택된 상태)

i=2 : 1 << i : 0000 0001 => 0000 0100

선택 여부 비교 : mask & 1 << 2

0000 1010

& 0000 0100  <= 2번째 빼고 모두 0

결과적으로 mask 의 2(i) 번째 자리가 1 이면 전체 연산 결과는 0 이 아닌 어떤 수,

2(i) 번째 자리가 0 이면 전체 연산 결과는 0 이 된다.

 

| 연산

mask 에 표현 선택(1), 비선택(0) 표현에 i 번째 자리를 선택 (1) 바꾸는 처리

mask : 0000 1010 (두번째, 네번째 사용 중 index 중 1, 3 선택된 상태)

i=2 : 1 << i : 0000 0001 => 0000 0100

mask 에 선택 처리 : mask | 1 << 2

0000 1010

0000 0100  <= 2번째 빼고 모두 0  i 번째 자리를 빼고 나머진 변경 X, i 자리만 1이로 결과는

 mask 의 나머지 자리는 그대로 i 자리는 무조건 1 로 변경

 

3) 바이너리 카운팅

셀렉트 배열 부담되어서 대체하는 효과

index하나가

 

1.1. Ch16 그리디

1) 그리디

• 항상 최적의 해 탐색

 

2. 실습

1) 분할 정복 알고리즘

package basic.Ch13_DivideNConquer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 반복문
public class DivideNConquer {
    static int N, r, c, ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        // 풀이
        N = (int) Math.pow(2, N); // 2의 제곱수이므로 계속 반으로 나눌 수 있다.

        // 원점 초기화
        int y = 0;
        int x = 0;

        while( true ) {

            if( N == 1 ) break;


            N /= 2;

            // r,c 가 4개의 영역 중 어디에 있는 지 판단
            if( r < y + N && c < x + N ) { // 상좌
                ;
            }else if( r < y && c >= x + N ) { // 상우
                ans += N * N * 1;
                x += N; // 원점 우로 이동
            }else if( r >= y + N && c < x + N ) { // 하좌
                ans += N * N * 2;
                y += N; // 원점 하로 이동
            }else {
                ans += N * N * 3;
                y += N; // 원점 하로 이동
                x += N; // 원점 우로 이동
            }
        }

        System.out.println(ans);
    }
}

https://www.acmicpc.net/problem/1074

---

package basic.Ch13_DivideNConquer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class G5_2447_Star {
    static char[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        arr = new char[N][N];

        //전부 별
        for (char[] star : arr) Arrays.fill(star, '*');

        //빈칸 뚫기
        star(N,0,0);

        //결과 출력
        for (char[] star : arr) {
            sb.append(star).append("\n");
        }
        System.out.println(sb);
    }

    public static void star(int N, int y, int x) {
        if(N == 1) return;

        //공백 삽입
        for (int i = y+(N/3); i < y+(N/3*2); i++) {
            for (int j = x+(N/3); j < x+(N/3*2); j++) {
                arr[i][j] = ' ';
            }
        }

        //분할 정복
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3 ; j++) {
                star(N/3, y+(i*N/3), x+(j*N/3));
            }
        }
    }
}

https://www.acmicpc.net/problem/2447

 

2) 그리디 알고리즘

package basic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G5_1074_Z {
    static int result = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //입력
        int N = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        //배열 크기와 r,c를 인자로 넣음
        func((int)Math.pow(2, N), r, c);
        System.out.println(result);
    }

    public static void func(int size, int r, int c){
        //크기가 1이면 return
        if(size == 1) return;

        //아니면 4분할
        if(r < size/2 && c < size/2){ //2사분면에 속하면
            func(size/2, r, c);

        }else if(r < size/2 && c >= size/2){ //1사분면에 속하면
            result += size * size/4;
            func(size/2, r, c-size/2);

        }else if(r >= size/2 && c < size/2) { //3사분면에 속하면
            result += (size * size/4) * 2;
            func(size/2, r - size/2, c);

        }else { //4사분면에 속하면
            result += (size * size/4) * 3;
            func(size/2, r-size/2, c-size/2);
        }
    }
}

https://www.acmicpc.net/problem/2839

 

3. WorkShop

1) 별찍기 - 10

별찍기 분할 정복 발표하려고 합니다

 

4.  마무리

1) 더 공부할 것

• 비트 마스크 연산 진짜 모르겠다
• StringBulider