본문 바로가기

전체 글154

2020년 계획 알고리즘 : solved.ac 플레 1찍기 or 500문제 이상 풀기 리눅스 : 리눅스 커널 패치 1개 이상 작성하고 Accept 받기, 그 전까지 겁나 삽질하기 깃허브 : 1일 1커밋 2020. 1. 2.
리눅스 커널 입문에 도움이 될만한 것들 리눅스 커널 1도 모르는 학생이 쓴 거라 도움이 안 될 수도 있습니다 어렸을 때부터 리눅스 커널을 공부하는 데에 로망이 있었는데, 당시에 중딩이던 나는 엄청난 진입 장벽에 좌절하고 이론 책만 조금 공부했던 기억이 있다. (그리고 이것도 제대로 이해 못했다 ㅋㅋㅋ) 그래도 한 5년 동안 머리가 자랐으니, 다시 도전해보고 싶어서 며칠 전부터 구글링을 엄청나게 했다. 아, 물론 리눅스 커널의 대략적인 작동 방식, 자료구조를 정리한 책은 많다. 그런데 그것도 중요하지만 직접 소스코드를 분석해보고 싶었다. 물론 5년 전이나 지금이나 진입 장벽은 높은 것 같다 아무튼 간에, 내가 느낀 리눅스 커널 입문의 어려운 점은 : 1. 우선 어디서부터 시작해야 할지 모른다. 내가 "프로세스 관리"에 관심이 있어서 소스를 찾아.. 2020. 1. 2.
나의 대학교 1학년, 2019년 회고 나는 원래 이런 걸 하는 사람이 아닌데, 내가 존경하시는 분들이 많이들 회고를 올리셔서 나도 올해 한 해를 다시 되돌아보려고 한다. (스무살이 쓴거라 별 영양가가 없을 수 있다.) 1~2월 : 이전까지 알바를 한 번도 해본 적이 없었는데, 올해 1~2월을 기점으로 택배 상하차, 극장 알바를 시작해보면서 조금이나마 사회생활을 경험하게 된 것 같다. 그전까지는 학교에서 (위아래 없이..) 지내다보니 처음엔 어색했는데, 사회생활에서 필요한 눈치와 책임감을 기르게 된 것 같다. 3~6월 (1학기) : 처음 학교에 들어가서 완전 신났던 시기다. 과 MT부터 시작해서 술자리란 술자리는 다 참여하면서 친구들이랑 친해지고, 맘껏 놀았다 ㅋㅋㅋ 내 인생에서 제일 신나게 논 것 같다. 물론 그만큼 나한테 투자하는 시간이 .. 2019. 12. 29.
[KOI 초등부] BOJ 17616 등수 찾기 (2019 2차 대회) 이 풀이는 homebody님의 풀이를 보고 이해하며 작성한 것입니다. 처음에는 줄세우기 문제와 비슷하다고 생각했는데, 누가 더 잘 하고, 못하고에 맞춰서 정렬하는 건 쉽지만 그 범위를 알아내는 건 어려웠다. 그래서 반대로 root 노드로부터 떨어진 거리를 각각 기록하고, 각 정점의 자식 수를 기록해서 같은 거리에 있는 그래프들의 순위 변화에 따라서 어떻게 등수가 바뀌는지 계산하려고 했지만 구현이 까다로울 뿐더러 연결 그래프가 2개 이상인 경우에는 답도 구할 수 없어서 결국 풀이를 봤다. 아이디어는 간단한데, 그래프를 두 개로 분리해서 "나보다 등수가 높은 그래프"와 "나보다 등수가 낮은 그래프"로 관리하는 것이다. (이걸 어떻게 생각했을까...) 예를 들어서 경민이가 형곤이보다 등수가 높다고 해보자. 그.. 2019. 12. 28.
[KOI 초등부] BOJ 17614 369 (2019 2차 대회) 17614번: 369 민수는 같은 반 친구들과 369게임을 하고 있다. 369게임은 여러 명이 원형으로 둘러 앉아 시작 위치의 사람이 1을 외치며 시작된다. 이후 시계방향으로 돌아가며 2, 3, 4와 같이 1씩 증가된 수가 자기 수가 된다. 순서대로 돌아오는 자기 수에 3, 6, 혹은 9가 포함되어 있지 않다면 그 수를 말해야 하며, 3, 6, 혹은 9가 포함되어 있으면 그 개수만큼 박수를 쳐야 한다. 이 규칙을 지키지 못하면 게임이 종료된다. 민수는 369게임이 N까지 규칙 www.acmicpc.net 문제 유형 : ad-hoc or 간단한 DP 369 게임에서 N번째 숫자를 부르기 까지 박수를 몇 번 쳐야하는지 구하는 문제로, 다음과 같이 풀었다. 1. 임의의 숫자 K에 대해서 박수를 치는 횟수를 구.. 2019. 12. 28.
[KOI 초등부 / 메모리초과] BOJ 17609 회문 (2019 1차 대회) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 유형 : DP라고 생각했는데 좀 더 생각해봐야겠다. DP로 풀려니까 N = 100,000인데다가 O(N^2)이라 안풀린다. 흠. 2019. 12. 25.
[KOI 초등부] BOJ 17608 막대기 (2019 1차 대회) 불러오는 중입니다... 문제 유형 : 개인적으론 ad-hoc인듯 해설 : 먼저 막대기의 길이를 배열에 저장, 막대기의 개수가 N이라고 했을때 오른쪽에서 바라보므로 N-1, N-2, ... , 0 이렇게 마지막 원소부터 차례대로 순회를 하는데, "지금까지 순회한 막대기 중 가장 긴 것"보다 길이가 긴 경우에만 개수를 더해주면 된다. 지금까지 순회한 막대기 중 가장 큰 것 보다 작거나 같은 경우는 눈에 보이지 않기 때문 문제의 테스트 케이스를 직접 그려보면 이해가 잘 된다. 구현 : 2019. 12. 25.
[NetworkFlow] 네트워크 유량과 포드 풀커슨 알고리즘 이번 글에서는 네트워크 유량 문제 (네트워크 플로우)와 포드 풀커슨 알고리즘에 대해 알아보자. 네트워크 유량 문제 (Network Flow Problem) 원래의 그래프는 간선을 거리, 비용으로 생각했다면, 유량 네트워크 (Flow Network)에서는 단방향 그래프에서 간선의 가중치를 최대로 흐를 수 있는 용량(capacity)과 실제로 흐르는 유량(flow)으로 생각한다. 이게 무슨 말이냐 하면 A에서 B로 가중치가 10이 존재한다면, A에서 B로 흐를 수 있는 최대 물의 양이 10이라고 해석할 수 있다. (실제로 물이 얼마나 흐르는지는 우리가 얼마나 흘려보내냐에 따라 다르다.) 이제 유량 네트워크가 뭔지 대충 느낌을 알았는데, 그래서 네트워크 유량이 뭐냐? 하면 네트워크 유량은 이 유량 네트워크에서.. 2019. 12. 24.
동적 프로그래밍(Dynamic Programming)의 개념 DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다. Dynamic Programming 동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다. 위의 코드를 한 번 읽어보자. 1 = 1 2 = 2 + 1 3 = 3 + 2 + 1 ... 100 = 100 + 99 + 98 + ... + 3 + 2 + 1 이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므.. 2019. 10. 7.

티스토리툴바