반응형

Java 클래스에서 of(), from(), getInstance()와 같은 정적 팩토리 메소드를 많이 사용하는 것을 보고, 정적 팩토리 메소드를 사용하는 이유에 대해서 궁금하여 글을 정리하게 되었습니다.

 

 

1. 정적 팩토리 메소드(static factory method)는 무엇인가?

  • 정적 팩토리 메소드는 객체 생성의 역할을 하는 클래스 메소드이다.
  • 자바 코드를 짜봤다면 정적 팩토리 메소드를 써본 적이 있을 것입니다.
public class Example {
    public static void main(String[] args) {
        // 직접 생성자를 통해서 객체를 생성
        List<String> list1 = new ArrayList<>();
        list1.add("김씨");
        list1.add("박씨");
        list1.add("정씨");
        list1.add("이씨");
        list1.add("윤씨");
        
        // 정적 팩토리 메소드를 통해서 객체를 생성
        List<String> list2 = List.of("김씨", "박씨", "정씨", "이씨", "윤씨");
    }
}

위 코드는 List.of()를 사용하여 직접 생성자를 사용하지 않고, 리스트를 만드는 방법에 대한 코드입니다.

 

 

 

2. 정적 팩토리 메소드는 왜 사용하는가?

  • 사실 저도 코드를 짜면서 이 부분이 가장 의문이었습니다. 객체 생성은 생성자라는 것을 통해서 할 수 있는데, 굳이 왜 정적 팩토리 메소드를 사용해서 객체를 생성하는 것일까에 대한 의문입니다.
  • 정적 팩토리 메소드를 사용하는 이유를 알아보기 위해서는 생성자와 어떤 점이 다르고, 어떤 점에서 더 좋은 점이 있는지 먼저 알아야 합니다.

 

 

 

3. 정적 팩토리 메소드와 생성자의 차이

(1) 이름을 가질 수 있습니다.

  • 객체의 생성은 목적에 따라서 생성자를 구별해서 사용해야 합니다. 생성자는 이름을 가지고 있지 않기 때문에 목적에 맞게 객체를 생성하려면 해당 클래스의 내부 구조를 잘 알고 있어야 합니다
  • 정적 팩토리 메소드를 사용하면 객체 생성 목적에 맞게 이름을 지정할 수 있습니다. 이를 통해 얻을 수 있는 효과는 코드의 가독성을 더욱 높일 수 있습니다.

 

 

(2) 호출할 때마다 새로운 객체를 생성할 필요가 없습니다.

  • 생성자를 호출하여 객체를 가져올 때는 새로운 객체를 생성해야 합니다.
  • 하지만 만약 싱글톤처럼 미리 만들어져 있는 객체를 가져와서 사용해도 되는 상황이라면 굳이 생성자를 직접 호출해서 사용할 필요가 없습니다.
  • 이때 정적 팩토리 메소드를 이용하면 호출할 때마다 새로운 객체를 생성하지 않아도 됩니다. 정적 팩토리 메소드를 사용해서 객체의 생성을 제한하고 싶다면 객체의 생성자를 private로 설정하는 것이 좋습니다.

 

 

(3) 하위 자료형 객체를 반환할 수 있습니다.

  • 생성자 역할을 하는 정적 팩토리 메소드는 반환값을 가지고 있기 때문에 하위 타입의 객체를 반환할 수 있습니다.
  • 아래는 점수만 입력하면 해당 점수에 맞는 티어의 타입을 반환해 주는 분기분을 팩토리 메소드에서 구현할 수 있습니다.
public class Level {
    public static Level of(int score) {
        if (score < 1000) {
            return new Bronze();
        } else if (score < 10000) {
            return new Silver();
        } else if (score < 100000) {
            return new Gold();
        } else {
            return new Platinum();
        }
    }
}

class Bronze extends Level {
    public Bronze() {
        System.out.println("브론즈 티어");
    }
}

class Silver extends Level {
    public Silver() {
        System.out.println("실버 티어");
    }
}

class Gold extends Level {
    public Gold() {
        System.out.println("골드 티어");
    }
}

class Platinum extends Level {
    public Platinum() {
        System.out.println("플래티넘 티어");
    }
}

 

 

(4) 객체 생성을 캡슐화할 수 있습니다.

  • 생성자에 private를 붙이고, 정적 팩토리 메소드 안에서 생성자를 호출함으로써 내부 상태를 외부에 드러낼 필요 없이 객체 생성 인터페이스를 단순화할 수 있습니다.
  • DTO에서 사용하는 from()을 한 가지 예시로 볼 수 있습니다.
  • StudentDto의 내부 구현을 모르고 있더라도 Student 객체를 정적 팩토리 메소드 from()의 파라미터로 넣어주면 해당 Student에 대한 Dto 객체를 얻을 수 있습니다.
