Computer Science Knowledge Storage

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

포인트

가장 최소의 처리량 평균 시간을 구하는 문제였습니다. 요청시간이 빠른 순대로 정렬을 하면 짧은 작업시간을 가지는 일들에 대해서는 너무 오래 기다리게 되고, 짧은 작업시간 순대로 정렬을 하면 요청이 먼저 온 작업을 처리를 하지 못하게 됩니다. 

따라서 현재 시간에 따라 처리 가능한 작업을 구하고 그 중에서 요청시간이 짧은 것을 먼저 처리합니다.

소스코드

import java.util.*;

class Solution {
    
    static class Job implements Comparable<Job> {
        int requestTime, workingTime;
        
        public Job(int requestTime, int workingTime) {
            this.requestTime = requestTime;
            this.workingTime = workingTime;
        }
        
        @Override
        public int compareTo(Job j) {
            if (this.requestTime == j.requestTime) {
                return this.workingTime - j.workingTime;
            }
            return this.requestTime - j.requestTime;
        }
    }
    
    public int solution(int[][] jobs) {
        PriorityQueue<Job> disk = new PriorityQueue<>();
        int len = jobs.length;
        
        for(int[] job: jobs) {
            disk.add(new Job(job[0], job[1]));
        }
        
        int time = 0; // 현재 시간
        int ans = 0; // 처리량 평균 구하기
        List<Job> execList = new ArrayList<>();
        
        while (!disk.isEmpty() || !execList.isEmpty()) {
            // 현재 시간에 요청된 작업을 모두 execList에 추가
            while (!disk.isEmpty() && time >= disk.peek().requestTime) {
                execList.add(disk.poll());
            }

            // 작업을 소요 시간 기준으로 정렬
            if (!execList.isEmpty()) {
                Collections.sort(execList, Comparator.comparingInt(job -> job.workingTime));
                Job exec = execList.remove(0);
                if (time < exec.requestTime) {
                    time = exec.requestTime;
                }
                time += exec.workingTime;
                ans += time - exec.requestTime;
            } else if (!disk.isEmpty()) {
                time = disk.peek().requestTime;
            }
        }
        
        return ans / len;
    }
}

코드 설명

Job 클래스

• Job 클래스는 Comparable 인터페이스를 구현하며, 작업의 요청 시간(requestTime)과 소요 시간(workingTime)을 필드로 가지고 compareTo 메서드는 Job 객체를 요청 시간 순서로 정렬합니다. 요청 시간이 동일할 경우, 소요 시간 기준으로 정렬하도록 조건을 설정할 수 있습니다.

• PriorityQueue<Job> disk = new PriorityQueue<>();
  작업 요청 시간 기준으로 정렬되는 우선순위 큐를 초기화합니다. Job 객체를 담아 요청 시간이 빠른 순서대로 작업을 처리할 수 있습니다.
• while문 내부 변수 사용부분
  • time은 현재 시각을 나타내며, ans는 작업 완료까지 걸린 총 시간을 누적합니다.
  • execList는 현재 처리 가능한 작업 목록입니다.
• while (!disk.isEmpty() || !execList.isEmpty()) { ... }
  • disk 큐의 작업 중 현재 time에 요청된 작업을 execList로 이동합니다.
  • execList에 작업이 있으면 소요 시간 기준으로 정렬하고, 가장 짧은 작업을 선택하여 실행합니다.
  • time이 해당 작업의 요청 시간보다 작으면, time을 그 요청 시간으로 맞춥니다.
  • time을 해당 작업의 소요 시간만큼 증가시키고, 요청부터 종료까지 걸린 시간(time - requestTime)을 ans에 더합니다.
  • 만약 execList가 비어 있고 disk에 작업이 남아 있다면, time을 다음 작업의 요청 시간으로 설정하여 작업을 진행할 수 있게 합니다.

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

포인트

최솟값을 찾기 위해 정렬을 사용해도 되지만 가장 효율적인 자료 구조 Heap을 이용하여 스코빌 지수의 최솟값을 찾도록 코드를 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scovilles = new PriorityQueue<>();
        
        for (int level: scoville) {
            scovilles.add(level);
        }
        
        int mix = -1;
        int ans = 0;
        while (scovilles.peek() < K) {
            if (scovilles.size() < 2) {
                return -1;
            }
            int first = scovilles.poll();
            int second = scovilles.poll();
            mix = first + second * 2;
            scovilles.add(mix);
            ans++;
        }
        
        return ans;
    }
}

코드 설명

• PriorityQueue<Integer> scovilles = new PriorityQueue<>();
  스코빌 지수를 저장하는 Heap을 생성합니다. 해당 힙은 최소 힙으로 구현합니다.
