뜨균이의 개발 생활

메모리 관리

운영체제(OS)의 메모리 관리란 컴퓨터 시스템의 메모리 자원을 효율적으로 관리하고, 프로그램들이 안정적이고 효율적으로 실행되도록 지원하는 기능을 의미합니다.
메모리 관리는 다음과 같은 주요 기능으로 구성됩니다.

1. 메모리 관리의 목적

프로세스 격리

각 프로세스가 서로의 메모리에 영향을 주지 않도록 보호.

효율적인 자원 활용

메모리의 사용을 최적화하여 시스템 성능을 극대화.

빠른 접근

프로그램이 메모리에 빠르게 접근할 수 있도록 지원.

안정성 및 보안

메모리 관리 오류로 인한 시스템 불안정성 및 보안 문제 방지.

2. 메모리 관리 기법

2.1 물리적 메모리와 논리적 메모리

물리적 메모리 (Physical Memory)

실제 RAM의 주소 공간.

논리적 메모리 (Logical Memory)

프로그램이 사용하는 가상 주소 공간.

2.2 메모리 할당 방식

연속 메모리 할당 (Contiguous Memory Allocation)

단일 분할: 전체 메모리를 하나의 프로세스가 사용.
다중 분할: 메모리를 여러 프로세스가 연속적으로 사용.
단점: 외부 단편화(프로세스가 종료된 후 남은 작은 메모리 공간)

분할 메모리 할당 (Partitioned Allocation)

고정 분할: 메모리를 크기가 고정된 여러 분할로 나눔.
가변 분할: 필요에 따라 크기가 다른 분할로 나눔.
단점: 고정 분할의 경우 내부 단편화(분할 크기보다 작은 메모리 사용)

2.3 가상 메모리 (Virtual Memory)

페이징 (Paging)

메모리를 같은 크기의 페이지로 나누어 관리.
페이지 테이블: 논리적 페이지 번호와 물리적 프레임 번호를 매핑.
장점: 외부 단편화 문제 해결, 메모리 효율성 향상.
단점: 페이지 테이블 관리의 오버헤드.

세그멘테이션 (Segmentation)

메모리를 논리적 단위(세그먼트)로 나누어 관리.
세그먼트 테이블: 세그먼트 번호와 물리적 주소를 매핑.
장점: 프로그램 논리 구조 반영, 효율적 메모리 사용.
단점: 외부 단편화 발생 가능.

페이징과 세그멘테이션 혼합 (Segmented Paging)

세그먼트를 페이지로 나누어 관리.
장점: 세그멘테이션의 논리적 구조와 페이징의 효율성 결합.

3. 메모리 관리 전략

3.1 교체 알고리즘
메모리가 부족할 때, 어떤 페이지를 교체할지 결정하는 방법입니다.

FIFO (First In First Out)

가장 먼저 들어온 페이지를 교체.

LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체.

LFU (Least Frequently Used)

가장 적게 사용된 페이지를 교체.

Optimal Page Replacement

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 (이론적 모델).

3.2 스와핑 (Swapping)
프로세스를 메모리에서 디스크로, 디스크에서 메모리로 옮기는 작업.
메모리가 부족할 때 프로세스를 임시로 디스크로 이동시켜 메모리를 확보.

3.3 캐시 메모리
CPU와 메인 메모리 사이에 위치한 고속 메모리.
자주 사용되는 데이터나 명령어를 저장하여 접근 속도를 향상.

4. 메모리 보호

가상 메모리

프로세스가 자신에게 할당된 메모리 외부를 접근하지 못하도록 보호.

5. 메모리 단편화

내부 단편화

고정 크기의 블록 할당 시, 사용되지 않는 공간이 발생.

외부 단편화

가변 크기의 블록 할당 시, 사용되지 않는 작은 블록들이 메모리 공간에 흩어져 발생.

해결 방법

메모리 압축 (Compaction)

메모리 블록을 모아서 연속된 공간을 만듦.

페이징

메모리를 고정 크기의 페이지로 나누어 외부 단편화 문제 해결.

버디 시스템 (Buddy System)

메모리를 2의 제곱 크기로 나누어 효율적으로 할당.

