프로그래밍 비타민

진리표를 보고 출력 S에 대한 논리식으로 옳은 것은?

입력		출력
A	B	S
0	0	0
0	1	1
1	0	0
1	1	1

답 : S = B / S = B * 1 / S = A'B+AB

ANSI(American National Standards Institue)에서 ASCII(American Standard Code for Information Interchange)라는 표준을 제시. ASCII는 각 문자를 7비트로 표현하므로 총 128(=2^7)개의 문자를 표현할 수 있다. 128개는 영문대문자, 소문자, 숫자, 구두점, 특수문자등을 포함한다.

'A'의 ASCII : 1000001

'a'의 ASCII : 1100001

'a'는 'A'보다 32가 크다.

ASCII은 기존의 7비트에 추가 문자 1비트를 추가하여 8비트를 사용한다.

유니코드는 사용중인 운영체제, 프로그램 언어에 관계없이 문자마다 고유한 코드 값을 제공하는 새로운 코드의 개념이다. 모든 문자를 16비트로 표현하고 최대 65,536(=2^16)자를 표현할 수 있다.

'A'의 ASCII : 1000001

'A'의 Uni   :  0000000001000001

폴란드식 표기법 : 연산자의 표기가 앞에 위치하며, 전위 표기법이라고도 한다.

연산자 - 피연산자 - 피연산자

(4+2)*3 -> *+423

역 폴란드식 표기법 : 연산자를 피연산자 뒤에 위치시키며, 후위표기법이라고도 한다.

피연산자 - 피연산자 - 연산자

(4+2)*3 -> 423+*(잘못됨) , 42+3*(정답)

Q (4+3) * (5-2)를 폴란드식 표기법과 역 폴란드식 표기법으로 표현하라.

*+43-52 / 34+52-*

트리(Tree)는 나무를 뒤집은 모습의 계층 구조를 표현하기에 적합하다. 트리의 각 객체는 노드(node)라 하고, 노드와 노드를 연결하는 선을 링크(link)라 한다. 가장 위에 위치한 노드를 루트노드(root node)라 하는데, 이는 한 개만 존재한다. 최 하단에 위치한 노드를 단말노드(terminal node)혹은 리프노드(leaf node)라 한다. 루트노드에서 임의의 노드까지 방문한 노드의 수를 레벨이라 하며, 최대 레벨으 깊이(depth)라 한다.

이진트리(binary tree)는 모든 노드들의 자식 노드가 두 개 이하인 트리를 의미하여, 서브 트리는 왼쪽 과 오른쪽 서브 트리로 구분한다. 그리고 단말 노드를 제외한 나머지 노드가 두 개의 자식 노드를 가지고 있는 트리를 '완전 이진 트리(complete binary tree)'라 하며, 모든 노드가 채워진 이진 트리를 포화 이진 트리(full binary tree)라 한다.

트리의 순회(traversal)란 이진 트리의 모든 노드를 특정한 순서대로 방문하는 것이며, 전위(preorder), 중위(inorder), 후위(postorder)순회가 있다.

전위 순회 : 노드 방문 -> 왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문

중위 순회 : 왼쪽 서브 트리 방문 -> 노드 방문 -> 오른쪽 서브 트리 방문

후위 순회 : 왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문 -> 노드 방문

이진 탐색 트리(binary search tree)는 이진 트리이면서 같은 값을 갖는 노드는 없어야 하며, 왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 크다.

그래프 : 각 정점(vertex)과 정점이 연결하는 선(간선(dege))로 표현된다. 무방향 그래프와 방향그래프고 구분되는데, 무방향 그래프는 방향성이 없는 간선으로 이루어진 그래프 이며, 방향 그래프는 방향성이 있는 간선으로 이루어진 그래프이다. 또한 가중 그래프(weighted graph)는 간선마다 가중치를 부여한 그래프를 뜻한다.

그래프의 탐색은 깊이 우선 탐색(DFS, depth first search)와 너비 우선 탐색(BFS, breadth first search)가 있다.

깊이 우선 탐색은  시작 정점에서 방문하지 않은 정점을 방문하고, 계속 아래 정점으로 진행하다 더 이상 진행하지 못할 경우 되돌아 가면서 방문하지 않은 정점을 찾는다.