public class StudentDto {
    private String name;
    private Integer age;
    
    private StudentDto(String name, Integer age) {
        this.name = name;
        this.age = age;
    }
    
    public static StudentDto from(Student student) {
        return new StudentDto(student.getName(), student.getAge());
    }
    
    // Getter, Setter 생략
}

 

 

 

객체 사이의 형변환이 필요하거나, 객체 생성이 반복되는 경우에는 생성자보다는 정적 팩토리 메소드를 활용해 보는 것이 좋을 것으로 보입니다. 

 

 

🔗 참고자료

정적 팩토리 메서드(Static Factory Method)는 왜 사용할까?

반응형
반응형

1. 관계


  • 하나의 데이터 베이스에는 여러 개의 테이블이 존재합니다. 
  • 여러 개의 테이블들은 서로 관계를 가지고 있고, 이런 관계를 '관계 화살표'를 이용하여 표현합니다.

 

[그림 1] 관계화살표 예시

 

 

여러 가지 관계의 종류에 대해서 알아봅시다.

 

(1) 1 : 1 관계

  • 유저 한 명에게는 하나의 유저 이메일이 존재한다고 해봅시다.
  • 그럼 유저와 유저 이메일은 1 : 1 관계를 가지게 됩니다.
  • 1 : 1 관계를 사용하면 두 개의 테이블로 나누어 테이블 구조를 더 쉽게 이해할 수 있도록 해준다는 장점이 있습니다.

[그림 2] 1 : 1 관계의 관계 화살표

 

 

(2) 1 : N 관계

  • 위에서 만들었던 유저 테이블이 존재하고, 만약 이 유저가 구매할 상품들을 장바구니에 담는다고 해봅시다.
  • 한 명의 유저는 여러 개의 상품을 장바구니에 담을 수 있습니다.
  • 이때는 유저와 상품이 1 : N 관계를 가지게 됩니다.
  • 여기서 주의해야 할 점은 유저가 장바구니에 어떠한 상품도 안 담을 수도 있기 때문에 0이라는 값도 생각해야 합니다.

[그림 3] 1 : N 관계의 관계 화살표

 

 

(3) N : M 관계

  • 만약 학생과 학생들이 듣는 강의가 여러 개 있다고 생각해 봅시다.
  • 한 명의 학생은 여러 개의 강의를 가질 수 있고, 하나의 강의도 여러 명의 학생을 가질 수 있습니다.
  • 이때는 관계 테이블을 하나 형성해서 학생과 강의가 N : M 관계를 가질 수 있도록 해줍니다.

[그림 4] N : M 관계의 관계 화살표

 

 

 

 

2. 키


  • 테이블 사이의 관계를 명확하게 구분할 수 있게 해 주고, 테이블 자체의 인덱스를 위해서 존재하는 개념이 '키(Key)'입니다.
  • 키의 종류에는 슈퍼키, 후보키, 기본키, 대체키, 외래키가 존재합니다.

[그림 5] 슈퍼키, 후보키, 기본키, 대체키의 관계

 

 

(1) 유일성과 최소성

  • 유일성은 말 그대로 중복되는 값이 없이 유일한 값이어야 하는 성질을 말합니다.
  • 최소성은 해당 키를 구성하는 모든 부분 집합들이 유일성을 가지지 않는 성질을 말합니다.
  • 다시 말해서 유일성은 하나의 Key로 하나의 Tuple을 유일하게 구별할 수 있는 성질을 말하고, 최소성은 꼭 필요한 속성들만을 가지고 구성되어 있는 성질을 말합니다.

[그림 6] 속성 A, B, C에 대한 표

 

[그림 6]을 예시로 들면서 유일성과 최소성을 이해해 봅시다.

[그림 7] 그림 6을 분석해본 표

 

[그림 7]은 키가 될 수 있는 요소의 부분 집합을 알아보고, 유일성과 최소성 그리고 키로 사용할 수 있는지의 여부를 분석해 본 표입니다.

  • (A), (B), (C)는 각각 겹치는 값들이 존재하기 때문에 유일성을 만족하지 않습니다. 유일성을 만족하지 않기 때문에 최소성은 볼 필요도 없이 존재하지 않고, 키로 사용할 수 없습니다.
  • (A, B), (B, C), (A, C)는 각각 겹치는 값들이 없기 때문에 유일성을 만족합니다. 최소성을 보기 위해서 각 요소의 부분 집합을 확인해 보면 각 부분 집합의 요소들이 모두 유일성을 가지고 있지 않기 때문에 키로 사용할 수 있습니다.
  • (A, B, C)는 겹치는 값들이 없기 떄문에 유일성을 만족합니다. 하지만 부분 집합 중 {A, B}, {B, C}, {A, C}는 이미 유일성을 가지고 있기 때문에 키로 사용할 수 없는 슈퍼키입니다.

 

 

