Tech Log 🛠️

문제

분석

사실 이 문제를 굉장히 단순 무식하게 풀었다.

대략 문제의 조건을 요약하면

1.  중간에 파티션(X)이 존재한다면 거리 두기를 지킨 것이다.

2. 파티션을 사이에 두고 앉은 경우도 거리 두기를 지킨것이다. (옆에 빈 테이블이 있으면 안됨)

으로 요약 가능하다.

생각해보면, 

1번 조건은 파티션이 나오면 해당 라인은 더 이상 탐색할 필요가 없는 것이다.

2번 조건에서는 P(참가자) 옆에 공석(O)이 있으면 안된다. 

라고 해석할 수 있다.

이제 알고리즘을 짜보자 

탐색을 할 때는 세가지 경우가 있다.

1. 파티션(X)이 나오는 경우 

     - 더 이상 볼 필요 없음 skip

2. 참가자(P)가 나오는 경우

    - 무조건 안됨

3. 공석(O)이 나오는 경우

    - 이건 좀 더 탐색할 필요가 있다.

      주변에 참가자(P) 가 있는 지 확인해 보자

이런 메커니즘으로 풀면 문제를 효율적으로 해결할 수 있다.

근데 난 상하좌우 대각선 까지 일일이 탐색해주었다 ㅎㅎ...

코드

import java.util.*;

class Solution {
    
    static int[] dx = {1,2,-1,-2,0,0,0,0,-1,-1,1,1};
    static int[] dy = {0,0,0,0,1,2,-1,-2,-1,1,-1,1};
    static List<Integer> answer_ = new ArrayList<>();
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i=0;i<5;i++){
            visit(places[i]);
            if(visit(places[i]) == true){
                answer_.add(1);
            }
            else {
                answer_.add(0);
            }
        }
        
        for(int i=0;i<5;i++){
            answer[i] = answer_.get(i);
        }
        
        return answer;
    }
    
    static boolean visit(String[] places){
        for(int j=0;j<5;j++){
                for(int k=0;k<5;k++){
                    if(places[j].charAt(k) == 'P'){
                        check(j,k,places);
                        if(check(j,k,places) == false){
                            return false;
                        }
                    }    
                }
            }    
        return true;
    }
    
    static boolean check(int y,int x,String[] places){
        for(int i=0;i<=7;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break; 
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        
        for(int i=2;i<=3;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        for(int i=4;i<=5;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        for(int i=6;i<=7;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X') break;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P') return false;
        }
        for(int i=8;i<=11;i++){
            if(y+dy[i] < 0 || y+dy[i] > 4 || x+dx[i] < 0 || x+dx[i] > 4) continue;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'X' || places[y+dy[i]].charAt(x+dx[i]) == 'O') 
                continue;
            if(places[y+dy[i]].charAt(x+dx[i]) == 'P'){
                
                
              if(places[y+dy[i]].charAt(x) == 'X' && places[y].charAt(x+dx[i]) == 'X') {
                  continue;
                }
                else return false;
                }
            
            }  
        return true;
        }
        
    
    }

투포인터 알고리즘 

- 리스트에 순차적으로 접근해야 할 때 두 개의 점(시작점 , 끝점)의 위치를 기록하면서 처리하는 알고리즘이다.

- 시작점과 끝점으로 접근할 데이터의 범위를 표현할 수 있다.

예를 들어, 해당 수열에서 합이 5인 부분 수열의 개수를 찾는다고 생각해보자

완전 탐색으로 문제를 해결할 수도 있지만 너무 많은 시간이 걸린다는 단점이 있다.

따라서 이때 투포인터 알고리즘을 이용하여 문제를 해결할 수 있다.

투포인터 알고리즘의 방식은 다음과 같다.

1. 처음에는 시작점과 끝점 모두 0에서 시작한다.

2. 합이 목표값과 같으면 카운트한다.

