Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
접은 글을 통해 먼저 답변을 해보시고 제가 정리한 답을 확인해보시기 바라겠습니다!!

면접 리스트

GET, POST 방식의 차이점

TCP 3-way-handshake

TCP 와 UDP 의 차이점

HTTP 와 HTTPS 의 차이점

HTTP 1.0과 1.1의 차이는 무엇인가요?

HTTP2와 그 특징에 대해서 설명해 주세요.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

모음 배열의 사전순으로 정렬합니다. 그 이후 인덱스를 찾습니다.

소스코드

import java.util.*;

class Solution {
    ArrayList<String> dict = new ArrayList<>();
    String std = "AEIOU";
    
    public void init(int num, int cnt, String cmd) {
        if(num == cnt) {
            dict.add(cmd);
            return;
        }
        
        for(int i = 0; i < 5; i++){
            init(num, cnt + 1, cmd + Character.toString(std.charAt(i)));
        }
    }
    
    public int solution(String word) {
        int answer = 0;
        
        for(int i = 1; i <= 5; i++) {
            init(i, 0, "");
        }
        Collections.sort(dict);
        int idx = 1;
        for(String s: dict) {
            if(s.equals(word)){
                answer = idx;
                return answer;
            }
            idx++;
        }
        return answer;
    }
}

코드 설명

• 클래스 변수
  
  • dict: "AEIOU"로만 이루어진 단어들을 담을 리스트입니다. 이 리스트는 가능한 모든 단어를 사전 순으로 정렬한 후, 주어진 단어의 순서를 찾는 데 사용됩니다.
  • std: 사용될 알파벳들이 담긴 문자열입니다. 즉, 'A', 'E', 'I', 'O', 'U'입니다.
• init 메서드
  
  • 이 함수는 재귀적으로 호출되어 cmd라는 문자열을 구성해 나가면서 모든 가능한 단어를 dict 리스트에 추가합니다.
  • num은 현재 단어의 길이를 나타내며, cnt는 현재까지 구성된 문자열의 길이를 나타냅니다. num과 cnt가 같으면, 즉 cmd가 길이에 맞게 완성되면 그 단어를 dict에 추가합니다.
  • for 루프는 각 자리마다 'A', 'E', 'I', 'O', 'U' 중 하나의 문자를 선택하여, 해당 문자를 cmd에 붙여가며 재귀적으로 호출합니다.
  • 이 방식은 길이 1부터 길이 5까지의 모든 가능한 단어를 생성합니다.
• solution 메서드
  • init 메서드를 호출하여 길이가 1부터 5까지인 모든 단어를 dict에 추가합니다.
  • 그런 후 dict를 사전 순으로 정렬합니다. 이때 사전 순 정렬은 문자열의 알파벳 순서에 맞춰 자동으로 이루어집니다.
  • 정렬된 dict에서 주어진 word와 일치하는 단어를 찾아 그 순서(idx)를 반환합니다. idx는 1부터 시작하는 순번입니다.
  • word가 발견되면 즉시 answer에 해당 값을 할당하고 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

union-find 함수를 사용하여 연결된 전선의 갯수를 구하는 문제를 사용합니다. 끊어진 전선에 대하여 완전탐색을 진행합니다. 

소스코드

class Solution {
    public int[] parent;
    
    public void init(int n) {
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    public int findParent(int n) {
        if (parent[n] != n) {
            parent[n] = findParent(parent[n]);
        }
        return parent[n];
    }
    
    public void union(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        int len = wires.length;
        for(int i = 0; i < len; i++) {
            // i는 끊는
            parent = new int[n+1];
            init(n);
            
            for(int j = 0; j < len; j++) {
                if(i == j) {
                    continue;
                }
                if(findParent(wires[j][0]) != findParent(wires[j][1])) {
                    union(wires[j][0], wires[j][1]);
                }
            }
            
            // 각 송전탑의 최상위 부모 노드 갱신 및 개수 세기
            Map<Integer, Integer> connect = new HashMap<>();
            for (int j = 1; j <= n; j++) {
                int root = findParent(j);
                connect.put(root, connect.getOrDefault(root, 0) + 1);
            }
            
            // 두 개의 그룹으로 나뉘었는지 확인하고 차이 계산
            if (connect.size() == 2) {
                List<Integer> counts = new ArrayList<>(connect.values());
                int diff = Math.abs(counts.get(0) - counts.get(1));
                answer = Math.min(answer, diff);
            }
            
        }
        return answer;
    }
}

코드 설명

• 클래스 변수
  
