요약 프로그래밍 언어로 작성된 “소스 파일”을 컴파일러에게 먹여주면 컴파일러는 이것을 꼭꼭 씹고 뜯고 맛본 후, 실행 파일 형태로 뱉어냄. 실행 파일이 바로 CPU가 직접 실행할 수 있는 기계 명령어 임. 즉, 컴파일러는 “번역기” 이자 “텍스트 처리 프로그램” 이라고 생각할 수 있음. 컴파일러는 소스 파일의 각 항목을 잘게 쪼개어 토큰화 함. 소스 코드에서 토큰을 추출하는 과정을 어휘 분석(lexical analysis) 라고 함. 토큰을 가지고 그 의도를 표현해야만 함. 특정 토큰 키워드에 따라 컴파일러는 문법 오류를 보고할 수 있음. 이 과정을 해석(parsing) 이라고 함. 컴파일러는 해석을 통한 구조를 트리로 표현함. 구문 트리에서 이상이 있는지 확인함. 이 단계를 통과하면 컴파일 오류가 없다..
요약 (Section 1.1 여러분이 프로그래밍 언어를 발명한다면?) CPU는 단순하지만 빠르다. 프로그래머는 단순하지만 빠른 CPU를 다루기 위해 천공 카드로 컴퓨터 작업을 제어함. 하지만 이는 CPU 관점의 코드일 뿐 인간이 이해하기 어려움 어셈블리어를 통해 인간이 인식할 수 있는 ‘기계 명령어’ 를 이용하여 CPU를 제어하게됨. 하지만 여전히 어셈블리어는 저수준 언어임. 저수준 언어는 매우 추상화되어 있어 구체적으로 ‘우리가 원하는 동작’ 을 하려면 세부 사항들을 하나하나 다 알려줘야 함. 고급 프로그래밍 언어를 통해 CPU를 동작시키기 위한 ‘추상적인 표현’ 을 ‘구체적인 표현’으로 자동 변환할 수 있게 됨. 프로그래밍 언어를 통해 단순한 문장을 표현하기도 하지만, 이들이 중첩되어 복잡한 문장을 ..
수강 목적 지난 COMP1500 수업 이후 많은 것을 얻어갔다고 생각했기 때문에 POCU 아카데미의 로드맵을 쭉 따라가서 "전문 프로그래머가 되기 위한" 과정을 밟아가고 싶었다. 현재 총 7개의 로드맵이 열려있는데, 이제 2개의 로드맵이 끝났다. 소프트웨어 공학용 수학 수업의 설명에서 컴퓨터를 이해하는데 중요한 수학을 다루고, 특히 논리적 사고를 강조한다고 한다. 본인은 학창 시절 수학 수업을 매우 좋아했다. 오랜만에 수학 수업을 듣게되어서 설레기도 했고 다시 복습도 하고 이제는 프로그래머로서 알아야할 논리적 사고를 학습하고 수학 지식들을 정리하여 배울 수 있다는 점이 매력적으로 다가왔다. 물론 이제 3년차 개발자이기 때문에 왜 굳이? 직무에 필요한 기술들을 더 공부하는게 더 중요하지 않아? 라고 생각할..
17. 어려운 연습문제 17.21 막대 그래프의 부피 히스토그램(막대 그래프)을 상상해 보자. 누군가가 히스토그램 위에서 물을 부었을 때, 이 그래프가 저장할 수 있는 물의 양을 계산하는 알고리즘을 설계하라. 단, 막대의 폭은 1이라고 가정하자. 17.26 드문드문 유사도 서로 다른 단어로 구성된 두 문서의 유사도는 단어들의 교집합의 크기 나누기 합집합의 크기로 정의할 수 있다. 즉, 정수로 이루어진 두 문서 {1, 5, 3}과 {1, 7, 2, 3}의 유사도는 0.4가 된다. 왜냐하면 두 문서의 교집합의 크기는 2이고 합집합의 크기는 5이기 때문이다. 유사도의 밀도가 굉장히 ‘희박’할 것 같은 문서가 굉장히 많이 주어져 있다(각 문서는 ID로 표현된다). 여기서 희박하다는 뜻은 임의의 두 문서의 유사도..
17. 어려운 연습문제 17.16 마사지사 인기 있는 마사지사가 있다. 마사지 사이에 15분간 휴식이 필요하므로 마사지 예약이 연달아 들어온다면 그중에서 어떤 예약을 받을지 선택해야 한다. 연달아 들어온 마사지 예약 리스트가 주어졌을 때(모든 예약 시간은 15분의 배수이며 서로 겹치지는 않고 한번 예약이 되면 변경이 불가능하다), 총 예약 시간이 가장 긴 최적의 마사지 예약 순서를 찾으라. 17.19 빠진 숫자 찾기 1부터 N까지 숫자 중에서 하나를 뺸 나머지가 정확히 한 번씩 등장하는 배열이 있다. 빠진 숫자를 O(N) 시간과 O(1) 공간에 찾을 수 있겠는가? 만약 숫자 두 개가 빠져 있다면 어떻게 찾겠는가?
17. 어려운 연습문제 17.12 BiNode BiNode라는 간단한 자료구조가 있다. 이 자료구조 안에는 다른 두 노드에 대한 포인터가 들어 있따. public class BiNode { public BiNode node1, node2; public int data; } BiNode 자료구조는 이진 트리를 표현하는 데 사용될 수도 있고(node1은 왼쪽 노드를, node2는 오른쪽 노드를 가리키게 만들면 된다), 양방향 연결리스트를 만드는 데 사용할 수도 있다(node1은 이전 노드를, node2는 다음 노드를 가리키게 만든다). BiNode를 사용해서 구현된 이진 탐색 트리를 양방향 연결리스트로 변환하는 메서드를 작성하라. 값의 순서는 유지되어야 하며 모든 연산은 원래 자료구조 안에서(in-place..
17. 어려운 연습문제 17.9 k번째 배수 소인수가 3, 5, 7로만 구성된 숫자 중 k번째 숫자를 찾는 알고리즘을 설계하라. 3, 5, 7이 전부 소인수로 포함되어야 하는 건 아니지만 3, 5, 7 외에 다른 소수가 포함되면 안 된다. 이 조건을 만족하는 숫자의 예를 몇가지 나열해보면 1, 3, 5, 7, 9, 15, 21이 있다. 17.10 다수 원소 다수 원소란 배열에서 그 개수가 절반 이상인 원소를 말한다. 양의 정수로 이루어진 배열이 주어졌을 때 다수 원소를 찾으라. 다수 원소가 없다면 -1을 반환하라. 알고리즘은 O(N) 시간과 O(1) 공간 안에 수행되어야 한다.
17. 어려운 연습문제 17.8 서커스 타워 어느 서커스단은 다른 사람 어깨 위에 다른 사람이 올라서도록 하는 ‘인간 탑 쌓기’를 공연한다. 실질적이면서도 미학적인 이유 때문에 어깨 위에 올라서는 사람은 아래 있는 사람보다 가벼우면서 키도 작아야 한다. 단원의 키와 몸무게가 주어졌을 때, 최대로 쌓을 수 있는 인원수를 계산하는 메서드를 작성하라. 17.23 최대 검은색 정방행렬 정방형의 행렬이 있다. 이 행렬의 각 셀(픽셀)은 검은색이거나 흰색이다. 네 가장자리가 전부 검은색인 최대 부분 정방행렬을 찾는 알고리즘을 설계하라.
17. 어려운 연습문제 17.3 임의의 집합 길이가 n인 배열에서 m개의 원소를 무작위로 추출하는 메서드를 작성하라. 단, 각 원소가 선택될 확률은 동일해야 한다. 17.5 문자와 숫자 문자와 숫자로 채워진 배열이 주어졌을 때 문자와 숫자의 개수가 같으면서 가장 긴 부분배열을 구하라.
17. 어려운 연습문제 17.1 덧셈 없이 더하기 두 수를 더하는 함수를 작성하라. 단, +를 비롯한 어떤 연산자도 사용할 수 없다. 17.2 섞기 카드 한 벌을 ‘완벽히’ 섞는 메서드를 작성하라. 여기서 ‘완벽’의 의미는, 카드 한 벌을 섞는 방법이 52!가지가 있는데 이 각각이 전부 같은 확률로 나타날 수 있어야 한다는 뜻이다. 단, ‘완벽한’ 난수 생성기(random number generator)는 주어져 있다고 가정해도 좋다.
16. 중간 난이도 연습문제 16.23 Rand5로부터 Rand7 rand5()를 사용해서 rand7() 메서드를 구현하라. 즉, 0부터 4까지 숫자 중에서 임의의 숫자를 반환하는 메서드를 이용해서 0부터 6까지의 숫자 중에서 임의의 숫자를 반환하는 메서드를 작성하라. 16.24 합이 되는 쌍 정수형 배열이 주어졌을 때, 두 원소의 합이 특정 값이 되는 모든 원소 쌍을 출력하는 알고리즘을 설계하라. 16.25 LRU 캐시 가장 오래된 아이템을 제거하는 ‘최저 사용 빈도(least recently used)’ 캐시를 설계하고 구현하라. 캐시는 특정 키와 연관된 값을 입력하거나 읽어 들일 수 있어야 하며 그 크기는 최대로 초기화되어 있다. 캐시가 꽉차면 가장 오래된 아이템을 제거하고 새 아이템을 입력해야 한..
16. 중간 난이도 연습문제 16.20 T9 과거의 핸드폰에서는 문자 입력을 돕기 위해 각 숫자에 0~4개의 알파벳을 대응시켰다. 이에 따라 어떤 수열이 주어지면 그 수열에 대응되는 단어 리스트를 만들 수 있었다. 유효한 단어 리스트(여러분이 원하는 방식으로 자료구조가 주어진다)와 어떤 수열이 주어졌을 때, 해당 수열에 매핑되는 단어 리스트를 출력하는 알고리즘을 작성하라. 각 숫자에 대응되는 알파벳은 다음과 같다. 1 2 (abc) 3 (def) 4 (ghi) 5 (jkl) 6 (mno) 7 (pqrs) 8 (tuv) 9 (wxyz) 0 16.21 합의 교환 정수형 배열 두 개가 주어졌을 떄, 각 배열에서 원소를 하나씩 교환해서 두 배열의 합이 같아지게 만들라. 16.22 랭턴 개미 검은색과 하얀색 셀(..
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