3. 만약 목표값보다 부분수열의 합이 작다면 end 인덱스를 1 증가시킨다.

3-1. 현재 부분 수열의 값은 3이므로 end 인덱스를 1만큼 더 증가시킬 수 있다. 

         그렇게되면 부분 수열의 값은 6이 된다.

4. 만약 목표값보다 부분수열의 합이 크다면 start 인덱스를 1만큼 증가시킨다.

5. 모든 경우를 확인 할때까지 2~4 과정을 반복한다.

이렇게 함으로써 합이 5가 되는 부분 수열을 모두 구할 수 있다 !

프로그래머스 - 연속된 부분 수열의 합

투 포인터를 활용하여 풀 수 있는 대표적인 문제이다

분석

합이 k 가 되는 부분 수열의 시작 인덱스와 마지막 인덱스를 구해야 한다.

따라서 투포인터 알고리즘을 이용하면 모든 경우를 구할 수 있다.

그리고 인덱스의 길이를 비교해서 가장 최소 일 때를 반환해주면 된다.

코드

class Solution {
    
    public int[] solution(int[] sequence, int k) {
        int min = Integer.MAX_VALUE;
        int end = 0;
        int num = sequence.length;
        int sum = 0;
        int[] answer = new int[2];
        
        for(int start=0;start<num;start++){
            while(sum < k && end < num){
                sum += sequence[end];
                end ++;
            }
            
            if(sum == k && min > (end-1) - start) {
                min = (end-1) - start;
                answer[0] = start;
                answer[1] = end-1;
            }
            
            sum -= sequence[start];
        }
        
        return answer;
    }
}

"이것이 취업을 위한 코딩 테스트다 with 파이썬" 내용을 기반으로 제작하였습니다.

https://www.youtube.com/watch?v=ttLRltNDiCo

"이것이 취업을 위한 코딩 테스트다 with 파이썬" 내용을 기반으로 제작하였습니다.

(https://www.youtube.com/watch?v=KGyK-pNvWos&t=2349s)

정렬이란?

- 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다.

- 문제에 따라 적절한 정렬 알고리즘이 사용된다.

위와 같이 정렬되지 않은 수열을 정렬하려면 어떻게 해야될까 ?

정렬 알고리즘에는 크게 4가지가 있다.

1. 선택 정렬 

     - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

첫번째 단계에서는 0이 제일 작으므로 0과 7을 교환한다.

두번째 단계에서는 1이 제일  작으므로 5와 교환한다.

이렇게 단계를 진행해나가다 보면 결국 0부터 9까지 정렬이 된다.

시간복잡도 : O(N^2)

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
            for(int i=0;i<arr.length;i++){
                int min_idx = i;
                for(int j=i+1;j<arr.length;j++){
                    if(arr[min_idx] > arr[j]){
                        min_idx = j;
                    }
                }
                int temp = arr[i];
                arr[i] = arr[min_idx];
                arr[min_idx] = temp;
            }
        for (int num : arr) {
            System.out.print(num+" ");
        }
        }

}

2. 삽입 정렬

     - 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

     - 선택 정렬보다 더 효율적으로 동작한다.

첫번째 단계에서는 5의 위치를 결정한다. 7의 오른쪽 or 왼쪽으로 가게 되는데 7보다 작기 때문에 7의 왼쪽으로 이동한다.

두번째 단계에서는 9의 위치를 정한다. 하지만 앞에 있는 두 개의 숫자보다 9가 더 크므로 위치를 변경하지 않는다.
(정확히는 바로 앞에 7보다 커서 바로 정렬을 멈춘다,)

이런식으로 정렬을 진행하면 0부터 9까지 정렬이 된다.

시간 복잡도: O(N^2)

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
            for(int i=1;i<arr.length;i++){
                for(int j=i;j>0;j--){
                    if(arr[j-1] > arr[j]){
                        int temp = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = temp;
                    }
                    else break;
                }

            }
        for (int num : arr) {
            System.out.print(num+" ");
        }
        }

}

