풀캠정글러

01.06 ~ 01. 12 아호-코라식 마지막으로 아호코라식을 배우는 것으로 새 알고리즘의 공부를 마쳤다. 하산(?)한 뒤로는 계획대로 테크닉을 쌓기 위해 실버-골드 DP 문제를 풀었는데, 갑자기 이것저것 사건이 터져 결과적으로 푼 문제가 적다. 매일 일어나서 워밍업 겸 한두문제만 풀고 외면한 느낌 원래 계획은 일주일~10일 안에 핀토스 프로젝트 3을 끝내고 4까지 미리 끝내는 것이었다. 알고리즘 공부야 집에서 데탑으로도 할 수 있는거니 한 일주일 여유롭게 코테준비만 하면서 설 연휴를 보낼 계획이었는데, 갑자기 나만의 무기 관련해서 신경써야 할 일이 너무 많아졌다. 같은 공지를 보고도 많은 사람들이 나와는 다른 방식으로 받아들인 것 같아 아쉽다. 계획을 실천하지 못한건 반성하고는 싶지만 사실 정글 분위기..

이번주에도 과제의 구현에 집중하면서 필요한 깊이만큼 이론을 배워나가며 진행했다. 커맨드라인 파싱은 할만했다고 생각한다. 어디에서 무엇을 해야 할지를 제시해주었기 때문에, 이 기능이 왜 필요하고 어떤 방식으로 구현해야 하는지에 초점을 맞추면 결국 남는 것은 '잘 구현하는 것' 뿐이어서 시키는 대로 잘 구혔했다. 그런데 'Implement user memory access' 부터 무언가 잘못되었음을 느꼈다. 분명 VM은 프로젝트 3의 영역이라고 믿고 있었는데 이렇게 발을 걸치니 VM 관련 공부를 하고 와야하나, 아니면 그냥 함수 따라 올라가며 대강 어떻게 작동하는지말 알고 넘어가야 하나부터 고민이 많았다. 결국 이후 구현할 수많은 시스템콜의 구현량이 두려워 후자를 택하고, '커널 영역을 유저 영역 뒤(더 큰..

와! 목표달성! 코테를 뚫는데에는 골드 상위 문제를 푸는것으로도 충분하다는 말이 있다. 코테를 뚫어본적은 없지만 아마도 맞는 말이라고 생각한다. 그럼에도 굳이 위로 올라가면서 새 알고리즘을 배운 것은, 코딩테스트가 아니라 실제 개발에서 쓰일 알고리즘들이 보였기 때문이다. 문자열 알고리즘은 텍스트가 쓰이는 온갖 곳에 다 활용될 것이고, 이분매칭, 최대유량은 네트워크 플로우라는 이름처럼 네트워크 연결의 우선도를 부여하는 데에 쓰일 수 있을 것이다. 각종 트리의 자료구조는 말할 것도 없고. 수학쪽은 솔직히 재밌어서 푼건데 암호와 보안에 활용될 수도 있다 본다. 개발자는 끊임없이 새 기술을 공부해야 한다는 말이 있다. 나는 이 말이 단순히 새로 나온 기술 스택 정도에만 해당되는 것이 아니라고 생각한다. 알고리즘..

12.30 ~ 01.05 고속 푸리에 변환 (FFT) 이번주는 PintOS 프로젝트 2가 진행중이다. 다음주 화요일까지라 아직도 하고 있다. 목요일에 부스터샷 맞은 뒤 3일밤낮을 뻗어서 아무것도 못하다가 월요일이 되어 강의실에 오니, 프로젝트 2의 방대한 구현량과 난이도에 숨이 턱 막혔다. 매일매일 하고 있지만 일주일이 지난 아직까지도 반도 못했다는 느낌이 든다. 알고리즘에 많은 시간을 투자했다가는 멸망각이 보이는 상황이라 이번주는 전부터 익히기로 맘먹고 있었던 FFT 딱 하나만 파보기로 맘먹었다. 하루 날잡고 FFT 이론을 보고, 로직을 쭉 읽어가며 파이썬 코드로 구현해 라이브러리를 만들었다. 시작하기 전엔 쫄았지만 푸리에 변환 자체는 학부때 배웠던 거라 의외로 머리에 잘 들어왔던 것 같다. 그 후로는..

12.23 ~ 12.29 lazy propagation 머지 소트 트리 펜윅 트리 오프라인 쿼리 / mo's min cost max flow 이번주는 PintOS 프로젝트 1을 진행했다. OS란 무엇인가 잘 설명된 영상 강의들을 몇시간 들었는데, 아무래도 영상이란게 자기가 글을 읽는것에 비해서 정보의 밀도가 낮다보니 그리 집중이 되지가 않았다. 그래서 남는 머리와 손으로 알고리즘 문제를 풀어가면서 듣고 강의는 거의 한귀로 듣고 한귀로 흘린 것 같다. 이걸 멀티태스킹이라 해도 되나? 대학생 시절이랑 똑같은듯... 세그먼트 트리의 갱신을 필요한 시점까지 늦춰 효율을 개선한 lazy propagation 정렬된 부분수열을 저장하는 머지 소트 트리 크기 n으로 가볍지만 부분합에 대해서는 세그먼트 트리와 같은 기..

