스미스요원

좋은 기회로 프로그래머스 데브코스 활동 후기에 대한 인터뷰를 진행하게 되었다!

후기글을 남겨야지 하다가 시간이 없어서 미루고만 있었는데,
인터뷰 내용에 내가 활동하면서 느낀 점들이 잘 담겨있는것 같아 이 글을 후기로 대신해도 좋을 것 같다.

교육도, 인터뷰도 매번 좋은 추억 만들어 주셔서 감사합니다 :)

페이지 교체 알고리즘이란?

• 가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하여 사용한다.

• 하지만 필요한 페이지만 올려도 메모리는 결국 차게 되고, 올라와있던 페이지가 다 사용된 후 자리만 차지하고 있을 수도 있다.

    즉 메모리가 가득 차면 안쓰는 페이지는 out 하고, 필요한 페이지는 in 시켜야 한다.

• 이 때 효율적인 페이지 교체를 위해 고안된 방법이 바로 페이지 교체 알고리즘이다.

• 프로세스와 운영체제의 경향에 알맞은 알고리즘을 선택하여 사용하는것이 좋다.

FIFO (First-in First-out)

• 메모리에서 내보낼 페이지를 선택할 때, 메모리에 먼저 올라온 페이지 순서대로 내보내는 방법

• 가장 간단한 방법이며, 특히 초기화 코드에 적절한 알고리즘이다.

    ◦  초기화 코드란? : 프로세스가 처음 실행될 때 최초 초기화를 수행하는 역할의 코드

OPT (Optimal)

• 앞으로 가장 사용하지 않을 예정인 페이지를 가장 우선적으로 내보내는 알고리즘

• FIFO에 비해 페이지 결함의 발생 횟수를 많이 감소시킬 수 있다.

    ◦  페이지 결함 : 메모리에 페이지가 올라와 있지 않아 페이지 적재가 필요한 상황

• 미래에 어떤 페이지가 사용되는지의 여부를 예측할 수 없기 때문에(앞으로 가장 사용하지 않을 예정인 페이지가 무엇인지 알 수 없음)
    이론적으로만 가능한 알고리즘이다.

LRU (Least-Recently-Used)

• 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

    ◦  최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다는 논리

• OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적인 구현이 가능하다.

• OPT 보다 페이지 결함이 더 많이 발생할 수 있지만, 구현 가능한 페이지 교체 알고리즘 중에서는 가장 좋다.

LFU (Least-Frequently-Used)

• 페이지의 참조 횟수로 교체할 페이지를 선택하는 알고리즘

• 누적 참조 횟수가 가장 낮은 페이지를 우선적으로 내보낸다.

    ◦ 가장 적게 참조된 페이지는 앞으로도 사용되지 않을 확률이 높다는 논리

    ◦ 누적 참조 횟수가 동일한 페이지끼리는 가장 오랫동안 사용되지 않은 페이지가(LRU) 우선적으로 제거된다.

• LRU는 참조된 시점을 고려하지만, LFU는 참조 횟수를 고려하기 때문에 더 과거의 참조성향까지 고려할 수 있다.

• 단점

    ◦  가장 최근에 참조된 페이지가 교체될 수 있다. (최근에 참조된 페이지일수록 앞으로 더 많이 참조될 가능성이 있는데 말이다)

    ◦  구현이 LRU보다 더 복잡하고 오버헤드가 발생할 수 있다.

MFU (Most-Frequently-Used)

• 마찬가지로 페이지의 참조 횟수를 활용하는 알고리즘
• LFU와 반대로, 누적 참조 횟수가 가장 높은 페이지를 우선적으로 내보낸다.

    ◦ 가장 많이 참조된 페이지는 앞으로 사용되지 않을 확률이 높다는 논리 (충분히 쓸만큼 쓴 페이지일 것이다)

참고자료

가상 메모리란?

• 물리적 메모리 크기의 한계를 극복하기 위해 나온 기술이다.

    ◦  가상 메모리를 사용하면 물리적 메모리 공간보다 큰 프로세스를 수행할 수 있다.

    ◦  예) 100MB 메모리 공간에서 200MB 크기의 프로세스를 수행할 수 있음