3. 퀵 정렬

     - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 변경

     - 프로그래밍 언어의 정렬 라이브러리의 근간

     - 보통 첫 번째 데이터를 기준(pivot)으로 한다.

첫번째 단계에서는 5를 기준으로 한다. 

그렇다면 왼쪽에서부터 7은 5보다 크기에 선택되고 , 오른쪽에서부터의 4는 5보다 작기에 선택된다.

이제 둘의 위치를 바꾼다.

이제 쪽에서부터 9는 5보다 크기에 선택되고 , 오른쪽에서부터의 2는 5보다 작기에 선택된다.

다시 둘의 위치를 바꾼다.

이렇게 진행하다보면 데이터의 위치가 엇갈리는 순간이 올것이다.

그때 작은 데이터와 피벗값의 위치를 변경한다

이렇게 되면 왼쪽 데이터는 5보다 작고 , 오른쪽 데이터는 5보다 크다.

이처럼 피벗을 기준으로 데이터를 나누는 것을 분할이라고 한다.

앞에서 진행했던 것처럼 분할된 데이터에서 다시 퀵정렬을 적용하면 된다.

시간복잡도 : 일반적으로 O(NlogN) , 최악의 경우 O(N^2)

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        quickSort(arr,0,arr.length-1);
        for (int num : arr) {
            System.out.print(num+" ");
        }
        }

        public static void quickSort(int[] arr,int start,int end){
            if(start >= end) return;

            int pivot = start;
            int left = start+1;
            int right = end;

            while (left <= right){
                while (left <= end && arr[left] <= arr[pivot]) left++;
                while(right > start && arr[right] >= arr[pivot]) right--;

                if(left > right){
                    int temp = arr[pivot];
                    arr[pivot] = arr[right];
                    arr[right] = temp;
                }
                else{
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            }
            quickSort(arr,start,right-1);
            quickSort(arr,right+1,end);
        }

}

4. 계수 정렬

    - 특정한 조건이 부합할 때만 매우 빠르게 동작한다.

    - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 가능하다.

먼저 크기가 0 인 배열을 만들어준다.

만약 이런 배열이 있다면 각각의 데이터가 나오는 숫자를 카운팅하고 배열에 집어 넣는 다면 효과적일 것이다.

먼저 만든 0 배열에 적용시켜보자

숫자들이 등장한 횟수만큼 배열에 플러스를 해주어 넣어주었다.

이제 이것을 그대로 출력해주면 된다.

이 알고리즘은 최악의 경우에도 O(N+K)를 보장하지만 경우에 따라선 최악의 효율을 낼 수도 있다.

ex) 0과 9밖에 데이터가 없는 경우에는 데이터가 두 개밖에 없는 데 크기가 10인 배열을 만들어서 정렬해야한다.

따라서, 동일한 값이 여러개일 경우 효과적으로 작동할 수 있다.

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        int[] sort = new int[arr.length+1];

        for(int i=0;i<arr.length;i++){
            sort[arr[i]] ++;
        }

        for(int i=0;i<sort.length;i++){
            for(int j=0;j<sort[i];j++){
                System.out.print(i+" ");
            }
        }
        }

}

분석

해당 문제는 백트래킹 , 비트마스킹 두 가지 방법으로 풀 수 있습니다.

1. 비트마스킹

비트 마스킹이란?

불리언 배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색 , 수정 등의 작업을 하는 것을 말합니다

- 큰돌의 터전 유튜브

더 자세한 사항은 이전에 블로그에 정리해 놓은 내용을 참고해주세요 

https://cb036133.tistory.com/91

static void dfs() {
    for (int i = 0; i < (1 << num) ; i++) {
        int cnt = 0;
        team = new boolean[num];
        for (int j = 0; j < num; j++) {
            if ((i & (1 << j)) != 0) {
                team[j] = true;
                cnt++;
            }
        }
        if (cnt == num / 2) cal();


    }
}