(2) 기본키 (Primary Key, PK)

  • 기본키는 유일성과 최소성을 모두 만족하는 키를 말합니다.
  • 기본키를 사용하면 테이블에서 어떤 요소를 유일하게 구분해 낼 수 있습니다.
  • 기본키는 자연키와 인조키 중에서 골라서 설정하게 됩니다.

 

# 자연키

이름 그대로 속성 중 자연스럽게 중복되지 않는 것들을 뽑다가 나오는 키를 말합니다. "이름", "성별", "주민등록번호"가 있을 때, 이름과 성별을 중복된 값이 들어올 가능성이 매우 높습니다. 그에 반해 주민등록번호는 중복될 가능성이 매우 희박하기 때문에 자연스럽게 주민등록번호를 키로 사용하게 됩니다.

 

# 인조키

요소마다 인위적으로 어떤 Id 값을 부여하는 것을 말합니다. 대표적으로 MySQL의 auto-increment가 인조키의 예시에 속합니다. 사용해 봤다면 알겠지만, MySQL에서 데이터를 추가하게 되면 순차적으로 Id 값이 증가하는 것을 볼 수 있습니다.

 

 

(3) 외래키 (Foreign Key, FK)

  • 다른 테이블의 기본키를 그래도 참조하는 값으로서 개체와의 관계를 식별하는 데 사용하는 키입니다.
  • 외래키는 중복되어도 상관없습니다.
  • 앞서 설명했던 관계 그래프에서 유저와 상품의 사이를 예시로 들어봅시다.

[그림 8] Product 테이블에 있는 외래키 user_id

 

Product와 User는 N : 1 관계를 가지고 있기 때문에 Product에서 자신을 주문한 User에 대한 정보를 가지고 있어야 합니다. 이때 관계를 연결시켜 주기 위해서 Product 테이블에 자신을 주문한 User의 Id 값을 외래키로 넣어줍니다.

 

 

(4) 후보키 (Candidate Key)

  • 기본키(PK)가 될 수 있는 후보들의 집합입니다.
  • 후보키도 유일성과 최소성을 모두 만족합니다.

 

 

(5) 대체키 (Alternate Key)

  • 기본키로 대체될 수 있는 키를 말합니다.
  • 후보키가 여러 개인 경우 1개를 기본키(PK)로 지정하고, 기본키가 되지 못한 나머지 후보키들을 모두 대체키라고 할 수 있습니다.

 

 

(6) 슈퍼키 (Super Key)

  • 유일성을 만족하는 키를 말합니다.

 

 

💡 면접에서 나올 수 있는 질문들

  1. 키의 종류와 특징에 대해서 설명해 보세요.
  2. 유일성과 최소성에 대해서 설명해 보세요.

 

반응형
반응형

백준 1931번 회의실 배정

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

 

📖 문제

 

그리디 알고리즘의 대표적인 예시 문제라고 해도 될 문제입니다. 그래서 풀이에 대해서 조금 정리해보려고 합니다.

 

 

 

🔎 접근 방법

  • 회의 일정에는 시작 시간과 종료 시간이 존재합니다.
  • 회의 일정은 겹치면 안되고, 최대한 많은 회의를 진행해야 합니다.

 

위 조건을 생각해봤을 때, 이전 회의 일정의 종료 시간과 겹치지 않아야 하고 이후 일정의 시작 시간과 겹치지 않아야 합니다.

즉, 회의 일정을 종료 시간 기준으로 오름차순 정렬하여 종료 시간이 빠른 일정부터 해결해나가면 정답에 접근할 수 있습니다.

 

1. 회의 일정을 저장할 수 있는 클래스 선언 후 Comparable 구현하기

배열을 사용하는 풀이도 많았지만 가장 직관적이고 자바라는 언어 특성을 사용할 수 있도록 Meeting 클래스를 만들어 객체의 비교 기준을 정의할 수 있는 Comparable를 구현해 줬습니다.

class Meeting implements Comparable<Meeting> {
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting obj) {
        // 종료 시간이 동일하다면 시작 시점이 빠른 순으로 정렬
        if (this.end == obj.end) {
            return this.start - obj.start;
        }
        // 종료 시점이 빠른 순으로 회의 일정을 정렬
        return this.end - obj.end;
    }
}