운영체제의 메모리 관리는 복잡하고 중요한 작업으로, 효율적인 메모리 사용과 프로그램 간의 보호를 위해 다양한 기법과 전략이 사용됩니다. 
이러한 기술들은 시스템의 성능과 안정성을 보장하며, 메모리 자원을 최대한 효율적으로 활용할 수 있도록 합니다.

프로그래머스의 올바른 괄호 문제를 풀어봤습니다.

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제

풀이

괄호가 올바르게 만들어지면 true
괄호가 올바르게 만들어지지 않으면 false

올바른 경우
'()'  true

올바르지 않은 경우
')('  false
')'  false
'('  false

스택을 사용하여 문제를 풀었습니다.
'(' 는 추가시키고 ')' 는 제거하였습니다.
최종적으로 Stack에 아무것도 남아있지 않아야 올바른 괄호라고 판단했습니다.
최초에 ')' 가 먼저 들어오면 올바른 괄호가 아닙니다.

boolean solution(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if ('(' == c) {
            stack.add(c);
            continue;
        }
        if (')' == c) {
            if (stack.empty()) return false;
            stack.pop();
            continue;
        }
    }
    return stack.empty();
}

후기

* 난이도 (5점 만점)

5 : 풀 줄 알면 기업 코딩 테스트는 문제없음.

4 : 평균적인 기업 코딩 테스트의 중간 이상.

3 : 평균적인 기업 코딩테스트의 쉬운 문제.

2 : 알고리즘 문제를 연습하고 있다면 풀 수 있는 문제.

1 : 시간이 오래 걸리지 않고, 누구나 풀 수 있는 문제.

프로그래머스 올바른 괄호 문제는 stack, queue 문제로 분류되어 있어서 해당 자료구조를 사용했습니다.

프로그래머스 소수 찾기를 풀어보았습니다.

링크

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

문제

풀이

모든 수의 조합을 만들고 그 중에서 소수 갯수를 반환합니다.
1. 모든 수의 조합 생성
2. 소수 갯수 반환

1. 모든 수의 조합 생성
createdNumber 함수에 모든 수의 조합을 생성하는 로직을 만들었습니다.
재귀함수를 이용하여 모든 수의 조합을 만들었습니다.

HashSet<Integer> set = new HashSet<>();

public void createdNumber(String com, String numbers) {
    if (!"".equals(com)) set.add(Integer.parseInt(com));
    for (int i = 0; i < numbers.length(); i++) {
        if (!"".equals(com)) set.add(Integer.parseInt(com));
        createdNumber(com + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1));
    }
}

....
....

반복문을 사용하여 모든 경우의 수를 생성합니다.
이 때 중복되는 수가 있으니 set을 이용하여 중복은 제거합니다.

con 값이 공백이 아닐경우 set에 담아줍니다.

if (!"".equals(com)) set.add(Integer.parseInt(com));

이 if문이 두 번 똑같이 나와서 setCom 함수로 따로 만들었습니다.

public void setCom(String com) {
    if (!"".equals(com)) set.add(Integer.parseInt(com));
}

public void createdNumber(String com, String numbers) {
    setCom(com);
    for (int i = 0; i < numbers.length(); i++) {
        setCom(com);
        createdNumber(com + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1));
    }
}

2. 소수 갯수 반환
중복을 제거한 수의 조합 중에 소수인 수의 갯수를 반환합니다.
스트림의 filter를 이용하여 소수인 수만 count 하였습니다.

// 2. 소수 갯수 반환
return (int) set.stream().filter(n -> isPrime(n)).count();

isPrime 함수는 소수인지 판별해주는 함수입니다.

public boolean isPrime(int num) {
    if (num < 2) return false;

    int limit = (int) Math.sqrt(num);

    for (int i = 2; i <= limit; i++)
        if (num % i == 0)
            return false;

    return true;
}

전체코드

HashSet<Integer> set = new HashSet<>();

public boolean isPrime(int num) {
    if (num < 2) return false;

    int limit = (int) Math.sqrt(num);

    for (int i = 2; i <= limit; i++)
        if (num % i == 0)
            return false;

    return true;
}

public void setCom(String com) {
    if (!"".equals(com)) set.add(Integer.parseInt(com));
}

public void createdNumber(String com, String numbers) {
    setCom(com);
    for (int i = 0; i < numbers.length(); i++) {
        setCom(com);
        createdNumber(com + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1));
    }
}