  • parent: 각 노드의 부모를 나타내는 배열입니다. Union-Find에서 사용되는 핵심 배열입니다.
• init 메서드
  
  • 부모 배열을 초기화합니다. 각 노드의 부모를 자기 자신으로 설정하여, 초기에는 모두 독립적인 집합으로 시작합니다.
• findParent 메서드
  
  • 주어진 노드 n의 부모를 찾는 함수입니다. 경로 압축(Path Compression) 기법을 사용하여 부모를 재귀적으로 찾아, 트리의 높이를 낮추고 효율성을 높입니다.
• union 메서드
  • 두 집합을 합치는 함수입니다. findParent를 이용해 각 노드의 부모를 찾고, 더 작은 부모를 선택하여 큰 부모를 그 아래로 합칩니다. 이로써 두 집합이 하나로 결합됩니다.
• solution 메서드
  
  • 전선 끊기:
    • 전선이 여러 개 있는데, 각 전선에 대해서 하나씩 끊어보고 그 결과를 확인합니다. i == j일 때는 i번째 전선만 끊고 나머지 전선은 그대로 연결합니다.
  • 전선 연결:
    • 각 전선의 두 끝을 union으로 연결합니다. 즉, 전선들이 연결된 노드를 하나의 네트워크로 묶습니다.
  • 네트워크 크기 계산:
    • 연결된 네트워크의 부모 노드(parent[j])를 기준으로 각 네트워크의 크기를 계산합니다. 부모 노드별로 네트워크에 속한 노드의 개수를 connect 맵에 저장합니다.
  • 두 네트워크로 분리되었는지 확인:
    • connect.size()가 2일 때, 즉 두 개의 독립적인 네트워크로 나누어진 경우에만 그 크기 차이를 계산합니다.
    • counts.get(0)과 counts.get(1)을 비교하여 두 네트워크의 크기 차이를 diff로 구하고, 이 값이 최소가 되도록 answer를 갱신합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

던전의 순서를 지정한 후 단순히 피로도를 비교하여 탐험 가능한 최대 던전 수를 구합니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited = new boolean[9];
    List<Integer> list = new ArrayList<>();
    int ans = 0, K = -1;
    int[][] pDungeons;
    
    public void find(int cur, int size) {
        if (cur == size) {
            int pirodo = K, stage = 0;
            for(int num: list) {
                if (pirodo >= pDungeons[num][0]) {
                    pirodo -= pDungeons[num][1];
                    stage++;
                }
            }
            
            ans = Math.max(ans, stage);
            return;
        }
        
        for (int i = 0; i < size; i++) {
            if (visited[i]) continue;
            list.add(i);
            visited[i] = true;
            
            find(cur + 1, size);
            
            visited[i] = false;
            list.remove(list.size() -1);   
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        int n = dungeons.length;
        pDungeons = new int[n][2];
        for(int i = 0; i < n; i++) {
            pDungeons[i][0] = dungeons[i][0];
            pDungeons[i][1] = dungeons[i][1];
        }
        K = k;
        
        find(0, n);
        
        return ans;
    }
}

코드 설명

• 클래스 변수 선언
  
  • visited: 방문 여부를 추적하는 배열로, 최대 9개의 던전을 탐색할 수 있다고 가정하여 크기가 9로 설정됩니다.
  • list: 현재 탐색 중인 던전 순서의 인덱스를 저장합니다.
  • ans: 탐험 가능한 최대 던전 수를 저장하는 변수입니다.
  • K: 초기 피로도를 저장하는 변수입니다.
  • pDungeons: 입력으로 받은 던전 배열을 저장하는 2차원 배열입니다.
• 탐색 메서드 (find)
  
