programmer life guidance 101

> Hashing - 01 Hash Table 탐색과 삽입, 삭제를 지원하는 자료구조를 dynamic set이라고 부른다. 4장에서는 검색트리를 가지고 dynamic set을 구현했고, 또다른 한가지 구현 방법이 Hashing을 이용하는 것이다. 해시 테이블은 dynamic set을 구현하는 효과적인 방법의 하나이다. "적절한 가정"하에서 평균 탐색, 삽입, 삭제시간 O(1) 보통 최악의 경우 O(n) 해시 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 h : U -> {0, 1, 2, … , m-1} 여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합 키 k가 h(k)로 해싱되었다고 말한다. 즉, h() 해시 함수는 각 키에 대한 해시함수값을 그 키를 저장할 배열 ..

> 이진탐색트리(BST) Dynamic Set 집합이다. 여러개의 데이터의 집합인데, 그것들의 내용이 고정되지 않고, 생성과 삭제를 반복하면서 유동적인 집합이다. 아래와 같은 특징을 가진다. Dynamic Set, Dictionary 또는 Search Structure라고 불린다. 여러 개의 키(key)를 저장 다음과 같은 연산들을 지원하는 자료구조 INSERT - 새로운 키의 삽입 SEARCH - 키 탐색 DELETE - 키의 삭제 예: 심볼 테이블 일반적으로 구현할 때 배열 or 연결리스트를 사용한다. 각 동작에 있어서 다음과 같은 시간복잡도를 가진다. 정렬된 배열의 이진탐색 - O(logn) 정렬된 배열에서 원소를 insert, delete하면 나머지 원소들을 한칸식 shift - O(n) 정렬된 ..

> 트리와 이진트리 기본 트리(Tree) 계층적인 구조를 표현하기 위해 사용하는 자료구조 조직도 디렉토리와 서브디렉토리 구조 가계도 용어 루트(Root) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다. 맨 위의 노드를 루트라고 한다. 부모-자식(parent-child) 관계 각 노드들의 상하 관계를 부모-자식(parent-child)관계로 나타낸다. 형제 관계(sibling) 루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 가진다. 부모가 동일한 노드들을 형제관계라고 부른다. 리프(leaf) 노드 자식이 없는 노드들을 leaf 노드라고 부른다. 리프노드가 아닌 노드들을 내부(internal)노드라고 부른다. 조상-자손(ancestor - descendant) 관계 부모..