public int solution(String numbers) {
    // 1. 모든 수의 조합 생성
    createdNumber("", numbers);

    // 2. 소수 갯수 반환
    return (int) set.stream().filter(n -> isPrime(n)).count();
}

후기

* 난이도 (5점 만점)

5 : 풀 줄 알면 기업 코딩 테스트는 문제없음.

4 : 평균적인 기업 코딩 테스트의 중간 이상.

3 : 평균적인 기업 코딩테스트의 쉬운 문제.

2 : 알고리즘 문제를 연습하고 있다면 풀 수 있는 문제.

1 : 시간이 오래 걸리지 않고, 누구나 풀 수 있는 문제.

프로그래머스의 소수 찾기 문제는 완전탐색에 대해 공부가 필요한 문제입니다.
완전탐색을 공부하여 모든 수의 조합을 생성하고 소수를 판별하여 갯수만 반환해주면 됩니다.
완전탐색 + 소수판별.

링크

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

문제

풀이

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

조건을 하나씩 적용하겠습니다.

1. 다트 게임은 총 3번의 기회로 구성된다.

총 3개의 값을 구합니다.

2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.

입력 받는 점수 범위는 0~10 입니다.

3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.

S : 1제곱 

D : 2제곱

T : 3제곱

4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.

* : 현재 점수, 이전 점수 X 2

# : 현재 점수 X (-1)

5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다.

* : 이전 점수가 없다면 현재 점수만 X 2

6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다.

4, 5번 조건을 적용해주면 6번도 해결됩니다.

7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다.

4, 5번 조건을 적용해주면 7번도 해결됩니다.

8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.

3번의 다트 점수 중 S, D, T 은 하나씩 존재하므로 중복 체크 없이 구현하면 됩니다.

9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

3번의 다트 점수 중 *, # 조건이 있을때 적용하면 됩니다.

위의 설명대로 하나씩 구현하면 됩니다.

dartResult : 1S2D*3T

받은 dart 값을 나눠보면

1S

2D* (현재 점수와 이전 점수 X 2) -> 위의 1S도 X 2 

3T

이렇게 볼 수 있고

1^1 * 2

2^2 * 2

3^3

이렇게 완성됩니다.

반환은 3개 점수 합 입니다.

위의 로직 구현

class Solution {
	
	/**
	 * 카카오 다트 게임
	 * @param dartResult
	 * @return
	*/
	public int solution(String dartResult) {

		int count	= dartResult.length();
		int bonus 	= 0;
 		int[] arr 	= new int[3];
		int arrCnt 	= 0;
		for (int i = 0; i < count; ++i) {
			char ch =  dartResult.charAt(i);
			if (ch == 49) {
 				if (dartResult.charAt(i+1) == 48) {
					ch = 58;
					++i;
				}
			}
    		
			//옵션 로직
			switch(ch) {
			case '*':
				arr[arrCnt-1] *= 2;
				if (arrCnt-1 > 0) arr[arrCnt-2] *= 2;
				continue;
			case '#':
				arr[arrCnt-1] *= (-1);
				continue;
			}
    		
			//제곱 로직
			switch(dartResult.charAt(i+1)) {
			case 'S':
				bonus = 1;
				break;
			case 'D':
				bonus = 2;
				break;
			case 'T':
				bonus = 3;
				break;
			}
    		
			arr[arrCnt] = (int) Math.round(Math.pow(ch-'0', bonus));
			++arrCnt;
			++i;
		}
		return arr[0]+arr[1]+arr[2];
	}  
}

후기

* 난이도 (5점 만점)

5 : 풀 줄 알면 기업 코딩테스트는 문제 없음.

4 : 평균적인 기업 코딩테스트의 중간 이상.

3 : 평균적인 기업 코딩테스트의 쉬운 문제 .

2 : 알고리즘 문제를 연습하고 있다면 풀 수 있는 문제.

1 : 시간이 오래 걸리지 않고, 누구나 풀 수 있는 문제.

난이도는 생각보다 쉬운 편이었으며 문제를 이해하고 천천히 풀면 충분히 풀 수 있다.

어려운 기술이 들어간 것은 없고, 말 그대로 문제 내용을 하나씩 구현한 것이다.