start와 end는 회의의 시작 시간과 종료 시간이고, Comparable을 구현하기 위한 compareTo() 메소드를 보면 정렬 조건을 확인할 수 있습니다. 

 

위에서는 정렬 조건을 종료 시간만을 언급했지만, 문제에서 "회의의 시작시간과 끝나는 시간이 같을 수도 있다."란 조건이 존재하기 때문에 회의 시작 시간도 신경 써줘야 합니다. 반례를 한번 생각해 볼까요

[입력]
4
3 5
1 3
8 8
5 8

위처럼 만약 입력이 들어왔다고 했을 때, 정답이 몇일까요? 정답은 4입니다. 하지만 회의의 종료 시간만을 고려해서 정렬하게 되면 3이라는 결과를 얻을 수도 있습니다. 어떻게 3이 나올 수 있었을까요. 회의의 종료시간을 기준으로 정렬을 해보겠습니다.

Meeting A(1, 3) -> Meeting B(3, 5) -> Meeting C(8, 8) -> Meeting D(5, 8)

회의의 종료 시간을 오름차순으로 정렬했습니다. 이제 처음 데이터부터 확인하면서 회의 일정을 확인해 보면 아래와 같습니다.

1시 - 3시 : Meeting A
3시 - 5시 : Meeting B
8시 - 8시 : Meeting C

Meeting D의 시작 시간인 5시가 이전 미팅 Meeting C의 종료 시간 8시보다 작기 때문에 이어서 회의를 진행할 수 없습니다.

이런 반례가 발생할 수 있기 때문에 해당 문제는 회의의 종료 시간도 오름차순으로 정렬해줘야 하고, 회의 종료 시간이 같을 때는 시작 시간으로 오름차순 정렬을 해줘야 합니다.

 

 

2. 입력받은 데이터로 Meeting 인스턴스 만들어서 PriorityQueue에 넣기

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
PriorityQueue<Meeting> meetings = new PriorityQueue<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());
    meetings.offer(new Meeting(start, end));
}

Meeting 인스턴스를 저장해서 바로 우리가 정의한 Comparable의 정렬 조건대로 정렬하기 위해서 우선순위 큐(Priority Queue)를 사용했습니다. 물론 ArrayList를 사용해서 Collections.sort()를 사용해 줘도 됩니다.

 

 

3. Priority Queue의 Meeting 객체를 하나씩 꺼내오면서 이전 Meeting의 종료 시간과 비교하여 정답을 확인

Meeting prevMeeting = meetings.poll();
int answer = 1; // 가장 처음 회의 일정은 추가되기 때문에 1부터 시작
while (!meetings.isEmpty()) {
    Meeting meeting = meetings.poll();
    // 현재 회의 시작 시간이 이전 회의 일정의 종료 시간과 동일하거나 크면 정답에 추가
    if (prevMeeting.end <= meeting.start) {
        answer++;
        // 현재 회의를 이전 회의로 지정
        prevMeeting = meeting;
    }
}
System.out.println(answer);

prevMeeting(이전 회의)에 가장 우선순위가 높은 회의 일정을 하나 넣어줍니다. N은 1 이상이기 때문에 비어있는 검사를 하지 않고 바로 poll()을 사용해서 넣어줬습니다. 방금 꺼내준 회의 일정은 바로 추가되기 때문에 answer는 1로 초기화합니다.

 

그리고 이제 Priority Queue가 비워질 때까지 반복문을 돌면서 회의 일정을 확인합니다. 만약 이전 회의의 종료 시간보다 현재 회의의 시작 시간이 크거나 같다면 정답 카운트를 증가시키고, prevMeeting를 다시 현재 회의 meeting으로 갱신합니다.

 

 

 

🧑🏻‍💻 전체 코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PriorityQueue<Meeting> meetings = new PriorityQueue<>();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings.offer(new Meeting(start, end));
        }
        Meeting prevMeeting = meetings.poll();
        int answer = 1; // 가장 처음 회의 일정은 추가되기 때문에 1부터 시작
        while (!meetings.isEmpty()) {
            Meeting meeting = meetings.poll();
            // 현재 회의 시작 시간이 이전 회의 일정의 종료 시간과 동일하거나 크면 정답에 추가
            if (prevMeeting.end <= meeting.start) {
                answer++;
                // 현재 회의를 이전 회의로 지정
                prevMeeting = meeting;
            }
        }
        System.out.println(answer);
    }
}

class Meeting implements Comparable<Meeting> {
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting obj) {
        // 종료 시간이 동일하다면 시작 시점이 빠른 순으로 정렬
        if (this.end == obj.end) {
            return this.start - obj.start;
        }
        // 종료 시점이 빠른 순으로 회의 일정을 정렬
        return this.end - obj.end;
    }
}
반응형
반응형

