BangBang's Devlogs

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;
    }
}

준비물 

JDK, Eclipse 등을 이미 설치하였고 환경 구성까지 완료되어있다고 가정함

1. e(fx)clipse (3.5.0) 플러그인 설치

• Java를 이용하여 데스크톱 응용 프로그램을 개발할 때 GUI 라이브러리인 JavaFX를 사용하기 위해 e(fx)clipse 플러그인을 설치
• Help > Eclipse Marketplace > e(fx)clipse 설치

2. SceneBuilder 설치

• GUI 작업을 위해 Oracle javafx SceneBuilder 2.0 설치
• 다운로드: https://www.oracle.com/technetwork/java/javafxscenebuilder-1x-archive-2199384.html

3. 정상구동 확인

• 이클립스에서 JavaFX 프로젝트 생성

• 생성된 UserInteractionView.fxml파일 마우스 우클릭 > Open with SceneBuilder 클릭

• Open with SceneBuilder 클릭시 아래와 같이 GUI를 구성할 수 있는 화면이 생성됨

• SceneBuilder 화면 저장 후 Main 클래스를 클릭해보면 아래와 같은 비슷한 코드가 생성되어있음
  
  SceneBuilder를 이용하여 직접 화면을 구성할 수 있으며 화면 구성시 Main의 코드도 자동으로 수정됨
  또한 JavaFX 라이브러리를 이용하여 Main에서 직접 코드로 화면을 구성이 가능함 

package com.IntelligentSystem.UserInteraction;

import javafx.application.Application;
import javafx.fxml.FXMLLoader;
import javafx.scene.Scene;
import javafx.scene.layout.BorderPane;
import javafx.stage.Stage;

public class Main extends Application {
    @Override
    public void start(Stage primaryStage) {
        try {
            BorderPane root = (BorderPane)FXMLLoader.load(getClass().getResource("UserInteractionView.fxml"));
            Scene scene = new Scene(root,400,400);
            scene.getStylesheets().add(getClass().getResource("application.css").toExternalForm());
            primaryStage.setScene(scene);
            primaryStage.show();
        } catch(Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {

        launch(args);
    }
}

• Main 클래스 실행시 따로 화면 구성을 한게 없어서 아래와 같이 아무 화면이 없는 프로그램이 실행되며 정상으로 구동됨을 확인할 수 있음

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;
    }
}

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

해결 방안

1. 전체 경우는 (000~999)라고 생각하였으며 그 중 서로 다른 3자리 숫자 이므로 (123~987)로 범위를 줄일 수 있었음
또한 같은 숫자와 0이 들어간 숫자가 나온 경우 continue 해줘서 가능한 전체 숫자를 정해줌 (위와 같이 전체 경우가 주어짐)

2. 전체 경우의 수를 돌면서 baseball 이차원 배열에 담긴 전체 수와 비교하여 strike 수와 ball 수가 모두 같으면 가능한 답이 되므로 answer++ 해줌
=> 도중 flag를 두어 strike 수와 ball 수가 틀린 경우 break를 해주고 flag에 따라 answer++를 해줌

코드

import java.util.*;

// 숫자 야구

class Solution {
    public int solution(int[][] baseball) {
        // 세자리 수 가능한 답의 갯수
        int answer = 0;
        
        int[] answerNum = new int[3];
        int[] baseballNum = new int[3];
        int strike, ball;
        boolean flag;
        
        // 세자리수 전체 경우 돌면서 baseball 전체 행이랑 비교
        // 전체 경우: 1~9 3개의 임의 숫자(서로다른 3자리 숫자)(123~987)
        for(int i=123; i<=987; i++){
            // 각 자리 수
            answerNum[0] = i/100;
            answerNum[1] = (i%100)/10;
            answerNum[2] = i%10;
            
            // 0 나오면 제외
            if(answerNum[0] == 0 || answerNum[1] == 0 || answerNum[2] == 0)
                continue;
            
            // 같은 숫자 나온 경우 제외
            if(answerNum[0] == answerNum[1] || answerNum[1] == answerNum[2] || answerNum[0] == answerNum[2])
                continue;
            
            flag = true;
            // baseball 한 행씩 비교해서 전체 baseball 행 다 맞으면 answer++
            for(int j=0; j< baseball.length; j++){
                
                strike = 0;
                ball = 0;
                
                // baseball 각 자릿수
                baseballNum[0] = baseball[j][0]/100;
                baseballNum[1] = (baseball[j][0]%100)/10;
                baseballNum[2] = baseball[j][0]%10;
                
                // answerNum과 baseballNum 스트라이크 체크
                for(int k=0; k<3; k++){
                    if(answerNum[k] == baseballNum[k])
                        strike++;
                }
                
                // answerNum과 baseballNum 볼 체크
                for(int k=0; k<3; k++){
                    for(int x=0; x<3; x++){
                        if(k != x){
                            if(answerNum[k] == baseballNum[x])
                                ball++;
                        }
                    }
                }
                
                // baseball에 저장되 있는 스트라이크, 볼 수와 우리가 체크한 strike, ball 수 비교
                if(baseball[j][1] == strike && baseball[j][2] == ball){
                    continue;
                }
                else{
                    flag = false;
                    break;
                }   
            }
            if(flag)
                answer++;
        }
        
        return answer;
    }
}

준비물 

JDK, Eclipse 등을 이미 설치하였고 환경 구성까지 완료되어있다고 가정함

1. OpenCV 설치

• Windows 버전 다운로드: https://opencv.org/releases/ 
• 환경 변수 PATH 추가: {설치 PATH}\opencv\build\x64\vc14(버전에 따라 다름)\bin

2. OpenCV 라이브러리 사용을 위한 설정 (User Libraries에 OpenCV 라이브러리 추가)

• Windows > Preferences > Java > Build Path > User Libraries에 New를 눌러 라이브러리 이름을 적어줌
• 해당 폴더에 우측의 Add External JARs를 클릭하여 opencv-xx.jar를 추가함
  {설치 PATH}\opencv\build\java\opencv-xx.jar 선택

3. 프로젝트에 OpenCV 라이브러리 적용

• openCV를 적용하고자 하는 프로젝트 우클릭 > properties > Java Build Path > Libraries > Add Library > User Library > openCV를 눌러 적용해줌

4. 프로젝트에 OpenCV 라이브러리 잘 적용됬는지 확인

• 확인 코드

import org.opencv.core.Core;
import org.opencv.core.CvType;
import org.opencv.core.Mat;

public class OpenCVTest{

	public static void main(String[] args) {
        System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
        System.out.println(Core.NATIVE_LIBRARY_NAME);
        Mat mat = Mat.eye(5, 5, CvType.CV_8UC(1));
        System.out.println(mat.dump());

        launch(args);
    }
}

• Console 창에서 결과 확인

5. 참고자료

• 설정 참고: https://rosia.tistory.com/247