너비 우선 탐색은 시작 정점에서 시작 정점과 연결된 모든 정점을 방문한다. 그런 다음 새롭게 방문한 정점들에 연결된 아직 방문하지 않은 정점을 방문한다.

다익스트라 알고리즘(Dijikstra algorithm)은 정해진 하나의 출발점에서 목표지점까지의 가장 짧은 경로를 구하는 것이다.

해시 테이블(hash table)은 데이터가 저장될 위치가 데이터의 값에 의해 정해지는 데이터 구조이다. 각 각의 자료를 담기 위하여, 여러 개의 데이터를 저장할 수 있도록 구성하지만, 공간이 넘칠 경우 저장의 문제가 발생된다. 그때 바람직한 구조는 연결리스트를 이용한 체이닝(chaining)방법(포인터 이용)이 있다.

히노이 탑 퍼즐

규칙 1. 왼쪽 기둥에서 2(n-1)개의 원판을 가운데 기둥으로 옮긴다.

규칙 2. 왼쪽 기둥의 원반을 오른쪽 기둥으로 옮긴다.

규칙 3. 가운데 기둥의 2(=n-1)개의 원반을 오른쪽 기둥으로 옮긴다.

인공 지능 탐색

최고 우선 탐색(best-first search)은 임의의 상태에서 목표 상태에 도달하기 위해 어떤 상태를 탐색하는 것이 지름길인지를 추측하는 방식으로 이 때 상태의 가치를 추정하기 위해 사용하는 함수를 평가함수라 하는데 평가 함수 값이 최대인 상태를 선택해서 탐색해간다.

패리티 비트는 짝수 패리티와 홀수 패리티로 나뉘는데, 홀수 패리티는 짝수를 홀수로만 대체하면 된다. 패리티 비트는 2진 데이터에 패리티 비트가 추가되어 1의 개수가 짝수가 되게 하는 것이다.

1000001 / 패리티(0)

1000011 / 패리티(1)

이렇게 생성된 패리티 비트를 수신하여 수신 정보에 대한 패리티 비트를 구해 0이면 오류가 발생안함, 1이면 오류가 발생한 것으로 판단한다.

패리티 비트 검사의 경우 짝수개의 오류가 발생할 경우 발견하지 못하는 상황이 발생된다

송신) 1100001 / 1

수신) 1000011 / 1

이러한 문제점을 해결하기 위해 세로 중복 검사가 있다.

세로 중복 검사(LRC:Longitudinal Redundancy Check)는 패리티 비트에서 발견하지 못한 오류를 검출할 확률 높은 방법이다.

데이터) 01000001 01101100 11010011

0 1 0 0 0 0 0 1 (8비트씩 3행으로 전환)

0 1 1 0 1 1 0 0

1 1 0 1 0 0 1 1

1 1 1 1 1 1 1 0 (중복 정보)

중복 정보르 구하여 데이터와 함께 수신측으로 전송하며, 이를 통하여 오류를 검출 한다.

압축 기술

런 렝스 코딩(run length coding) : 반복문자 * 탈출문자 * 반복횟수로 표현한다.

AAAAAAABBCCCDEEEEFFFFFFG

A7B2C3D1E4F6G1(구분하기 애매)

A*7B*2C*3D*1E*4F*6G*1

안좋은 예)I love you 압축률이 오히려 떨어진다.

허프만 코딩(Huffman coding) : 자주 사용되는 문자는 적은 비트로 된 코드로 변환해서 표현하고, 별로 사용되지 않는 문자는 많은 비트로 된 코드로 변환하여 표현함으로써 전체 데이터를 표현하는데 필요한 비트의 양을 줄이는 방법이다. 허프만 코딩에서는 압축 대상이 되는 데이터마다 최대한 효율적으로 압축이 될 수 있게끔 코드를 생성하고 그 체계에 따라 압축한다. 그렇게 되려면 각 문자에 대한 특정 코드가 정해져 있어야 하는데 이때 필요한 것이 허프만 트리(Huffman tree이다.)