1. 개요


프로세스가 여러 개라면 어떤 프로세스에게 먼저 CPU 소유권을 제공해야 할까요? 이런 고민 속에서 CPU의 이용률은 높이고, 프로세스의 대기 시간은 줄이면서, 응답 시간은 짧게 하기 위해서 나온 것이 CPU 스케줄링 알고리즘입니다.

 

CPU 스케줄링 알고리즘의 7가지 종류 (이외에도 더 존재하지만 여기서는 이정도만)

 

  • CPU 스케줄링 알고리즘은 크게 비선점형과 선점형으로 나눌 수 있습니다.
  • 비선점형 방식에는 FCFS(First Come, First Served), SJF(Shortest Job First), 우선순위 알고리즘이 존재합니다.
  • 선점형 방식에는 Round Robin(RR), SRT(Shortest Remaining Time), 다단계 큐, 다단계 피드백 큐 방식이 존재합니다.

 

 

 

2. 비선점형 방식 (non-preemptive)


  • 비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식입니다.
  • 다시 말해서 CPU가 실행되는 도중 중간에 강제로 프로세스를 중지하지 않는 방식을 말합니다.
  • Context Switching이 적게 일어나기 때문에 부하가 적다는 특징이 있습니다.

 

(1) FCFS (First Come First Served)

  • 이름 그대로 Ready Queue에 먼저 들어온 순서대로 처리하는 알고리즘입니다.
  • 먼저 요청한 프로세스부터 CPU를 할당하여 처리합니다.
  • 먼저 들어온 프로세스가 처리되는 시간 동안 프로세스들이 기다리는 시간이 길어지는 단점이 발생합니다. 이런 현상을 호위 효과라고 합니다.

Process 1이 처리되는 오랜 시간동안 기다리는 다른 프로세스들

 

 

(2) SJF (Shortest Job First)

  • FCFS에서 발생하는 호위 효과를 방지할 수 있는 알고리즘입니다.
  • CPU를 점유하는 시간이 짧은 프로세스부터 실행합니다.
  • 호위 효과는 피할 수 있지만, 긴 처리 시간을 요구하는 프로세스가 실행되지 않는 기아현상(Starvation)이 발생할 수 있습니다.

파란색 Process가 처리된 후 빨간색이 들어오고, 그 다음으로 노란색이 들어와서 처리되는 상황 (초록색이 실행되지 않는 기아현상)

 

 

(3) 우선순위 알고리즘

  • 프로세스들에게 우선순위를 부여하고, 그 우선순위대로 프로세스를 처리하는 알고리즘입니다.
  • 만약 2개의 프로세스가 우선순위가 동일하다면 먼저 Ready Queue에 들어온 순서대로 처리합니다.
  • 위에서 설명한 FCFS, SJF 알고리즘도 우선순위 알고리즘에 포함시킬 수 있습니다.
  • 우선순위 알고리즘에서 발생할 수 있는 위험 요소는 위에서 말했던 "기아현상(Starvation)"이 있습니다.
  • 기아현상을 해결하기 위해서 오랫동안 대기상태였던 프로세스의 우선순위를 점차 증가시키는 Aging(에이징) 기법을 사용합니다.

 

 

 

3. 선점형 방식


  • 선점형은 현재 실행 중인 프로세스를 강제로 중단시켜 다른 프로세스에게 CPU 소유권을 할당하는 방식입니다.
  • 비선점형에 비해 Context Switching이 빈번하게 발생한다는 특징이 있습니다.

 

(1) Round Robin(RR, 라운드 로빈)

  • FCFS 알고리즘에 Time Slice(타임 슬라이스) 개념을 추가한 알고리즘으로 현대적인 CPU 스케줄링 방법입니다.
  • 정해진 타임 슬라이스만큼 프로세스에게 CPU 소유권을 줘서 처리하는 방식입니다.
  • 정해진 타임 슬라이스 만큼 CPU를 선점하여 프로세스를 처리하고, 만약 타임 슬라이스가 지났는데도 아직 처리되지 못했다면 Ready Queue의 가장 뒤쪽에 삽입됩니다.
  • 타임 슬라이스가 너무 크다면 FCFS와 다를 것이 없어 호위 효과가 발생할 수 있고, 타임 슬라이스가 너무 작다면 Context Switching이 너무 빈번하게 발생하여 오버헤드가 증가되는 현상이 발생할 수 있습니다.
  • 적당한 타임 슬라이스를 정하는 것이 중요한 알고리즘입니다.
Time Slice : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 말합니다.

 

 