• 섞은 음식의 스코빌 지수
  • while 루프는 큐의 최솟값(scovilles.peek())이 K 미만인 동안 반복됩니다.
  • 이때 큐의 크기가 2 미만이 되면, 더 이상 결합할 수 없으므로 -1을 반환하여 목표를 달성할 수 없음을 나타냅니다.
  • 최솟값 두 개를 꺼내어(poll() 메서드 사용) 결합하여 새로운 스코빌 지수(first + second * 2)를 계산합니다.
  • 새로 만든 스코빌 지수를 큐에 다시 추가하고, 결합 횟수 ans를 증가시킵니다.
• 섞은 횟수를 반환합니다.

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

면접 리스트

NAT 네트워크를 사용했을때의 사이드 이펙트는 없는가?

왜 라우팅 알고리즘은 모든 라우터에서 실행되어야 하는가?

라우터에서의 라우팅과 포워딩의 차이를 설명해주세요.

loopback address는 무엇인가? 또 어떻게 쓰일 수 있는가

default gateway는 무슨 역할을 하는가?

만약 라우팅 테이블에 다음 목적지에 대한 맵핑정보가 없다면 라우터는 어떻게 동작하는가?

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

면접 리스트

여러개의 프로세스가 존재할 때 트랜스포트 레이어의 동작을 설명해보세요

소켓 생성과 삭제에서 발생하는 오버헤드를 줄이는 방법은 무엇이 있을까요?

N+1번의 세그먼트에 대한 ACK가 도착하고 N에 대한 ACK는 도착하지 않았을 때 TCP는 어떻게 동작하는가?

네트워크 레이어의 목적은 무엇일까요?

왜 트랜스포트 레이어에 checksum이 있는데 네트워크 레이어에도 체크섬이 있는가?

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

포인트

다리를 큐로 표현해 각 트럭의 상태를 관리하며, 트럭이 다리를 건너는 동안의 시간과 다리의 무게 제한을 고려해 순차적으로 트럭을 다리에 올리고 내립니다. 반복문은 트럭이 모두 다리를 건널 때까지 계속됩니다.

소스코드

import java.util.*;

class Solution {
    static class Truck {
        int weight, position;

        public Truck(int weight) {
            this.weight = weight;
            this.position = 0;
        }

        public Truck(int weight, int position) {
            this.weight = weight;
            this.position = position;
        }
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0; // 경과 시간
        int bridgeWeight = 0; // 현재 다리 위의 트럭 총 무게
        Queue<Truck> bridge = new LinkedList<>(); // 다리 위의 트럭 큐
        int idx = 0; // 대기 트럭 인덱스

        while (idx < truck_weights.length || !bridge.isEmpty()) {
            time++;

            if (!bridge.isEmpty()) {
                Truck frontTruck = bridge.peek(); // 맨 앞의 트럭
                if (time - frontTruck.position >= bridge_length) { // 다리를 다 건넜을 경우
                    bridgeWeight -= frontTruck.weight; // 다리 무게에서 제외
                    bridge.poll(); // 트럭 다리에서 내림
                }
            }

            if (idx < truck_weights.length) {
                if (bridgeWeight + truck_weights[idx] <= weight && bridge.size() < bridge_length) {
                    bridge.add(new Truck(truck_weights[idx], time)); // 트럭 다리에 올림
                    bridgeWeight += truck_weights[idx]; // 현재 다리 무게 갱신
                    idx++; // 대기 트럭 인덱스 증가
                }
            }
        }
        return time;
    }
}

코드 설명

• Truck 클래스
  • weight: 트럭의 무게.
  • position: 트럭이 다리를 건너기 시작한 시점(시간).
• 변수 초기화:
  • time: 전체 시뮬레이션의 경과 시간을 나타냅니다.
  • bridgeWeight: 현재 다리 위에 있는 트럭들의 총 무게입니다.
  • bridge: 현재 다리를 건너고 있는 트럭들을 저장하는 큐입니다.
  • idx: 대기 중인 트럭을 가리키는 인덱스입니다.
• 메인 로직:
  • 시간 증가: 매 반복마다 time이 증가합니다. 이는 시뮬레이션의 한 단계를 의미합니다.
  • 트럭 이동:
    • bridge 큐에서 맨 앞에 있는 트럭(frontTruck)의 위치를 확인합니다.
    • time - frontTruck.position이 bridge_length보다 크거나 같다면, 트럭은 다리를 건넜으므로 bridge.poll()로 큐에서 제거하고, bridgeWeight에서 트럭의 무게를 뺍니다.
  • 새 트럭 추가:
    • 아직 다리를 건너지 않은 트럭이 있을 경우(idx < truck_weights.length), 현재 다리의 무게(bridgeWeight + truck_weights[idx])가 제한을 초과하지 않고 다리 길이 조건을 만족하면 새 트럭을 bridge에 추가합니다.
    • 새 트럭이 다리에 추가되면 bridgeWeight를 업데이트하고 idx를 증가시켜 다음 트럭을 가리킵니다.
• 종료 조건:
  • 대기 중인 트럭이 더 이상 없고(idx >= truck_weights.length), bridge에 남아 있는 트럭도 없을 때 시뮬레이션이 종료됩니다.