저는 비트마스킹을 이용해서 팀의 수가 반반이 되면 각 팀의 능력치 합을 빼주는 식으로 코드를 구성하였습니다.

2. 백트래킹

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

dfs를 이용하여 백트레킹을 구현할 수 있습니다.

static void dfs(int idx,int depth) {
        if (depth == num / 2) {
            cal();
            return;
        } else {
            for (int i = idx; i < num; i++) {
                if (check[i] == false) {
                    check[i] = true;
                    dfs(i+1,depth + 1);
                    check[i] = false;
                }
            }
        }
    }

코드 - 비트마스킹

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


public class Main {
    static int num;
    static int[][] arr;
    static boolean[] team;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        num = Integer.parseInt(br.readLine());
        arr = new int[num][num];
        team = new boolean[num];

        for (int i = 0; i < num; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < num; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs();

        System.out.println(min);
    }

    static void dfs() {
        for (int i = 0; i < (1 << num) ; i++) {
            int cnt = 0;
            team = new boolean[num];
            for (int j = 0; j < num; j++) {
                if ((i & (1 << j)) != 0) {
                    team[j] = true;
                    cnt++;
                }
            }
            if (cnt == num / 2) cal();


        }
    }

    static void cal() {
        int num1 = 0;
        int num2 = 0;

        for(int i=0;i<num-1;i++){
            for(int j=i+1;j<num;j++){
                if(team[i] == true & team[j] == true){
                    num1 += arr[i][j];
                    num1 += arr[j][i];
                }
                if(team[i] == false & team[j] == false){
                    num2 += arr[i][j];
                    num2 += arr[j][i];
                }
            }

        }


        int result = Math.abs(num1-num2);

        if(result == 0){
            System.out.println(0);
            System.exit(0);
        }

        if(min > result) min = result;
    }

}

코드 - 백트래킹

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

import static java.lang.Math.abs;

public class Main {
    static int[][] arr;
    static boolean[] check;
    static int num;
    static int result=Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
        check = new boolean[num];
        arr = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        dfs(0,0);
        System.out.println(result);
    }

    static void dfs(int idx,int depth) {
        if (depth == num / 2) {
            cal();
            return;
        } else {
            for (int i = idx; i < num; i++) {
                if (check[i] == false) {
                    check[i] = true;
                    dfs(i+1,depth + 1);
                    check[i] = false;
                }
            }
        }
    }

    static void cal() {
        int num1 = 0;
        int num2 = 0;

        for (int i = 0; i < num-1; i++) {
            for(int j= i+1;j<num;j++) {
                if (check[i] == true & check[j] == true) {
                    num1 += arr[i][j];
                    num1 += arr[j][i];
                }
                else if (check[i] == false & check[j] == false) {
                    num2 += arr[i][j];
                    num2 += arr[j][i];
                }
            }
        }
        int val = abs(num1 - num2);
        if(val == 0){
            System.out.println(0);
            System.exit(0);
        }

        result = Math.min(result,val);
    }
}

분석

이 문제를 풀려면 트리 자료구조와 트리의 순환에 대해 알아야한다.

트리란?

가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다.

루트노드 :  부모가 없는 최상위 노드 (F)단말노드 : 자식이 없는 노드 (A,C,E,H)크기 : 트리에 포함 된 노드의 개수 (8)깊이 : 깊이 루트 노드부터의 거리높이 :  깊이 중 최댓값 (3)차수 : 각 노드의 간선 개수

* 트리의 크기가 N 일때, 전체 간선의 개수는 N-1 이다.

트리의 순회 

트리 자료구조에 포함 된 노드를 특정한 방법으로 한번씩 방문하는 방법이다.

대표적인 순회의 방법은 3가지가 있다.