(2) SRT (Shortest Remaining Time)

  • Rround Robin 알고리즘에 SJF 알고리즘을 합친 알고리즘입니다.
  • SRT에서는 프로세스가 정해진 시간(타임 슬라이스)만큼 CPU의 소유권을 얻어 처리될 수 있습니다. (Round Robin)
  • 이때 CPU의 소유권을 얻는 우선순위는 남은 처리 시간이 적은 순으로 결정됩니다. (SJF)

 

 

(3) 다단계 큐 스케줄링 (Multilevel Queue 스케줄링)

  • 우선순위별로 Ready Queue를 여러개 사용하는 방식의 스케줄링 알고리즘입니다.
  • 우선순위가 낮은 Queue에 있는 프로세스부터 모두 처리하고, 그다음 우선순위의 Queue에 있는 프로세스를 처리합니다.
  • 각 Ready Queue는 사용하는 알고리즘이 다를 수 있습니다.
  • 대표적인 특징으로는 Queue에서 Queue 사이에 프로세스 이동은 불가능하기 때문에 Starvation(기아현상)이 발생할 확률이 높은 알고리즘입니다.

 

 

(4) 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue 스케줄링)

  • 다단계 큐 스케줄링 방식에서 발전시킨 알고리즘입니다.
  • Queue와 Queue 사이에 프로세스 이동이 가능하고, Aging 기법도 적용할 수 있는 스케줄링 알고리즘입니다.

다단계 피드백 큐 스케줄링 방식의 프로세스 처리 과정

 

  • 위 과정에서 우선순위가 낮은 CPU 집중 프로세스들에서 Starvation이 발생할 수 있기 때문에 Aging 기법을 적용하여 이런 문제점을 보완합니다.

 

 

💡 면접에서 나올 수 있는 질문

  1. CPU 스케줄링 알고리즘의 종류와 특징을 설명하고, 장점과 단점에 대해서 설명해 보세요.
  2. 비선점형 방식과 선점형 방식의 차이점을 설명해 보세요.

 

 

🔗 참고자료

면접을 위한 CS 전공지식 노트

강민철 강사님의 운영체제 강의

 

 

반응형
반응형

운영체제는 프로세스가 실행될 때 해당 프로세스가 필요로 하는 적절한 메모리를 할당하게 됩니다. 프로세스에게 할당되는 메모리 구조에 대해서 알아보고자 합니다.

 

 

1. 프로세스의 메모리 구조


프로세스의 메모리 구조

그림에서 보면 바로 알 수 있듯이 스택 영역과 힙 영역은 크기가 동적으로 변하는(화살표가 존재) 구조를 가지고 있고, 데이터 영역과 코드 영역은 정적인 구조라고 볼 수 있습니다. 하나씩 어떤 역할을 하는지 알아봅시다.

 

 

(1) 스택 영역 (Stack Area)

  • 스택 영역은 함수(메서드), 함수에 인자로 들어가는 매개변수(Parameter), 함수 안에 있는 지역변수(Local Variable)가 저장되는 영역입니다.
  • 컴파일 시에 크기가 결정되고, 동적인 구조를 가지고 있습니다.
  • 위 그림에서 볼 수 있듯이 위쪽에 있는 주소부터 할당됩니다.
  • 스택 영역은 함수를 재귀적으로 호출할 때 크기가 동적으로 늘어날 수 있습니다.
  • 함수가 호출되면 Stack Frame이 스택 영역에 생성되고, 해당 Stack Frame 내부에 함수의 매개변수, 지역변수들이 쌓이게 됩니다.
  • Java 코드에서 무한적인 재귀 호출이 발생되도록 코드를 잘못 작성하면 볼 수 있는 예외인 StackOverFlow는 제한되어 있는 스택 영역으로 인해 발생하는 예외입니다. 

 

(2) 힙 영역 (Heap Area)

  • 힙 영역은 동적으로 할당되는 변수가 저장되는 영역입니다. Java에서는 객체가 Heap 영역에 저장됩니다.
  • 런타임 시에 크기가 결정되고, 동적인 구조를 가지고 있습니다.
  • 위 그림에서 볼 수 있듯이 아래쪽에 있는 주소부터 할당됩니다.

 

(3) 데이터 영역

  • 데이터 영역은 전역변수, 정적변수가 저장되는 영역입니다.
  • 정적인 구조를 가지고 있고, 프로그램이 종료되면 사라지는 변수들이 들어가 있는 영역입니다.
  • 데이터 영역은 BSS(Block Started by Symbol) 영역Data 영역으로 나뉘게 됩니다.
  • BSS 영역에는 초기화 되지 않은 변수가 저장되는 영역입니다.
  • Data 영역에는 다른 값으로 초기화된 변수가 저장되는 영역입니다.

 