  • cur는 현재 재귀 깊이(탐색 중인 단계)를 나타내며, size는 던전의 총 개수입니다.
  • 기저 조건: cur가 size와 같으면 현재 순열에 대해 탐험을 시도합니다.
  • 탐험 가능 여부 확인: list에 저장된 인덱스 순서대로 던전을 탐험하며, 탐험할 수 있으면 피로도를 차감하고 stage를 증가시킵니다.
  • 최대 탐험 가능한 던전 수(ans)를 업데이트합니다.
  • for 루프: 방문하지 않은 던전을 탐색하여 list에 추가하고 재귀적으로 다음 탐색을 진행합니다. 이후 방문 표시를 해제하고 마지막 요소를 제거하여 상태를 되돌립니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

갈색 타일과 노란색 타일의 합이 카펫의 전체 넓이를 구할 수 있습니다. 그를 이용해서 소인수를 통해 맞는 가로와 세로 값을 구하고 갈색 타일 수가 일치하는 값을 리턴합니다. 가로가 더 길어야 하므로 i가 큰 값으로 시작합니다.

소스코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {0, 0};
        int area = brown + yellow;
        for (int row = area; row > 1; row--) {
            if (area % row == 0) {
                int col = area / row;
                if ((row * 2 + (col - 2) * 2) == brown) {
                    answer[0] = row;
                    answer[1] = col;
                    return answer;
                }
            }
        }
        return answer;
    }
}

코드 설명

• for (int row = area; row > 1; row--) { if (area % row == 0) { int col = area / row;
  
  • row는 카펫의 가로 길이로, 전체 면적(area)의 약수를 찾기 위해 area부터 2까지 역순으로 탐색합니다.
  • if (area % row == 0) 조건은 row가 area의 약수인지 확인합니다.
    약수인 경우, 대응되는 세로 길이 col을 계산합니다 (col = area / row).
• if ((row * 2 + (col - 2) * 2) == brown) { answer[0] = row; answer[1] = col; return answer; } }
  
  • (row * 2 + (col - 2) * 2) == brown 조건은 주어진 row와 col이 brown 타일 수를 만족하는지 확인합니다.
    • row * 2는 위와 아래 테두리를 포함하는 타일 수입니다.
    • (col - 2) * 2는 양쪽의 세로 테두리를 포함하는 타일 수입니다. 여기서 -2는 모서리 타일이 중복 계산되지 않도록 하는 역할을 합니다.
  • 조건이 만족되면 answer 배열에 row와 col 값을 저장하고 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

인덱스를 통해서 해당 인덱스가 소수인 지를 확인하고 조합을 통해서 해당 값이 소수인지 확인하는 알고리즘입니다.

소스코드

import java.util.*;

class Solution {
    boolean[] isPrime;
    Set<Integer> uniqueNumbers = new HashSet<>();
    
    public void initPrimeArray(int max) {
        isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * 2; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    public void findCombinations(String prefix, String str) {
        if (!prefix.isEmpty()) {
            int num = Integer.parseInt(prefix);
            if (isPrime[num]) {
                uniqueNumbers.add(num);
            }
        }
        for (int i = 0; i < str.length(); i++) {
            findCombinations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1));
        }
    }

    public int solution(String numbers) {
        int maxNum = (int) Math.pow(10, numbers.length());
        initPrimeArray(maxNum);

        // 모든 조합을 탐색
        findCombinations("", numbers);

        return uniqueNumbers.size();
    }
}

코드 설명

• 소수 배열 초기화 메소드(initPrimeArray)
  
  • initPrimeArray는 max까지의 숫자에 대해 소수 여부를 판별해 isPrime 배열에 저장합니다.
  • 에라토스테네스의 체 알고리즘을 사용하여 소수 판별을 효율적으로 수행합니다.
  • isPrime[i]가 true이면 i는 소수입니다. false로 변경된 값은 소수가 아닙니다.
• 순열 생성 및 소수 판별 메소드(findCombinations)
  
  • findCombinations는 prefix를 통해 현재까지의 숫자 조합을 나타내며, str은 사용 가능한 숫자입니다.
  • prefix가 비어 있지 않으면, 숫자로 변환하여 소수 여부를 확인합니다.
  • prefix와 str을 활용해 재귀적으로 모든 가능한 조합을 생성합니다.
  • 발견된 소수는 uniqueNumbers에 저장됩니다. => 동일한 값을 넣지 않기 위해 Set 자료구조를 이용합니다.
• solution 메소드
  
  • maxNum은 입력된 숫자 문자열의 길이에 따라 가장 큰 숫자를 계산합니다 (10^length).
  • initPrimeArray를 통해 maxNum까지의 소수 여부를 미리 계산합니다.
  • findCombinations 메서드를 호출해 모든 가능한 숫자 조합을 탐색하고 소수를 찾습니다.
  • uniqueNumbers.size()를 반환하여 발견된 소수의 개수를 출력합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