> 멱집합 (Recursion 응용) PowerSet 어떤 집합의 모든 부분집합을 멱집합이라고 부른다. 임의의 집합 data = {a, b, c, d}의 모든 부분집합은 2^n =16개이다. Recursion을 이용하여 모든 부분집합 나열 {a, b, c, d, e, f}의 모든 부분집하을 나열하려면 먼저 a를 포함하지 않는 부분집합과 a를 포함하는 부분집합으로 나눌수 있다. 따라서 아래와 같이 표현할 수 있다. a를 포함하지 않는 부분집합 a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열하고 a를 포함하는 부분집합 {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. => 이 두가지를 합치면 경우의 수가 2^n개가 되는 것이다. 그렇다면, {b, c, d, ..

> Counting Cells in a Blob (Recursion 응용) 입력으로 Binary 이미지가 주어진다. 각 픽셀은 background pixel(흰색)이거나 혹은 imagepixel(파란색)이다. 서로 연결된 image pixel들의 집합을 Blob이라고 부른다. 상하좌우 및 대각방향으로도 연결된것을 Blob으로 간주한다. 따라서 위 그림에서는 총 4개의 Blob이 존재한다. 특정 좌표가 속한 Blob의 크기 count 입력 N * N 크기의 2차원 그리드(grid) 하나의 좌표 (x, y) 출력 픽셀 (x, y)가 포함된 blob의 크기 (x, y)가 어떤 blob에도 속하지 않는 경우에는 0 Recursive Thinking 현재 픽셀이 속한 Blob의 크기를 카운트하려면 현재 픽셀이 i..

> 미로찾기(Recursion 응용) (n-1, n-1)의 좌표를 출구로 가정 흰색이 지날 수 있는 길, 파란색이 벽 입구에서 출구까지의 경로를 찾는 문제 Recursive Thinking 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구이거나(이미 내가 출구에 와 있거나). 혹은, 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가능경로가 있꺼나, 위의 경우를 Recursive하게 생각한다. 전체 문제를 해결하려고 하면 부분 문제의 해결이 이루어지면서 전체문제가 해결된다. => 위의 둘중에 하나가 성립해야 출구까지 가는 경로가 있다고 할 수 있다. 미로찾기(Decision Problem) - 답이 Yes or No 출발점에서 출구까지 가능 경로가 있느냐 없느냐?의 문제로 생각한다..

알고리즘을 위한 자바 IO codeplus - 프로그래밍 대회에서 사용하는 Java 참고 System.out System.out.println(); System.out.printf("%d", n) 실수형, 문자형 자료 출력 가능 Scanner next[자료형]을 이용해서 입력을 받을 수 있고, hasNext[자료형]을 이용해서 입력받을 수 있는 자료형이 있는지 구할 수 있다. 두 수 입력 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a, b; a = scanner.nextInt(); b = scanner.nextInt(); System.out.println(a..

> N-Queens (Back tracking) (n = 8) 아래의 예(n=8)에서는 8x8 체스보드에 8개의 말을 놓는데 그 중에 어떤 말들도 동일한 행, 동일한 열, 동일한 대각선 상에 오지 않도록 n개의 말을 놓을 수 있는가에 대한 문제이다. 위의 방법대로 n개의 말을 놓으려면, 결국 조건을 만족하면서 하나의 행에 하나의 말이 와야한다. Back Tracking 내가 지나온 길을 다시 되돌아 가면서 문제를 해결한다 어떠한 결정들을 내려가다가, 결정이 막다른 길이다. 즉, 그 결정을 내려서는 안된다라는 것이 분명해지면, 가장 최근에 내렸던 결정을 번복한다. 이런식으로 문제를 해결한다. 상태 공간트리 1번말이 (1,1)에 위치했을 때, 그리고 그 때 2번말이 (2,1), (2,2), (2,3), (2..

Bit Depth Bit Depth를 이해하기 가장 쉬운 방법은 "Bit Depth는 오디오의 음량 총량을 담는 컨테이너다"라고 생각하는 것이다. Bit Depth는 역시 헤비록, EDM이 만들어지는 홈스튜디오라면 크게 중요하지 않을 수 있다. 하지만 만약 적절한 음량에서 듣고 녹음하는 경우라면, 전체 프로덕션 과정에서 Bit Depth의 차이는 크게 느껴질 수 있을 것이다. 적절한 Gain 스테이징과 모니터링 레벨에서는 이 차이는 더욱 크게 느껴진다. Bit Depth는 Recording 하려는 음원이나 Audio File의 Line Level(0dB)부터, Noise Floor까지에 이르는 Dynamic Range의 거리를 조절해준다. Line Level은 Recording 또는 Mixing 시에 웬..

[ volatile ] 변수를 선언할 때 앞에 volatile을 붙이면 컴파일러는 해당 변수를 최적화해서 제외하여 항상 메모리에 접근하도록 만든다. volatile int num1 = 10; // 변수를 최적화해서 항상 메모리에 접근하도록 만듦 volatile로 선언한 변수는 사용할 때 항상 메모리에 접근한다. 즉, 이 변수는 언제든지 값이 바뀔 수 있으니까 항상 메모리에 접근하라고 컴파일러에게 알려주는 것이다. 예를 들면 다음과 같은 반복문이 있다. int i = 0; while(i 컴파일러는 이 코드를 최적화하여 while 반복문을 없애버리고 i에 그냥 10을 할당해 버린다.(Visual Studio의 /02옵션, GCC의 -03옵..

MUTEX를 이용한 쓰레드 동기화 1. 공유자원에 대한 접근 제어 다수의 객체가 공유 자원에 접근하려고 하면, (공유 자원의 종류에 따라서) 접근 시점을 동기화 시켜줄 필요가 생긴다. 여기에서 동기화란 시간과 공간을 맞추어 준다는 의미로, 즉 공유 자원 영역(공간)에 접근하는 객체들의 진입 시간을 제어할 수 있어야 함을 의미한다. Multi Thread(멀티 쓰레드) 프로그램 역시 공유 자원에 여러 개의 쓰레드가 접근할 수 있으므로 공유 자원 영역에 대한 동기화가 필요하다. 카운팅 프로그램을 예로 들어보자. 카운트 변수는 전역변수(:12)로 A,B 두개의 쓰레드가 공유하면서, 1씩 증가하는 카운팅 정보를 유지하기 위해 사용된다. 공유자원 영역 즉 "count 값을 읽어 오고, 연산을 해서 저장하는" 영역..

DMA 모드 Direct Memory Access I/O로 인한 성능 감소 방지를 위해 CPU 개입 없이 I/O 장치와 기억장치 간 직접 데이터 전송 방식 처리기를 거치지 않고 DMA컨트롤러에 의해 주변기기로부터 데이터가 메모리로 직접 전송되는 것을 뜻한다. 이 때 각 주변기기는 DMA 컨트롤러 칩의 지시에 따라 데이터를 주고받게 되며 DMA가 지원되지 않는 보드나 주변기기에서 이 부분을 체크하게 되면 컴퓨터가 작동을 멈추는 수가 있으므로 확인하고 사용하는 것이 좋다. DMA I/O Direct I/O(DMA 미사용) DMA 기반 Data 처리 중 CPU는 다른 프로세스 처리 Data I/O 처리 시 완료까지 작업 중지, CPU 대기 필요 DMA 구성도/구성요소 DMA 전송을 위한 중앙처리장치 버스 신호..

FDMA frequency division multiple access : 주파수분할 다중접속 통신망을 통해 전달되는 데이터중 가장 많은 양을 차지하는 것이 음성일 것이다. 사람의 음성을 전달하는 데 필요한 최소한의 주파수 대역폭은 300 ~ 3400 Hz로 알려져 있는데 이러한 음성 신호를 전기적인 신호로 변환하여, 통신망을 통해서 다른 곳으로 전달하기 위해서는 음성 신호를 전송하기에 적합한 전기적인 신호로 바꾸어 주고, 수신하는 쪽에서 이를 다시 음성 신호로 역변환을 하게 된다. 통신망에서 사용하는 전송 시스템의 특성을 살펴보면 전송가능한 주파수 대역이 음성 대역폭 보다는 월등이 크고, 훨씬 높은 주파수까지도 전송할 수 있다. 이런 전송로는 단 한 사람의 통신을 위해서만 사용하는 것은 경제적으로나 시..

17. 인터럽트 인터럽트란 CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어나 예외상황 등이 발생해 작업을 처리가 필요할 경우에 커널에게 처리해 달라고 요청하는 것이다. 그럼 먼저 하드웨어적 문제중에서 CPU에 대해 알아보자 17.1 CPU CPU는 먼저 인스트럭션을 가져온다. 그리고 그 인스트럭션을 분석하고 실행을 한다. 이렇게 실행을 하기 위해선 데이터를 읽어와야 하는 경우도 종종 있게 된다. 또한 연산을 처리 했다면 처리된 결과를 반환해준다. 인스트럭션이 다 끝났으면 그 다음 인스트럭션을 가져오기 위해 프로그램 카운터를 증가시킨다(보통은 4 byte 정도 증가시킨다). 이런 일련의 작업을 하던 중 Disk가 인터럽트를 걸었다고 생각해보자. 그러면 Interrupt Request Bit 한 비트..

20. 타이머와 시간 관리 지난 5강에선 Timeslice 라는 CPU에게 주어지는 사용시간과 CPU의 사용 순서를 관리하는 커널 스케쥴링에 대하여 공부를 했다. 이번 시간에는 그 시간의 단위에 대한 공부와 여러 개의 인터럽트가 일어났을 때의 관리방법에 대하여 공부를 할 것이다. 우리는 시계가 돌아갈때 나는 소리를 째깍째깍 거린다고 표현을 하며 이는 영어로 Tick Tack이라고 표현이 된다. 이때 일초에 1000번 째깍거리면 1000 헤르츠(Hertz, HZ)라고 하고 이는 1 밀리세컨드(1 Millisecond)가 된다. 이러한 표현들은 물리학에서 사용하는 표현들이고 #define HZ 1000이라는 표현을 사용하면 1초에 1000번 인터럽트가 걸리는 설정으로 된다. 대부분의 경우에는 100을 걸어 ..