(4) 코드 영역

  • 코드 영역은 실제 소스 코드가 기계어의 형태로 저장되는 영역입니다.
  • 정적인 구조를 가지고 있고, 수정이 불가능한 기계어로 저장되어 있기 때문에 Read Only의 특징을 가지고 있습니다. (수정 불가)

 

 

 

2. JVM(Java Virtual Machine)의 메모리 구조


  • Java를 학습하는 사람으로서 빼먹고 넘어갈 수 없는 내용이라고 생각되어 추가적으로 기록해보고자 합니다.
  • JVM은 운영체제(OS)로 부터 별도의 메모리 공간을 할당받아서 Java Application을 실행하는데 사용합니다.
  • 이런 JVM의 메모리를 Runtime Data Area라고 부릅니다.
  • Runtime Data Area는 Stack Area, Heap Area, Method Area, PC register, Native Method Stack으로 구성되어 있습니다.

 

(1) Method Area (Static Area)

  • 클래스 정보클래스 변수(static), 상수(final), 메서드 코드, 런타임 상수 풀 등의 데이터를 저장하는 영역입니다.
  • 한번 로드된 이후 메모리에 항상 상주하고 있는 영역입니다.
  • 모든 스레드가 공유할 수 있는 영역입니다.

 

(2) Stack Area

  • 함수(메서드)에서 직접 사용할 수 있는 지역변수(local variable), 매개변수(parameter), 객체의 경우에는 주소값을 저장합니다.
  • 함수가 호출되면 Stack Area에 Stack Frame이 생성되고, 해당 Stack Frame 내부에 지역변수, 매개변수 등이 쌓이게 됩니다.
  • 함수의 호출이 종료되면 pop으로 해당 Stack Frame이 제거됩니다.
  • JVM에서 Stack Area는 스레드마다 하나씩 가지고 있습니다.

 

(3) Heap Area

  • new를 통해서 생성된 객체, 배열 등이 저장되는 영역입니다.
  • JVM의 Statck Area에서 참조가 가능합니다. Heap Area에 존재하는데, 어떠한 곳에서도 참조를 하고 있지 않다면 메모리를 낭비하고 있기 때문에 GC(Garbage Collector)가 Heap Area에서 지워줍니다.

 

(4) PC(Program Counter) Register

  • 스레드가 생성될 때마다 생성되는 영역으로 현재 스레드가 실행되고 있는 부분의 주소와 해당 명령을 저장하고 있는 영역입니다.
  • 여러 스레드가 흐름을 잃지 않고 순차적으로 실행될 수 있도록 해줍니다.

 

(5) Native Method Stack

  • Java 코드 이외 다른 언어로 작성된 네이티브 코드를 실행하기 위한 영역입니다.
  • 성능 향상을 위해서 Java Application에서 다른 언어와 함께 사용되는 경우가 있습니다. 이때 다른 언어로 작성되어 제공되는 Method의 정보가 저장됩니다.

 

 

 

3. 면접에서 나올 수 있는 질문들


  • JVM의 메모리 구조와 각 영역에 대해서 설명해보세요.
  • Garbage Collector가 어떤 역할을 하는지 설명해보세요.

 

 

 

🙆🏻‍♂️ 마무리 하며


  • JVM은 프로세스인가라는 궁금점이 있었습니다. 글을 정리하고 싶었지만 정확한 근거가 되는 글을 찾을 수 없어서 따로 기록해보지 못했습니다. 
  • 운영체제 위에서 작동되고, 운영체제에 의해서 별도의 메모리 공간을 할당 받기 때문에 프로세스라고 생각은 되는데, 일반적인 프로세스의 메모리 구조와는 다른 구조를 가지고 있고, JVM의 메모리 관리 방식도 일반적인 프로세스와는 다르다고 알고 있습니다.

 

 

 

참고 자료

https://honbabzone.com/java/java-jvm/

면접을 위한 CS 전공지식 노트

반응형
반응형

DFS 문제 따로 BFS 문제 따로 풀어본 적은 있는데 한 문제에서 동일한 그래프로 DFS와 BFS를 모두 사용해야 하는 문제였습니다.

 

🔗 문제 링크

https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

 

 

🔍 문제 분석

  • 첫 째줄에 정점의 개수(N, 노드의 개수)와 간선의 개수(M) 그리고 탐색 시작 정점(V)이 공백으로 주어집니다.
  • 그다음 간선의 개수(M)만큼의 입력이 주어지고, 각 입력 줄에는 연결되어 있는 Node와 Node가 공백으로 주어집니다.
  • 정점의 번호는 1번부터 N번까지 이며, DFS 탐색 결과와 BFS 탐색 결과를 출력해 주면 되는 문제입니다.
  • 여기서 신경써줘야 할 점은 연결된 Node가 여러 개라면 크기가 작은 것부터 탐색을 시작합니다.

 

 

 