• 어떻게 가능한가?

    ◦  프로세스를 실행할 때 프로세스 전체가 아닌, 실행에 필요한 일부(페이지 단위)만 메모리에 올린다.

    ◦  이를 Demanding Paging 기법이라고 한다. (현재 필요한 페이지만 메모리에 올리는 것)

• 운영 체제는 물리 메모리의 제약을 갖고 있는 주기억장치를 보조하기 위해 디스크를 보조기억장치(Paging Space)로 사용한다.

    ◦  주기억장치와 보조 기억 장치를 묶어 하나의 가상 메모리를 구현한다.

    ◦  프로세스는 할당 받은 메모리가 실제 메모리인지, Swap 영역인지 모른다.

    ◦  Swap 영역은 실제 메모리가 아니기 때문에 지연시간이 발생하므로 가급적이면 사용하지 않는 것이 좋다.

         만약 Swap 영역의 사용일 계속해서 증가한다면 메모리 누수를 의심해 봐야 한다.

• 가상 메모리 사용의 장점

    ◦  더 많은 프로그램을 동시에 수행할 있어 CPU 이용률과 처리율이 높아진다.

    ◦  프로그래머는 메모리 크기에 관한 문제를 염려할 필요 없이 쉽게 프로그램을 작성할 수 있다.

    ◦  프로그램을 교체할 때 발생하는 메모리 교체 성능 문제를 최소화할 수 있다.

• 이런 가상 메모리 기법은 불연속 할당 기법인 페이징과 세그멘테이션 기법에 활용할 수 있다.

페이징 기법

• 프로세스를 일정한 크기의 페이지로 분할해서 메모리에 적재하는 방식

• 단순 페이징

    ◦  각 프로세스를 일정한 길이의 페이지로 나눈다. 이 때 페이지의 길이는 프레임과 같은 길이가 되도록 한다.

         -  페이지 : 고정 사이즈의 가상 메모리 내 프로세스 조각

         -  프레임 : 페이지 크기와 같은 주 기억 장치의 메모리 조각

    ◦  외부 단편화 (발생 X), 내부 단편화 (발생 O)

• 가상 메모리를 활용한 페이징

    ◦  단순 페이징과 달리 프로세스 페이지 전부를 로드할 필요가 없다.

         -  필요한 페이지가 있으면 나중에 자동으로 불러온다.

    ◦  복잡한 메모리 관리로 인한 오버헤드 발생할 수도 있다.

• 장점

    ◦  논리 메모리가 물리 메모리에 저장될 때 연속되어 저장될 필요가 없고, 물리 메모리의 남는 프레임에 적절히 배치되기 때문에

         외부 단편화가 생기지 않는다.

• 단점

    ◦  내부 단편화 문제가 발생할 수 있다. 페이지 단위를 작게하면 해결할 수 있지만, 페이지 매핑 과정이 복잡해져 비효율적이다.

세그멘테이션 기법

• 세그멘트 : 가상 메모리를 서로 크기가 다른 논리적 단위로 분할한 것

• 세그멘테이션 기법 : 프로세스를 물리적 단위인 페이지가 아닌 논리적 단위로 분할해서 메모리에 적재하는 방식

    ◦  페이징 : 소고기를 같은 크기로 잘라서 보관하는 것

    ◦  세그멘테이션 : 소고기를 부위 별로 잘라서 보관하는 것

• 의미가 같지 않는 논리적 내용을 기준으로 프로그램을 분할하기 때문에 각 조각의 크기가 동일하지 않다.

• 이러한 분할 방식을 제외하면 페이징과 동일하기 때문에, 매핑 테이블의 동작 방식은 페이징 기법과 동일하다.

• 단순 세그멘테이션

    ◦  각 프로세스는 여러 세그멘트로 나뉨

    ◦  외부 단편화 (발생 O), 내부 단편화 (발생 X)

    ◦  메모리 사용 효율 개선 및 동적 분할을 통한 오버헤드 감소 효과가 있다.

• 가상 메모리를 활용한 세그멘테이션

    ◦  필요하지 않은 세그멘트는 로드되지 않음. 필요한 세그멘트는 나중에 자동으로 불러들여짐

    ◦  복잡한 메모리 관리로 인한 오버헤드 발생할 수 있다.

