이분 매칭 알고리즘은 유량 그래프의 특수한 형태이다. 유량 그래프는 다음 포스팅에서 다루기로 하고... 이분 매칭 알고리즘에 대해 알아보자. 이분 매칭 알고리즘을 알아보기 전에, 이분 그래프에 대해 먼저 알고 넘어가야 한다. 이분 그래프란 정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 말한다. 위의 그림에서 보면 파란색 노드의 집합을 X, 빨간색 노드의 집합을 Y로 표현할 수 있고, 따라서 위의 그래프는 이분 그래프이다. 이분 매칭 알고리즘은 위와 같은 이분 그래프에서 최대 매칭의 개수를 찾는 것과 같다. 매칭이란 간선 하나를 선택하는 것을 말하는데, 예를 들어 그림에서 A와 a를 연결하는 간선을 선택하면 (A, a)라는 매칭이 생기는 것이다..
https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 2020 카카오 공채 1차 코딩테스트 7번 문제로 출제된 블록 이동하기 문제이다. 이렇게 맵을 탐색하는 문제는 굉장히 흔한데, 그런 문제들과 이 문제의 가장 큰 차이점은 바로 로봇이 한 칸이 아닌 두 칸을 차지한다는 점이다. 또한 로봇이 이동할 때에도 두 칸이 모두 이동할 수 있어야 한다는 제약이 걸려있다. 또 이러한 점을 고려하여 로봇이 회전까지 할 수 있다... 위의 조건들을 고려..
https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 작년 하반기 카카오 공채 문제로 나왔던 표 병합 문제이다! union-find 문제인데 당시에 문제를 풀 때는 거의 마지막쯤에나 깨달아서 결국 효율성 점수를 받지 못했었다... union-find 알고리즘 자체가 어려운 편은 아니라 구현만 꼼꼼하게 한다면 충분히 풀 수 있는 문제다. 구현 문제인 만큼 문제를 꼼꼼히 읽고 시작하자! 마치 엑셀을 연상시키는 것 같은 문제였는데, 엑셀과는..
https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 카카오 인턴십 문제로 출제된 코딩 테스트 공부이다! dp 문제는 언제나 구현하는 시간보다 생각하는 시간이 길어지는 것 같다. 나는 항상 dp 문제와 그리디 문제를 헷갈려하는데, 풀 때 먼저 그리디 하게 풀려고 했을 때 직관적인 풀이가 잘 떠오르지 않으면 dp로 푸는 것 같다. 코딩 테스트 공부 문제는 완전 탐색과 dp를 결합한 문제이다. 문제 요구 사항을 살펴보자. 문제에서 초기 알..
이번 주는 핀토스의 마지막 주차인 파일 시스템이다. 보통 핀토스는 프로젝트 2와 3이 가장 어려운 편이고, 마지막 프로젝트 4가 쉬운 편이라고 하는데 그렇다고 만만할 정도는 아니었다... 그래도 핀토스에 대한 흐름이 어느 정도 잡혀있어서 그런지 초반에 개념을 잡고 나니 구현은 생각보다 빠르게 진행됐다. 초반에 개념 잡는 게 어려우니 오늘 포스팅은 파일 시스템의 기본 개념에 대해서 다뤄보려고 한다! Inode 먼저 핀토스가 제공하는 기본 코드에 대해서 살펴보자. 커널에서 파일이나 directory에 접근할 때 항상 inode라는 구조체를 거쳐서 접근하게 된다. inode 구조체를 살펴보자! /* In-memory inode. */ struct inode { struct list_elem elem;/* El..
이번 포스팅에서는 개념에 관한 정리보다는 프로젝트를 진행하면서 궁금했던 점을 위주로 정리해보려고 한다! 프로젝트 3을 진행하다 보면, anon page나 file page에서 swap in 함수로 load_segment 함수를 사용할 일이 생긴다. 이때 load를 할 주소 값을 user virtual address로 넘겨주는 경우와 kernel virtual address로 넘겨주는 경우의 차이가 발생한다. 이 차이가 왜 발생하는지, 또 user virtual address의 경우 kernel virtual address와의 mapping 정보를 page table에 추가해 주었기 때문에 참조가 가능한데, kernel virtual address는 어떻게 바로 참조가 가능한지에 대해 알아보았다. User..
드디어 대망의 프로세스 관련 시스템 콜이다..! 앞에서 소개했던 파일 입출력 관련 시스템 콜은 거의 래핑 함수 위주여서 구현이 어렵지는 않았던 반면, 프로세스 관련 시스템 콜들은 구현할 양도 앞의 포스팅에 비해 많은 편이고 무엇보다도 개념 자체가 쉽게 와닿지 않아 많이 어려웠다고 느꼈다. 프로세스와 관련된 시스템 콜은 fork, exit, exec, wait 으로 총 네 가지가 있다. 이 파트가 특히 어려웠던 점은, 네 개의 시스템 콜 중 하나라도 제대로 구현이 되어있지 않으면 거의 모든 프로세스 시스템 콜 테스트가 통과되지 않아 네 개를 모두 구현하고 나서야 결과를 확인할 수 있었다는 점이다. 구현할 양도 꽤나 많은 편이라 네 개를 모두 구현하고 나서 문제가 생기면 그 문제를 찾기가 꽤나 힘들어진다....
이번 주는 가상 메모리와 관련된 과제를 진행하였다. VM 파트는 크게 Memory Management, Anonymous Page, Stack Growth, Memory Mapped Files, Swap in/out으로 구분되며 extra로 Copy-on-Write까지 있다. 이번 포스팅에서는 위의 내용들 중에서 Memory Management 파트에 대해 다뤄볼 예정이다. User Pool & Kernel Pool 사실 memory management 파트에서는 구현할 부분이 다른 파트에 비해 많지는 않은 편이다. 다만 초반에 코드의 흐름을 잡기가 힘들고, 가상 메모리 개념 자체가 잘 와닿지 않기때문에 핀토스의 메모리 구조와 프레임 할당 방식에 관해 중점적으로 다뤄볼 것이다. 우선 핀토스는 아래 그림과..
핀토스 프로젝트 2의 시작은 시스템 콜부터다. 사실상 argument passing은 몸풀기... 문제는 몸풀기 수준이었던 argument passing조차도 쉽지만은 않았다는 거..! 이번 포스팅에서는 시스템 콜 중에서 파일 입출력과 관련된 시스템 콜들을 다뤄볼 예정이다. 저번에 웹 프록시 서버를 구현할 때 소켓을 파일로 추상화하여 소켓에게도 파일 디스크립터가 붙었는데, 이번에도 파일 디스크립터 개념을 사용한다. 파일 디스크립터와 관련해서는 다뤘던 포스팅이 있으니 참고하자. https://codable.tistory.com/19 [Computer System] File Descriptor File Descriptor 유닉스 시스템에서는 많은 것들을 파일로 관리한다. 정규 파일들뿐만 아니라 디렉터리, 소..
핀토스 프로젝트 1의 extra 과제이다. multi-level feedback queue scheduler의 구현인데, 일단 저번 포스팅에서 소개했던 스케줄러들과 비교해서 어떤 점이 좋은지 살펴보자. 기존 Priority Scheduler의 문제점 기존 우선순위 스케줄러는 저번 포스팅에서도 언급했다시피 우선순위가 낮은 작업이 계속해서 순서가 밀려 CPU를 얻지 못하는 Starvation 현상이 발생할 수 있다는 점이 있었다. 물론 핀토스에서 구현하는 우선순위 스케줄러에서는 priority donation도 있어 우선순위가 낮은 작업도 충분히 실행될 기회를 잡을 수 있지만, 특별히 락을 소유하지 않고 우선순위도 낮은 작업들은 이러한 조정도 받지 못할 수 있다. 이로 인해 task들의 평균 대기 시간이 길..