1. 전위 순회 : 루트노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 방문한다.

                       F B A D C E G I H

2. 중위 순회 :  왼쪽 자식노드 -> 루트 노드 -> 오른쪽 자식 노드

                       A B C D E F G H I

3. 후위 순회 :  왼쪽 자식노드 -> 오른쪽 자식 노드 -> 루트 노드

                       A C E D B H I G F

위의 방법을 적용해서 입력으로 노드간 연결 정보를 받은 뒤에 순회 결과를 출력하면 된다.

코드

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


public class Main {
    //최상위 루트 노드 생성
    static Node root = new Node('A',null,null);
    //트리에 들어갈 노드 클래스
    static class Node{
        char name;
        Node left;
        Node right;

        public Node(char name, Node left, Node right) {
            this.name = name;
            this.left = left;
            this.right = right;
        }
    }

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

        int num = Integer.parseInt(br.readLine());

        for(int i=0;i<num;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            InsertNode(root,st.nextToken().charAt(0),st.nextToken().charAt(0),st.nextToken().charAt(0));
        }

        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
    }

    private static void InsertNode(Node root, char value, char left, char right) {
        //현재 노드와 value 의 값이 같다면
        if(root.name == value){
            root.left = (left == '.' ? null : new Node(left,null,null));
            root.right = (right == '.' ? null : new Node(right,null,null));
        }

        else{
            //왼쪽 자식노드가 존재한다면 해당 노드 탐색 후 자식 노드 추가
            if(root.left != null) InsertNode(root.left,value,left,right);
            //오른쪽 자식노드가 존재한다면 해당 노드 탐색 후 자식 노드 추가
            if(root.right != null) InsertNode(root.right,value,left,right);
        }
    }
    //전위 순회
    static void preOrder(Node node){
        if(node == null) return;
        System.out.print(node.name+" ");
        preOrder(node.left);
        preOrder(node.right);
    }
    //중위 순회
    static void inOrder(Node node){
        if(node == null) return;
        inOrder(node.left);
        System.out.print(node.name+" ");
        inOrder(node.right);
    }
    //후위 순회
    static void postOrder(Node node){
        if(node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.name+" ");
    }


}

참고 사이트

https://www.youtube.com/watch?v=i5yHkP1jQmo&t=470s 

https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-1991%EB%B2%88

분석

비트마스킹을 이용하여 푸는 문제이다.

비트마스킹이란?

- 컴퓨터는 모든 자료를 이진수로 표현하는데, 이를 이용하여 자료구조로 쓰는 기법이다.

  비트마스킹을 통해 스위치,방문 처리 등 다양한 문제를 해결할 수 있다.

비트연산자의 종류

- 비트마스크의 상태를 변경시키기 위해 다양한 비트 연산자를 활용할 수 있다.

1.  a | b

    - a의 모든 비트와 b의 모든 비트를 OR 연산을 수행한다.

    ex) a=1 , b=1 일때 a | b = 1

          a=1 , b=0 일때 a | b = 1

          a=0 , b=0 일때 a | b = 0

2.  a & b

    - a의 모든 비트와 b의 모든 비트를 AND 연산을 수행한다.

    ex) a=1 , b=1 일때 a & b = 1

          a=1 , b=0 일때 a & b = 0

          a=0 , b=0 일때 a & b = 0

3.  a ^ b

     - a의 모든 비트와 b의 모든 비트를 XOR 연산을 수행한다. (다르면 1 , 같으면 0)

    ex) a=1 , b=1 일때 a ^ b = 0

          a=1 , b=0 일때 a ^ b = 1

          a=0 , b=0 일때 a ^ b = 0

4.  ~a

      - a의 모든 비트에 NOT 연산을 한다.

5.  a << b OR a >> b

       - a의 비트를 왼쪽(오른쪽)으로 b만큼 쉬프트한다.

         ex) 1 << 2 : 2의 2승

               1 << 0 : 2의 0승 

