BangBang's Devlogs

https://programmers.co.kr/learn/courses/30/lessons/43104#qna

동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함

이 과정을 통해 점화식을 세우는게 중요함

그리고 메모제이션을 해서 시간을 줄이는게 중요함
=>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로

메모제이션 방법으로는 아래와 같은 방법이 있음 
1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 (BOTTOM-UP)
2. 그 순간 필요하면 계산해서 저장하는 방법(TOP-DOWN)

해결 방안

1. 위의 그림을 통해 정사각형 한변의 길이는 N=1일 때 1, N=2일 때 1, N=3일 때 2와 같은 결과를 알 수 있고 이를 점화식으로 표현하게 되면 (N 번째 정사각형 한 변의 길이) = (N-2 번째 정사각형 한 변의 길이) + (N-1 번째 정사각형 한 변의 길이)가 됨

2. 이와 같은 점화식을 이용하여 input으로 주어진 1~N 번째까지의 정사각형 한 변의 길이를 구하고 메모제이션함
이때 메모제이션 방법으로는 반복문을 이용하여 미리 값을 계산해주는 BOTTOM-UP 방식을 이용함

3. n번째 정사각형까지 메모제이션한 data 배열을 이용하여 직사각형의 둘레를 구하는 방정식을 구하고 그에 값을 대입함
=> answer = 4*data[N] + 2*data[N-1]

코드

// 타일 장식물
class Solution {

