크루저의 쉼터

오늘은 수학 문제들로 준비해봤다. 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net 11051번 이항 계수 2 문제는 DP를 적용할 수 있는 문제다. 문제에서는 (N, K) % 10007을 요구하고 있다. 하지만 우리가 알고 있는 공식 (N, K) = N! / K!(N-K..

오늘 문제 1541번은 보통 난이도를 가진 그리디 알고리즘 문제이다. 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제를 접근하는 방법은 간단하다. 처음 "-"의 위치를 기준으로, 이전에 나타나는 숫자는 더하고, 이후에 나타나는 숫자는 빼면 된다. 다만 C++ 구현에서 입력을 어떻게 처리해야 할지에 대해 고민하는데 시간이 많이 소요됐다. scanf로 전체 스트링을 받는 다음 strtok를 이용하는 방법, 또는 stringstream, sprintf를 활용하는 방법을 생각했지만 코드가 복잡해졌다. 결론..

이 글에서는 대학교 수업 중 "네트워크 프로그래밍"의 단골 과제인, C와 TCP를 기반으로 HTTP 서버를 작성한다. (안타깝게도) "C, C++를 이용한 웹서버"라는 키워드로 블로그 유입이 많이 되고 있어 복습할 겸 작성해봤다. 오늘 필자가 개발하고자 하는 HTTP 서버는 리눅스에서 동작할 수 있는 간단한 서버로, 서버 프로그램(a.out)이 존재하는 디렉터리를 기준으로 파일을 접근할 수 있는 서버다. 예를 들어 a.out이 /home/user/c-serv/에 있고, 8000번으로 bind 한다면 브라우저에서 localhost:8000/index.html을 요청하면 /home/user/c-serv/index.html 파일을 반환하고, 브라우저에서 localhost:8000/index.css를 요청하면 ..

이번 파트는 PL을 듣지 않은 학생이지만 답할 수 있으면 좋은 질문을 기출문제에서 선별하여 가져왔다. [기출편] KQ. 부동소수점(IEEE 754)의 sign bit, exponent, mantissa에 대해 설명하라. 만약 16-bit mantissa, 8-bit exponent를 사용한다면 가능한 양의 normal한 최대, 최소값은 무엇인가? KQ. 자바에서 public, protected, private 키워드가 있는데 아무것도 안 쓸 경우 default로 적용되는 범위는? KQ. Static typing과 dynamic typing의 차이점은? C++/JAVA은 어떤 typing을 사용하는가? KQ. C++에서 서로 다른 타입의 오브젝트를 가리키는 포인터를 사용할 수 있나? KQ. 전역 변수 사용..

이 파트에서는 이산수학, 선형대수, 확률 및 통계 일부를 다룬다. * 참고 교재: Discrete mathematics and its applications (Kenneth H. Rosen), Introduction to Linear Algebra (James Defranza), Fundamentals of Applied Probability and Random Processes (Oliver C. Ibe) * 알림 사항: 당시 질문을 작성할 때 필자가 확률 및 통계를 배우기 전이기 때문에 관련 질문이 부족하거나 없다. [기출편] Q. injection(one-to-one), surjection(onto), bijection(one-to-one correspondence)을 설명하라. 기출+: Bijec..

이 파트에서는 순수하게 형식 언어 및 오토마타 과목에서 물어볼 수 있는 질문을 나열한다. (컴파일러 과목은 제외한다는 의미입니다) 이 파트는 기출을 포함하지 않는다. 그 이유는 KAIST 기출문제가 이론 질문보다는 수학적으로 또는 주어진 Grammar을 갖고 푸는 문제이기 때문이다. 굳이 이론 질문을 뽑는다면 촘스키 위계(Chomsky Hierarchy)를 외워가는 것을 추천한다. * 참고 교재: Introduction to the Theory of Computation (Michael Sipser) [핵심편] Q. Finite Automata란 무엇인가? Language란 무엇인가? Regular Language란 무엇인가? Q. DFA와 NFA가 무엇인지 설명하라. Q. DFA의 Formal Defi..

컴퓨터 네트워크에서는 잘 알려져있는 TCP, UDP와 관련된 질문이 나올 확률이 높다. * 참고 교재: Computer Networking: A Top-down Approach (Jim Kurose) [기출편] Q. OSI 7계층, 각 계층의 역할에 대해 자세히 설명해보라. 각 레이어에서 추가되는 헤더에 대해 설명하라. 기출+: OSI 7계층에 대해 설명하시오. Q. TCP와 UDP의 차이는 무엇인가? 대표적으로 어떤 곳에 쓰이는가? 기출+: TCP와 UDP의 차이점은? Q. RDT(Reliable Data Transfer)에 대해 간단히 설명하라. 기출+: TCP와 같이 protocol을 reliable하게 설계 하려면 무엇이 필요한가? Q. TCP의 3-way handshake (연결 성립, 연결 종..

운영체제 역시 매우 중요한 과목으로, 크게 CPU (프로세스), 메모리 (가상 메모리), 디스크 (파일 시스템) 파트로 나뉜다. 기출에 의하면 프로세스와 메모리 중심으로 면접이 이루어지는 것으로 보인다. * 참고 교재: Operating System Concepts, 8th Edition (A. Silberschatz) [기출편] Q. 프로세스와 스레드의 차이는 무엇인가? 스레드의 장단점은 무엇인가? 메모리 면에서 스레드는 어떤 점이 좋은지 프로세스의 문맥 교환 cost와 함께 설명하라. 기출+: Thread와 process의 차이는 무엇인가? 기출+: Thread와 Process의 차이는? Thread끼리 context switching 하는 과정에 대해 설명하시오. 같은 프로세스 내부의 thread들..

컴퓨터 구조에서는 Pipeline, Memory Hierarchy 내용을 다룬다. 개요에서 등장하는 ISA, Microarchitecture와 같은 개념을 물어볼 수도 있다. * 참고 교재: Computer Organization and Design: The Hardware/Software Interface, 5th Edition (David Patterson) [기출편] Q. 메모리 계층 구조를 간단히 설명하라. 외부(blackbox)에서 봤을 때 이상적인 메모리의 성능은 무엇인가? 기출+: 캐시가 필요한 이유는? Q. Hit time, Miss penalty, AMAT에 대해 정의하라. 기출+: Cache Hit Ratio에 대해 설명하시오. 기출+: 메모리 접근하는데 x 사이클이 걸리고, 캐시에 접..

이 파트는 매우 매우 중요하다. * 참고 교재: 쉽게 배우는 알고리즘, 개정판 (문병로) * 참고 교재: C++로 구현하는 자료구조와 알고리즘, 2판(M.T. Goodrich) [기출편] Q. 트리를 정의하라. 이진 트리, 이진 탐색 트리를 정의하라. 기출+: 그래프의 정의는? 트리의 정의는? 트리와 그래프의 관계는? 기출+: Binary tree란? binary tree에서 각 node는 두 개의 children을 갖거나 혹은 leaf node 이거나 둘 중에 하나라고 할 때, non-leaf node와 leaf node 개수의 관계식은 어떻게 되는가? Q. 트리, 이진트리의 순회방법에는 무엇이 있는가? 순회를 간단한 재귀코드로 표현해보라. 기출+: Tree traversal의 3 가지 방식을 설명하시..