각 파트의 문제점과 그것을 개선하기 위한 구현 방향을 정리해보았다. 각 파트를 어떻게 구현했는지는 따로 포스트로 정리하고 있다. https://uneducatedjungler.tistory.com/141 [KAIST PintOS Project 1] 1. sleep and awake KAIST 핀토스를 기반으로 만든 코드는 재배포가 불가능하다고 프로젝트 가이드라인의 legal issue에 명시되어있다. 라이센스를 찾아봤는데 프로젝트에 따라 자기가 작성한 부분도 배포가 불가능하 uneducatedjungler.tistory.com https://uneducatedjungler.tistory.com/142 [KAIST PintOS Project 1] 2. priority scheduling priority s..

synchronization 지난 단계에서는 선입선출의 queue 구조였던 ready_list를 스레드의 priority에 따르는 heap 구조로 바꾸어 보다 효율적인 스케줄링을 하도록 개선했다. 그런데 이와 같은 아이디어로 똑같은 개선이 가능한 list가 둘 더 있다. 바로 세마포어의 waiters와 컨디션의 waiters이다. semaphore.waiters는 semaphore를 갖기 위해 대기중인 스레드를 elem으로 갖는 list이고, cond.waiters는 condition을 갖기 위해 대기중인 semaphore의 list인데, 둘 모두 개선 전의 ready_list처럼 선입선출의 구조를 갖고 있다. ready_list때와 마찬가지로 이는 우선도가 높은 스레드가 낮은 스레드를 기다리는 문제를 ..

priority scheduling 지난 단계에서는 CPU를 정말로 쓸 스레드만 ready_list에 삽입하는 sleep & awake의 구현으로 불필요한 토스를 줄여 기능을 개선했다. 이번 단계의 목표는 수많은 ready 상태의 대기중인 스레드 중 우선도가 높은 순서대로 사용하도록 하는 기능의 구현이다. 간단히 말해 ready_list를 queue에서 priority에 따르는 heap으로 바꾸는 것이 목적이다. 순서 1 ~ 2 스레드간의 우선도를 따지기 위해 각 스레드마다 priority라는 값을 가진다. 기존에 선착순으로 ready_list에 진입하던 구조를 개선하여 이 priority에 따라 ready_list가 정렬되도록 한다면, 항상 ready_list의 first만 취하는 현재의 알고리즘대로 ..

KAIST 핀토스를 기반으로 만든 코드는 재배포가 불가능하다고 프로젝트 가이드라인의 legal issue에 명시되어있다. 라이센스를 찾아봤는데 프로젝트에 따라 자기가 작성한 부분도 배포가 불가능하다고 한다. 따라서 코드는 블로그에 첨부하지 않는다. 이걸 코드없이 정리하려니 답이 없어서 내가 구현을 진행한 부분들을 순서대로 기록해봤다. sleep and awake 기존 timer는 busy waits이 발생하는 구조를 갖고 있었다. 알람 시각에 도달하기를 그저 기다리는 스레드들이 계속 서로에게 CPU 사용 권한을 넘겨주고, 알람 시각이 아니라면 다시 다른 스레드에게 CPU 사용 권한을 넘기는, 이러한 무의미한 토스를 반복하며 CPU의 사용 권한이라는 공유자원에 낭비가 일어나는 것이다. 각 스레드들이 기상시..

친구에게서 이런 말을 들었다. 핀토스는 엄청 빡센데 그래도 하려면 할만한가 싶다가, 후반부에 지옥도가 펼쳐진다. 정글이 끝나기까지 아직 2달 반정도의 시간이 남아있지만, 뭔가를 따로 할 여유는 이제 그리 없다는 의미일 것이다. 원래 목표는 1월 중순쯤에 P1, 2월 나만의무기 시작 전까지 D5를 다는 것이었다. 하지만 지금 생각해보면 늦어도 1월 첫째주 안에는 D5까지 가서 알건 다 알고 내려와 스킬적인 부분을 키워야 하겠다는 생각이 든다. 요즘은 지식을 늘고있지만 그걸 다루는 테크닉은 한참 못미치는 것을 느끼고 있다. 지금은 새로운 심화 알고리즘들을 배우는 단계이다 보니 문제해결력이 없어도 알고리즘만 이해하면 기초문제를 쑥쑥 풀 수 있지만, 응용과 조합을 요구하는 다이아 문제들은 거의 손도 못대겠다. ..