모의고사를 제일 많이 맞춘 사람을 구하는 문제입니다. 각 수포자가 규칙이 있으니 문제 번호에 패턴의 길이만큼의 나머지로 문제를 푸는 방법으로 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[][] omr = {
                {1, 2, 3, 4, 5},
                {2, 1, 2, 3, 2, 4, 2, 5},
                {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };
        
        int[] correctCount = new int[3]; // 정답 수를 저장할 배열
        
        for (int i = 0; i < answers.length; i++) {
            for (int j = 0; j < 3; j++) {
                if (omr[j][i % omr[j].length] == answers[i]) {
                    correctCount[j]++;
                }
            }
        }
        
        // 최대 정답 수 찾기
        int maxCorrect = Arrays.stream(correctCount).max().getAsInt();
        
        // 최대 정답 수와 일치하는 사람을 리스트에 추가
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (correctCount[i] == maxCorrect) {
                answer.add(i + 1); // 사람 번호는 1부터 시작하므로 i + 1
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

코드 설명

• int[][] omr
  
  • omr 배열은 각 수포자가 문제를 푸는 패턴을 저장합니다.
  • 각 수포자는 해당 배열에 정의된 주기를 반복하여 답을 제출합니다.
• int[] correctCount = new int[3];
  correctCount는 각 수포자가 맞힌 문제의 수를 저장하는 배열입니다.
• for (int num: nums) { ponkets.put(num, ponkets.getOrDefault(num, 0) + 1); }
  nums 배열을 순회하면서 각 숫자가 ponkets 맵에 이미 존재하는지 확인합니다.
  • 존재하면 해당 숫자의 값에 +1을 합니다.
  • 존재하지 않으면 기본값 0에서 +1을 하여 새로운 키-값 쌍으로 추가합니다.
• for (int i = 0; i < answers.length; i++) {
    for (int j = 0; j < 3; j++) {
      if (omr[j][i % omr[j].length] == answers[i]) {
        correctCount[j]++; } } }
  
  • 외부 for 루프는 주어진 answers 배열을 순회하면서, 각 문제의 정답을 확인합니다.
  • 내부 for 루프는 각 수포자의 답안 패턴을 현재 문제 번호에 맞게 가져옵니다. i % omr[j].length를 사용하여 패턴의 길이에 맞게 인덱스를 순환시킵니다.
  • 만약 해당 수포자의 답이 실제 answers의 답과 일치한다면, 그 수포자의 correctCount 값을 증가시킵니다.
• int maxCorrect = Arrays.stream(correctCount).max().getAsInt();
  correctCount 배열에서 가장 높은 정답 수를 찾아 maxCorrect에 저장합니다.
• 가장 높은 정답 수를 가진 수포자의 번호를 찾고, answer 리스트에 추가합니다. 사람 번호는 1부터 시작하므로 i + 1을 사용합니다.
• return answer.stream().mapToInt(Integer::intValue).toArray();
  answer 리스트를 정수 배열로 변환하여 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

하나의 명함의 최대 값을 가로로 설정하고 각 명함마다의 최대의 가로와 세로를 설정해야 모든 명함이 들어가는 명함 케이스의 최소 크기를 측정할 수 있습니다.

소스코드

class Solution {
    public int solution(int[][] sizes) {
        int row = Integer.MIN_VALUE, col = Integer.MIN_VALUE;
        for(int[] size: sizes) {
            row = Math.max(row, Math.max(size[0], size[1]));
            col = Math.max(col, Math.min(size[0], size[1]));
        }
        
        return row * col;
    }
}

코드 설명

• for(int[] size: sizes) {
  row = Math.max(row, Math.max(size[0], size[1]));
  col = Math.max(col, Math.min(size[0], size[1])); }
  sizes 배열을 순회하면서 각 명함의 크기를 확인합니다.
  
  • Math.max(size[0], size[1])를 사용해 현재 명함의 긴 변을 찾습니다. 이 값을 row와 비교하여 row에 더 큰 값을 저장합니다.
  • Math.min(size[0], size[1])를 사용해 현재 명함의 짧은 변을 찾습니다. 이 값을 col과 비교하여 col에 더 큰 값을 저장합니다.
• return row * col
  가장 큰 row와 col 값의 곱을 반환하여 지갑의 최소 크기를 계산합니다. 이 값은 모든 명함이 들어갈 수 있는 최소 크기의 지갑입니다.