🖥️ 문제 풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static StringBuilder builder;
    static boolean[] visited;

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

        String[] inputData = reader.readLine().split(" ");
        n = Integer.parseInt(inputData[0]);
        int m = Integer.parseInt(inputData[1]);
        int v = Integer.parseInt(inputData[2]);

        // step 1. 그래프 만들기
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            inputData = reader.readLine().split(" ");
            int startNum = Integer.parseInt(inputData[0]);
            int endNum = Integer.parseInt(inputData[1]);

            graph[startNum][endNum] = 1;
            graph[endNum][startNum] = 1;
        }
        builder = new StringBuilder();
        visited = new boolean[n + 1];
        dfs(v, graph);
        builder.append("\n");
        visited = new boolean[n + 1];
        bfs(v, graph);
        System.out.println(builder);
    }

    // step 2. BFS 탐색 (Queue)
    public static void bfs(int start, int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int vortex = queue.poll();
            builder.append(vortex).append(" ");
            int[] vortexWithNodes = graph[vortex];

            for (int i = 1; i <= n; i++) {
                if (vortexWithNodes[i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

    // step 3. DFS 탐색 (재귀)
    public static void dfs(int start, int[][] graph) {
        visited[start] = true;
        builder.append(start).append(" ");
        int[] startWithNodes = graph[start];

        for (int i = 1; i <= n; i++) {
            if (startWithNodes[i] == 1 && !visited[i]) {
                dfs(i, graph);
            }
        }
    }
}

 

  • 처음에 Graph를 어떤 방식으로 해놓을지 고민했었습니다. 첫 번째 방법은 위에 구현한 방법과 같은 인접 행렬 방법을 사용하는 방법이 있고, 두 번째는 각 노드에 연결된 점들을 리스트에 모아두는 인접 리스트 방법이 존재합니다.
  • 인접 행렬 방법을 선택한 이유는 간단합니다. "연결된 노드가 여러 개라면 크기가 작은 노드부터 방문합니다."라는 조건에서 연결된 Node들이 정렬되어 있어야 된다는 것 때문입니다.
  • 만약 인접 리스트 방법을 사용했다면, 연결된 노드들을 정렬해 주는 Collections.sort()를 사용해야 됐습니다.

 

 

 

🧑🏻‍💻 문제 풀이 전략

1. BFS는 Queue를 이용해서 구현했습니다.

public static void bfs(int start, int[][] graph) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int vortex = queue.poll();
        builder.append(vortex).append(" ");
        int[] vortexWithNodes = graph[vortex];

        for (int i = 1; i <= n; i++) {
            if (vortexWithNodes[i] == 1 && !visited[i]) { // <-- 이미 탐색한 노드인지 확인
                queue.offer(i);
                visited[i] = true;
            }
        }
    }
}
  • 큐(Queue)를 통해서 탐색 노드에 연결된 노드들을 모두 탐색하고, 탐색이 가능한 데이터(값이 1이고, 방문기록이 false인 노드)라면 Queue에 모두 넣습니다.
  • 이때 Queue에 넣으면서 해당 노드의 방문처리를 해줘야 합니다.
  • Queue에 데이터가 없을 때까지 반복하여 BFS 탐색을 진행합니다.

 

2. DFS는 재귀를 이용해서 구현했습니다.

public static void dfs(int start, int[][] graph) {
    visited[start] = true;
    builder.append(start).append(" ");
    int[] startWithNodes = graph[start];

    for (int i = 1; i <= n; i++) {
        if (startWithNodes[i] == 1 && !visited[i]) { // <-- 이미 탐색한 노드인지 확인
            dfs(i, graph);
        }
    }
}
  • 재귀를 통해서 가장 깊은 곳까지 탐색을 하고, 더이상 탐색할 데이터가 없으면 빠져나오게 됩니다.

 

3. Graph와 Visited는 공유하는 데이터입니다.

  • 그래프 탐색을 하는데 있어서 Graph의 내부 값을 변경시키지는 않습니다.
  • 하지만 Visited는 값을 false에서 true로 변경시키며 탐색하기 때문에 static으로 선언해서 탐색 시작 전에 new boolean[]으로 초기화를 진행해줬습니다.
visited = new boolean[n + 1]; // <-- 탐색 전 초기화
dfs(v, graph);

visited = new boolean[n + 1]; // <-- 탐색 전 초기화
bfs(v, graph);

 

반응형

+ Recent posts