    public long solution(int N) {
        long answer = 0;
        long[] data = new long[N+1];
        
        // dp(1)=1
        // dp(2)=1
        // dp(N)= dp(N-2) + dp(N-1)
        data[1] = 1;
        data[2] = 1;
        for(int i=3; i<data.length; i++){
            data[i] = data[i-2] + data[i-1];
        }
        
        // N개의 타일로 구성된 직사각형 둘레 : 4*data[N] + 2*data[N-1]
        answer = 4*data[N] + 2*data[N-1];
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42839

재귀호출을 이용하여 완전탐색하였음

해결 방안

1. 주어진 Numbers를 이용하여 만들 수 있는 전체 숫자의 경우를 구함
이 때, 만들어지는 숫자는 순열로 1~N자리의 숫자를 생성할 수 있으므로 nP1 ~ nPn 까지의 전체 숫자를 구해줌

2. 전체의 숫자를 구하면서 nPr의 r만큼의 숫자가 누적되어 만들어지면 중복 판단 및 소수 판단을 하고 소수이면 answer++을 해줌
소수 판단은 아리스토테네스의 체 방법을 이용하여 구현함

코드

import java.util.*;

// 소수 찾기
class Solution {
    // 소수 갯수
    public static int answer;
    // 중복되지 않는 전체 숫자 저장
    public static Set<Integer> totalNumbers; 
    
    public int solution(String numbers) {
        answer = 0;
        
        totalNumbers = new HashSet<>();
        int[] numbersArr = new int[numbers.length()];
        boolean[] usedNumbers = new boolean[numbers.length()];
        
        for(int i=0; i<numbersArr.length; i++){
            numbersArr[i] = Integer.parseInt(numbers.charAt(i) + "");
            usedNumbers[i] = false;
        }
        
        // 전체 숫자의 경우 구하기 (nP1 ... ~ nPn)
        // r : 1 ~ n
        for(int r=1; r<=numbersArr.length; r++){
            getResult(numbersArr, usedNumbers, "", r, 0);
        }
        
        return answer;
    }
    
    public static void getResult(int[] numbersArr, boolean[] usedNumbers, String num, int r, int current){
        
        // current번째 for문
        if(current >= r){
            // 숫자를 totalNumbers에서 있는지 Integer형으로 찾아봄(중복 확인)
            // 없으면 저장하고 숫자가 소수인지 판단
            if(!totalNumbers.contains(Integer.parseInt(num))){
                totalNumbers.add(Integer.parseInt(num));
                
                // 소수 판단
                if(isPrime(Integer.parseInt(num))){
                    answer++;
                    //System.out.println(num);
                }
                    
            }
            return;
            
        }
        else{
            for(int i=0; i<numbersArr.length; i++){
                //System.out.println(current+ ": " + i + ", " + numbersArr[i] );
                if(!usedNumbers[i]){
                    num += Integer.toString(numbersArr[i]);
                    usedNumbers[i] = true;
                    getResult(numbersArr, usedNumbers, num, r, current+1);
                    usedNumbers[i] = false;
                    num = num.substring(0, num.length()-1);
                }
                
            }
        }
    }
    
    public static boolean isPrime(int num){
		int sqrt = (int) Math.sqrt(num);

		// 2는 유일한 짝수 소수
		if (num == 2)
			return true;

		// 짝수와 1은 소수가 아님
		if (num % 2 == 0 || num == 1)
			return false;

		// 제곱근까지만 홀수로 나눠보면 됨
		for (int i = 3; i <= sqrt; i += 2) {
			if (num % i == 0)
				return false;
		}

		return true;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43164#

DFS로 구현함

해결 방안

1. DFS를 이용하여 전체 여행 경로의 경우를 구하며 한가지의 경로를 String형의 route에 누적한 뒤 한가지 경로가 다 누적되면 routes에 추가함
=> 나중에 정렬을 쉽게 이용하기 위하여 String 값으로 저장

2. 목적지가 2가지 이상일 경우 알파벳 순이 되어야하므로 sort 정렬을 이용하여 routes를 정렬함

3. 정렬된 routes.get(0)이 답이 되고 String 값으로 저장하였으므로 answer의 String[] 형식에 맞게 파싱하여 저장해줌

코드

import java.util.*;
// 여행 경로
class Solution {
    public static String[] answer;
    public static String route;
    public static List<String> routes;
    public static boolean[] used;
    
    public static void dfs(String[][] tickets, String departure, String destination, int index){
        route += (destination + " ");
        
        if(index == tickets.length){
        	routes.add(route);
            //System.out.println(route);
            return;
        }

        // 도착지가 출발지가 되고 출발지인 모든 경우 DFS
        String start = destination;
        String nextDeparture;
        String nextDestination;
        for(int i=0; i<tickets.length; i++){
            nextDeparture = tickets[i][0];
            nextDestination = tickets[i][1];

            if(start.equals(nextDeparture) && used[i] == false){
                used[i] = true;
                dfs(tickets, nextDeparture, nextDestination, index+1);
                used[i] = false;
                // 전 단계로 초기화
                route = route.substring(0, route.length()-4);
            }
        }
            
        
    }
    
    public String[] solution(String[][] tickets) {
        System.out.println(tickets.length);
        answer = new String[tickets.length + 1];
        routes = new ArrayList<>();
        used = new boolean[tickets.length];
        
        for(int i=0; i<used.length; i++){
            used[i] = false;
        }
        
        String start = "ICN";
        String departure;
        String destination;
        for(int i=0; i<tickets.length; i++){
            departure = tickets[i][0];
            destination = tickets[i][1];
            
            // 첫 스타트가 ICN인 모든 경우 DFS 해서 routes에 저장
            if(start.equals(departure)){
                used[i] = true;
                route = departure + " ";
                dfs(tickets, departure, destination, 1);
                // dfs가 끝나고 나면 티켓은 다시 사용 안한 것으로 초기화
                used[i] = false;
            }
        }
        
        // 모든 경로 저장하고 String 오름차순
        Collections.sort(routes);
        
        //System.out.println("answer = " + routes.get(0));

        answer = routes.get(0).split(" ");
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java

문제 이해

문제의 예시를 보면 왼쪽의 그림은 네트워크가 2개인 경우이고 오른쪽의 그림은 네트워크가 1개인 경우임

즉, n개의 컴퓨터들이 있고 연결되어있는 컴퓨터들이 각각의 네트워크임

따라서 DFS를 통해 연결되어있는 컴퓨터들끼리 네트워크를 구성하므로 네트워크의 갯수를 구해주는 문제임 

해결 방안

1. solution() 에서 전체 컴퓨터들의 방문 여부를 따져주고 방문되지 않은 컴퓨터의 경우 dfs()를 통해 연결된 컴퓨터들을 방문됬다고 표시되면 하나의 네트워크가 구성된다. 하나의 네트워크가 구성되면 answer 값을 증가해줌 

2. dfs() 에서는 해당 방문 컴퓨터를 방문했다고 체크해주고 인접 컴퓨터를 돎
이 때 인접 컴퓨터 여부는 computers에 저장되있는 값을 이용함(1이면 인접 컴퓨터)
인접한 컴퓨터이면서 방문한적 없으면 dfs()를 해줌

코드

// 네트워크
class Solution {
    public static int answer = 0;
    public static boolean[] visited;
    
    public static void dfs(int start, int[][] computers){
        visited[start] = true;
        
        // 인접 노드 돌기
        for(int i=0; i<computers[start].length; i++){
            // 자기는 제외
            if(i==start)
                continue;
            // 인접한 노드 아니여도 제외
            if(computers[start][i] == 0)
                continue;
            // 인접한 노드 
            else{
                // 방문한 적 없으면 dfs
                if(visited[i] == false)
                    dfs(i, computers);
            }
        }
    }
    
    // n: vertex , computers: edge
    public int solution(int n, int[][] computers) {
        
        visited = new boolean[n];
        for(int i=0; i<visited.length; i++){
            visited[i] = false;
        }
        
        // i는 start
        for(int i=0; i<visited.length; i++){
            // 방문한 적이 없으면 dfs
            if(visited[i] == false){
                dfs(i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

해결 방안

1. number 배열의 숫자를 계속 빼거나 더하는 두 가지 경우로 나눠져서 DFS를 이용하여 풀었음

2. DFS index가 numbers.length 까지 오게 되면 numbers에 쌓인 값들을 다 더해 sum을 구하고 그 sum이 target과 같으면 answer를 ++ 해줌

코드

// 타겟 넘버
class Solution {
    public static int answer = 0;
    
    public static void dfs(int[] numbers, int target, int index){
        if(index == numbers.length){
            int sum = 0;
            
            for(int i=0; i<numbers.length; i++){
                sum += numbers[i];
            }
            if(sum == target)
                answer++;
        }
        // 더하거나 빼거나 두 경우
        else{
            numbers[index] *= 1;
            dfs(numbers, target, index+1);
            
            numbers[index] *= -1;
            dfs(numbers, target, index+1);
        }
    }
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0);
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43238?language=java

이분탐색을 응용하여 문제를 구현하였음

이분탐색 알고리즘 코드

int BinarySearch(int arr[], int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

해결 방안 제시에 앞서 이분 탐색을 이용하여 알고리즘을 구현할 때 위와 같은 코드를 이해하고 있으며 이 코드를 응용하여 구현하는 것이 좋음

해결 방안

1. 무엇(start, mid, end)을 이분 탐색할 것이고 어떤 걸(위의 BinarySearch 코드의 target) 비교하여 다음 탐색 구간을 정할지 먼저 찾음
=> 이분 탐색할 것: 심사를 받는데 걸리는 시간(mid)
=> 비교대상(target) : n(입국 심사를 기다리는 사람)

2. 심사를 받는데 최소로 걸리는 시간(answer)을 구하므로 심사를 받는데 걸리는 시간(mid)을 이분 탐색함

3. Input에서 비교 대상으로 n(입국 심사를 기다리는 사람)명이 주어지므로 n명을 target으로 정해 다음 탐색 구간을 정함

4. n과 비교하기위해 주어진 mid 시간동안 검사할 수 있는 사람 수(sum)을 구하는 알고리즘이 포함되어야함

5. answer를 구하기 위해 최소 시간을 찾아내야함

이분 탐색 알고리즘 코드와 해결 방안을 조합하여 구현하면 아래와 같은 코드가 될 수 있음

코드

import java.util.*;

// 입국심사
class Solution {
    public long solution(int n, int[] times) {
        // 모든 사람이 심사를 받는데 걸리는 시간의 최솟값
        long answer = Long.MAX_VALUE;
        
        Arrays.sort(times);
        
        long start, mid, end;
        start = 0;
        end = Long.MAX_VALUE;
        long sum;
        // 모든 사람이 심사 받는데 걸리는 시간 이분 탐색
        // mid : 심사를 받는데 주어진 시간
        // sum : 주어진 시간(mid)동안 심사를 받을 수 있는 사람 수 
        while(start <= end){
            
            mid = (start + end) / 2;
            
            sum = 0;
            // 주어진 시간동안 몇명 검사 할 수 있는지 누적합
            for(int i=0; i<times.length; i++){
                sum += mid / times[i];
                
                if(sum >= n)
                    break;
            }
            
            // 비교 대상(사람 수)
            // 검사 다 못할 때(시간 부족)
            if(n > sum){
                start = mid + 1;
            }
            // 검사 다 했을 때 (시간이 남음)
            // 최소 시간 찾아야함
            else{
                end = mid - 1;
                answer = Math.min(answer, mid);
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42746?language=java

Comparator 인터페이스에 대한 지식이 있어야 문제를 쉽게 접근 가능할 수 있을 것이라고 생각함
정렬을 위한 인터페이스로 Comparable과 Comparator가 있는데 Comparable 인터페이스는 보통 객체의 기본적이고 고정된 정렬을 위해 사용하며 Comparator 인터페이스는 기본 정렬 기준과 다르게 정렬하고 싶을 때 사용함

해결 방안

1. numbers 1차원 int 배열 크기만큼 sNumbers 1차원 String 배열을 만들고 int 값들을 String 값들로 저장해줌

2. 위의 코드 처럼 sNumbers 배열을 정렬해주는데 정수들을 붙여서 만들었을 때 크게 만들 수 있도록 내림차순으로 정렬해줌
=> 나중에 다 이어 붙일 것이므로 내림차순 정렬 

3. sNumbers 배열들을 순서대로 다 이어 붙여줌

4. numbers 배열에 {0,0,0} 과 같이 0 값들만 가진 배열이 있을 수 있으므로 sNumbers 배열의 값들을 전부 이어 붙인 answer이 0으로 시작하면 "0"을 저장해줌

코드

import java.util.*;
// 가장 큰 수
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        String[] sNumbers = new String[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            sNumbers[i] = numbers[i] + "";
        }
        
        Arrays.sort(sNumbers, new Comparator<String>(){   
            @Override
            public int compare(String n1, String n2){
                // 더해서 큰 값 만드는 내림 차순
                return (n2+n1).compareTo(n1+n2);
            }
        });
        
        for(int i=0; i<sNumbers.length; i++){
            answer += sNumbers[i];
        }
        
        // "000" 과 같이 0이 여러번인 경우 제외
        if(answer.startsWith("0"))
            answer = "0";
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43237?language=java

이분탐색을 응용하여 문제를 구현하였음

이분탐색 알고리즘 코드

int BinarySearch(int arr[], int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

해결 방안 제시에 앞서 이분 탐색을 이용하여 알고리즘을 구현할 때 위와 같은 코드를 이해하고 있으며 이 코드를 응용하여 구현하는 것이 좋음

해결 방안

1. 무엇(start, mid, end)을 이분 탐색할 것이고 어떤 걸(위의 BinarySearch 코드의 target) 비교하여 다음 탐색 구간을 정할지 먼저 찾음
=> 이분 탐색할 것: 예산의 상한액(mid) 
=> 비교대상(target) : M(주어진 총 예산)

2. 예산의 최대 상한액(answer)을 구하므로 예산의 상한액(mid)을 이분 탐색함

3. Input에서 비교 대상으로 M(주어진 총 예산)이 주어지므로 M을 target으로 정해 다음 탐색 구간을 정함

4. M과 비교하기위해 상한액을 적용한 budgets 배열들의 합(sum)을 구하는 알고리즘이 포함되어야함

5. answer를 구하기 위해 최대 상한액을 찾아내야함

이분 탐색 알고리즘 코드와 해결 방안을 조합하여 구현하면 아래와 같은 코드가 될 수 있음

코드

import java.util.*;
// 예산
class Solution {
    // budgets: 지방에서 요청한 예산 / M: 총 예산
    public int solution(int[] budgets, int M) {
        int answer = 0;
        long sum = 0;
        
        Arrays.sort(budgets);
        
        for(int budget : budgets){
            sum += budget;
        }
        
        // 요청하는 예산들의 합 <= 총 예산
        if(sum <= M){
            // 상한액은 가장 큰 값
            answer = budgets[budgets.length-1];
        }
        // 요청하는 예산들의 합 > 총 예산
        else{
            
            int start, mid, end;
            sum = 0;
            // 예산의 크기
            start = 0; 
            mid = 0;
            end = budgets[budgets.length-1]; 
            
            // 이진 탐색
            while(start <= end){
                
                mid = (start + end) / 2;
                
                sum = 0;    
                // sum 구하기
                for(int i=0; i<budgets.length; i++){
                    if(budgets[i] < mid){
                        sum += budgets[i];
                    }
                    else{
                        sum += mid;
                    }
                }
                
                // 비교대상
                if(sum > M){
                    end = mid - 1;
                }
                else{
                    start = mid + 1;
                    answer = Math.max(answer, mid);
                }
                
            }
        }
        
        return answer;
    }
}