• 장점

    ◦  내부 단편화 문제가 해소된다.

    ◦  보호와 공유 기능을 수행할 수 있다. 프로그램의 중요한 부분과 중요하지 않은 부분을 분리하여 저장할 수 있고,

         같은 코드 영역은 한 번에 저장할 수 있다.

• 단점

    ◦  외부 단편화 문제가 생길 수 있다.

참고자료

문제 설명

풀이 방법

• 접근 방식

    ◦  특별한 수학적 규칙이 존재하지 않는다. 노드를 돌면서 양의 수가 최대가 되는 경우를 찾는 탐색 문제이다.

• 핵심 아이디어

    ◦  문제에서 제시된 트리의 형태는 이진 트리이나, 매 분기마다 방문 가능한 노드는 자식 노드 단 두개가 아닌 현재 방문한 노드의 모든

         자식 노드라는 점이 포인트

          -  즉 방문한 노드와 방문하지 않은 노드를 관리하기 위한 배열이 필요하다.

    ◦  이를 단순하게 생각해서, 존재하는 모든 노드 관계를 훑으면서 부모는 방문했는데 자식은 방문을 안했다면 바로 방문하는 식으로

         파고 들어가는 DFS 로직을 작성하면 된다.

    ◦  늑대의 수가 양보다 더 많아지면 그 이후로 양의 수는 양수가 될 수 없으므로, 더이상 DFS 트리를 파고들어 갈 필요가 없다.

         바로 재귀를 종료해주자.

• 알고리즘

    ◦  DFS 트리

          -  단 탐색 트리의 형태(각 노드의 자식의 개수)가 일정하지는 않다.

파이썬 코드

def solution(info, edges):
    # 방문한 노드를 기록하는 리스트
    visited = [0] * len(info)
    visited[0] = 1
    answer = []
    
    def dfs(sheep, wolf, visited):
        # 양과 늑대의 수에 따른 상태 집계
        if(sheep > wolf):
            answer.append(sheep)
        else:
            return
        
        # 방문할 노드가 남아있는 경우
        for i in edges:
            if(visited[i[0]] == 1 and visited[i[1]] == 0):
                newVisited = visited.copy()
                newVisited[i[1]] = 1
                
                # 새로 방문한 노드의 양/늑대 집계
                if(info[i[1]] == 1):
                    dfs(sheep, wolf+1, newVisited)
                else:
                    dfs(sheep+1, wolf, newVisited)
                
    # return answer
    dfs(1,0,visited)
    return max(answer)

문제 설명

풀이 방법

• 접근 방식

    ◦  그래프 최단거리로 접근하는 문제이다.

    ◦  먼저 그래프상의 노드간의 최단거리를 계산해 문제를 간단하게 구조화 한 다음 필요한 처리를 추가해주자.

• 핵심 아이디어

    ◦  무지와 어피치가 헤어지는 지점을 어디로 했을 때 택시요금이 최저가 되는지를 찾으면 된다.

    ◦  즉 (시작점 ~ 헤어지는 지점) + (헤어진 지점 ~ 무지의 집) + (헤어진 지점 ~ 어피치의 집) 이 최저가 되는 헤어지는 지점을 찾는 문제

• 알고리즘

    ◦  floyd warshall 알고리즘을 사용해 먼저 노드간의 최단거리 연산을 해주었다.

    ◦  그 다음 모든 노드에 대해 해당 노드가 헤어지는 지점일 때의 택시 요금을 비교하여 최저가 되는 상황의 요금을 구했다.

파이썬 코드

def solution(n, s, a, b, fares):
    # set variables
    INF = int(1e9)
    graph = [[INF] * (n) for i in range(n)]
    
    # initialize
    for i in range(0,n):
        graph[i][i] = 0
    
    # 간선 정보 입력
    for i in fares:
        graph[i[0]-1][i[1]-1] = i[2]
        graph[i[1]-1][i[0]-1] = i[2]
    
    # floyd warshall 알고리즘
    for i in range(n):
        for j in range(n):
            for k in range(n):
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
    
    # 최단거리 탐색
    minPath = INF
    for i in range(n):
        minPath = min(minPath, graph[s-1][i] + graph[i][a-1] + graph[i][b-1])
    return minPath