위의 연산자들을 응용하여 더 다양한 연산을 수행할 수 있다.

1.idx번째 비트 켜기

   S |= (1<<idx)

2. idx번째 비트 끄기 

    S &= ~(1<<idx)

3. idx에 대한 XOR 연산

    S ^= (1<<idx)

4. 최하위 켜져있는 idx 찾기

     idx = (S & -S)

     * -S = (~S+1) 의 특성을 가지기 때문에 가능하다.

      ex ) S = 1010 , ~S = 0101

             -S = 0101 + 1

                  = 0110

              S & -S = 2(마지막 인덱스)

5. n인 모든 집합의 비트 켜기

     (1<<n) - 1

6. idx번째 비트가 있는 지 확인하기

    if(S & (1 << idx)) 

이 개념들을 숙지하면 위의 문제를 풀 수 있다 !

코드

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

import static java.lang.Math.abs;

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int bit=0;
        for(int i=0;i<num;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int seq=0;

            switch (st.nextToken()){
                case "add":
                   seq = Integer.parseInt(st.nextToken());
                   bit |= (1<<(seq-1));
                   break;
                case "remove":
                    seq = Integer.parseInt(st.nextToken());
                    bit &= ~(1<<(seq-1));
                    break;
                case "check":
                    seq = Integer.parseInt(st.nextToken());
                    sb.append((bit & (1<<(seq-1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle":
                    seq = Integer.parseInt(st.nextToken());
                    bit ^= (1 << (seq-1));
                    break;
                case "all":
                    bit |= (~0);
                    break;
                case "empty":
                    bit &= 0;
                    break;
            }
        }
        System.out.println(sb);
    }


}

비트마스킹 문제를 마지막으로 골드를 달성하였다 !

비록 중간에 다른 사람꺼 참고한 코드도 있고 쉬운 문제들도 많이 풀었지만 어찌됐건 골드까지 오게되었다

이제 플레티넘을 목표로 더 열심히 풀어야겠다 ㅎㅎ

분석

이 문제를 풀려면 bfs와 dfs에 대해서 먼저 알아야한다.

dfs, bfs는 그래프를 탐색할 때 사용하는 알고리즘인데, 구현 방식이 다르므로 목적에 따라 다른 알고리즘이 사용된다.

(*그래프 : 노드와 간선으로 이루어진 자료구조의 일종)

깊이 우선 탐색(bfs)

- 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방식을 말한다.

  스택 , 재귀함수로 구현이 가능하지만 재귀함수로 구현하면 좀 더 간략한 코드가 나온다.

  모든 노드를 방문해야하거나 , 그래프가 큰 경우 사용

너비 우선 탐색(bfs)

- 인접한 노드를 먼저 탐색하는 방식을 말한다. 

  가까운 노드를 먼저 방문하고 멀리있는 노드를 나중에 방문한다.

  큐로 구현할 수 있다.

  최단 경로를 구할 경우 사용

코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int node, line, start;
    static int[][] arr;
    static boolean[] visit;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        visit = new boolean[node + 1];
        arr = new int[node + 1][node + 1];

        for (int i = 0; i < line; i++) {
            StringTokenizer str  = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }


        dfs(start);
        visit = new boolean[node + 1];
        sb.append("\n");
        bfs(start);
        System.out.println(sb);
    }

    static void dfs(int start) {
        sb.append(start + " ");
        visit[start] = true;
        for (int i = 1; i <= node; i++) {
            if (arr[start][i] == 1 && !visit[i]) {
                dfs(i);
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        visit[start] = true;

        while(!q.isEmpty()){
            int value = q.poll();
            sb.append(value+" ");

            for(int i=1;i<=node;i++){
                if(arr[value][i] == 1 && !visit[i]){
                    visit[i] = true;
                    q.add(i);
                }
            }

        }
    }


}

분석

완전탐색 문제이다.

처음부터 끝까지 비교해가면서 무식하게 답을 찾는 수 밖에는 없다..

인접한 사탕의 색이 다를 경우 위치를 변경한다고 하였지만 그 코드를 짜는 거 자체가 더 비효율적이기 때문에

모든 사탕의 위치를 바꾸면서 비교해가는 방식으로 해결하였다.

그리고 사탕을 바꾸는 경우의 수는 

1. 옆자리끼리 바꾸기

2. 위아래로 바꾸기

이렇게 두가지 경우가 있어서 두 경우 모두 비교를 해주었다.

사탕의 길이를 구하는 경우 또한 두가지가 있는데

1. 가로줄로 사탕으로 먹는 경우

2. 세로 줄로 사탕을 먹는 경우

이 두 가지 경우를 사탕의 자리를 바꿀 때마다 각각 비교해주면 된다 !

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int num;
    static char[][] board;
    static int max = 0;

    public static void find_row() {
        int cnt = 1;
        for (int i = 0; i < num; i++) {
            cnt = 1;
            for (int j = 0; j < num-1; j++) {
                if (board[i][j] == board[i][j + 1]) {
                    cnt++;
                } else {
                    cnt = 1;
                }
                if (max < cnt) max = cnt;

            }

        }
    }

    public static void find_column() {
        int cnt = 1;
        for (int i = 0; i < num; i++) {
            cnt = 1;
            for (int j = 0; j < num-1; j++) {
                if (board[j][i] == board[j+1][i]) {
                    cnt++;
                } else {
                    cnt = 1;
                }
                if (max < cnt) max = cnt;

            }

        }

    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
        board = new char[num][num];

        for (int i = 0; i < num; i++) {
            String str = sc.next();
            for (int j = 0; j < num; j++) {
                board[i][j] = str.charAt(j);
            }
        }
        char value;
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num-1; j++) {
                value = board[i][j];
                board[i][j] = board[i][j + 1];
                board[i][j + 1] = value;

                find_row();
                find_column();

                value = board[i][j];
                board[i][j] = board[i][j + 1];
                board[i][j + 1] = value;

            }

        }
        for (int i = 0; i < num-1; i++) {
            for (int j = 0; j < num; j++) {
                value = board[i][j];
                board[i][j] = board[i+1][j];
                board[i+1][j] = value;

                find_row();
                find_column();

                value = board[i][j];
                board[i][j] = board[i+1][j];
                board[i+1][j] = value;

            }

        }
        System.out.println(max);
    }
}