• 결과 반환:
  • 최종적으로 경과된 time을 반환합니다. 이는 모든 트럭이 다리를 건너기까지 걸린 총 시간입니다.

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

포인트

시간 복잡도 O(N^2)으로 잘 관리하면 문제가 패스하는 것을 확인했습니다. 하지만 시간복잡도를 줄이고 싶어 Stack을 이용하였고, O(N)의 시간 복잡도를 갖는 코드를 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] ans = new int[len];
        Stack<Integer> stack = new Stack<>();
        
        // 각 시간의 인덱스를 스택에 저장
        for (int i = 0; i < len; i++) {
            // 현재 가격이 스택의 마지막 가격보다 낮으면, 하락 시간 계산
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = i - idx; // 하락 시간 계산
            }
            stack.push(i); // 현재 인덱스를 스택에 추가
        }
        
        // 남아 있는 인덱스들은 끝까지 가격이 떨어지지 않음
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            ans[idx] = len - 1 - idx;
        }
        
        return ans;
    }
}

코드 설명

• 루프를 통해 각 시점의 가격을 순회합니다.
  • 스택의 크기와 현재 가격이 마지막 주식 가격보다 낮으면
    • 스택에서 해당 인덱스를 꺼내고, 그 하락 시간을 i - idx로 계산하여 ans 배열에 저장.
  • 현재 시점 i를 스택에 추가하여 이후 가격 변화에 대해 추적.
• 스택에 남아있는 시점들은 가격이 떨어지지 않은 것이므로 전체 크기에 대해 배열에 저장합니다.

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

포인트

프로세스의 최댓값과 그 갯수를 효율적으로 관리하는게 포인트였습니다. Map으로도 관리할 수 있고, 리스트로도 관리할 수 있겠지만
저는 이 문제에서 우선순위 큐를 사용하였습니다.

소스코드

import java.util.*;

class Solution {
    
    static class Process {
        int priority, index;
        public Process(int priority, int index) {
            this.priority = priority;
            this.index = index;
        }
    }
    
    public int solution(int[] priorities, int location) {
        Queue<Process> processes = new LinkedList<>();
        PriorityQueue<Integer> remainPriority = new PriorityQueue<>(Collections.reverseOrder());
        
        int len = priorities.length;
        
        for(int i = 0; i < len; i++) {
            int priority = priorities[i];
            remainPriority.add(priority);
            processes.add(new Process(priority, i));
        }
        
        int order = 1;
        while(true) {
            Process ready = processes.poll();
            int maxPriority = remainPriority.poll();
            if (maxPriority == ready.priority) {
                if (location == ready.index) {
                    return order;
                } else {
                    order++;
                }
            } else {
                remainPriority.add(maxPriority);
                processes.add(ready);
            }
        }
    }
}

코드 설명

• static class Process
  우선순위와 고유번호를 저장하기 위해 static class Process를 선언합니다.
• PriorityQueue<Integer> remainPriority = new PriorityQueue<>(Collections.reverseOrder());
  priority를 저장할 우선순위 큐를 선언합니다.
  
  • 해당 우선순위큐는 최소 힙이 아닌 최대 힙으로 선언하기 위해 Collections.reverseOrder()을 사용합니다.
• processes 큐에서 프로세스를 하나씩 꺼내 처리합니다.
• remainPriority에서 가장 높은 우선순위를 가져옵니다.
• 현재 프로세스의 우선순위가 가장 높은 우선순위와 같으면:
  • location에 있는 프로세스인지 확인합니다.
  • 맞다면 현재 순서(order)를 반환합니다.
  • 아니라면 실행 순서를 증가시킵니다.
• 현재 프로세스의 우선순위가 가장 높지 않으면:
  • 프로세스를 다시 큐에 넣고 remainPriority에 추가하여 다음 순서를 준비합니다.

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

포인트

유명한 스택 문제입니다. ')'이 있으면 '('가 스택에 존재해야합니다. 또 마지막 스택에는 아무런 원소가 없어야합니다.

소스코드

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> bracketValidator = new Stack<>();
        
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == ')') {
                if (bracketValidator.isEmpty() || bracketValidator.peek() != '(') {
                    return false;
                }
                bracketValidator.pop();
            } else {
                bracketValidator.add('(');
            }
        }
        
        return bracketValidator.isEmpty() ? true : false;
    }
}

코드 설명

• Stack<Character> bracketValidator = new Stack<>();
  Character를 원소로 갖는 Stack을 선언합니다.
• if (s.charAt(i) == ')') { if (bracketValidator.isEmpty() || bracketValidator.peek() != '(') { return false; } }
  • ')'가 되었을 때 Stack에 (이 없거나 empty이면 false를 리턴합니다.
  • 이후 Stack의 원소를 pop해줍니다.
• else { bracketValidator.add('('); }
  • '(' 값을 만났을 때에는 Stack에 add 해줍니다.
• return bracketValidator.isEmpty() ? true : false;
  • Stack의 원소가 없으면 true를 리턴 그렇지 않으면 false를 리턴합니다.