분석

일단 포도주를 3개라고 가정해보자

포도주를 제일 많이 마시는 경우의 수는

1. 첫 번째 , 두 번째 포도주를 마시는 경우

2. 세 번째 , 첫 번째 포도주를 마시는 경우

3. 세 번째 , 두 번째 포도주를 마시는 경우

크게 3가지가 나올 수 있다.

이렇게 생각하면 다음과 같은 점화식을 세울 수 있다.

dp[num] = max(max(dp[num - 3] + value[num - 1] + value[num], dp[num - 2] + value[num]),dp[num-1]);

3가지 경우의 수를 비교해주면 된다 !

코드

import java.util.Arrays;
import java.util.Scanner;

import static java.lang.Math.max;


public class Main {

    static long[] dp;
    static long[] value;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        value = new long[10001];
        dp = new long[10001];
        for (int i = 1; i <= num; i++) {
            value[i] = sc.nextInt();
        }
        dp[0] = 0;
        dp[1] = value[1];
        dp[2] = value[2] + value[1];
        if (num == 2) {
            System.out.println(dp[2]);
            return;
        }
        for (int i = 3; i <= num; i++) {
            dp(i);
        }
        System.out.println(dp[num]);


    }

    static void dp(int num) {
        dp[num] = max(max(dp[num - 3] + value[num - 1] + value[num], dp[num - 2] + value[num]),dp[num-1]);
    }

}