- 컴퓨터 시스템 간에 미리 정한 규약으로 문자를 표현한다.
- 코드를 받은 컴퓨터는 변환 프로그램을 통해 코드에 해당하는 문자를 생성한다.
- ASCII : American Standard Code for Information Interchange / 정보교환을 위한 미국 표준코드
- 문자를 7비트로 표현 - 2^7 : 128 개의 문자를 표현할 수 있다.
- Extended ASCII : 8비트를 사용하는 코드 체계
- 유니코드(Unicode)
- 한 문자를 16비트로 표현함, 아스키코드를 포함
- 아날로그의 디지털화 - 샘플링
- ‘주기’적으로 전압 측정
- 측정된 전압을 기록
- 일부 데이터는 손실될 수 있으나, 소리를 충분히 재생 가능
- 사람이 인식할 수 없을 정도의 차이를 허용해 파형을 근사적으로 묘사한다.
- 측정 주기가 짧을수록 데이터양은 증가, 질은 좋아짐
- 이미지와 그래픽의 표현
- 데이터를 여러 조각으로 나타냄 = 픽셀로 나타낸다.
- 많은 픽셀일수록 이미지를 더 세밀하게 묘사할 수 있음
- 픽셀의 개수를 해상도(resolution) 라고 한다.
- RGB 모델 - 각 8비트로, 총 24비트로 나타낸다.
- 전체 색깔은 256^3 조합 가능 ( 인간의 눈으로 판별이 불가능하다 )
- 픽셀 단위로 이미지 데이터를 저장하는 방식을 래스터 그래픽, 점, 선, 도형 등 좌표와 생성식으로 표현하는 방식을 벡터 그래픽이라고 한다.
- 벡터 그래픽 : 작은 데이터의 양으로 이미지를 저장할 수 있고, 이미지 크기가 변경되면, 쉽게 큰 이미지나 작은 이미지를 생성할 수 있다.
- 종류 : 배열, 연결리스트, 큐, 우선순위큐, 스택, 그래프, 트리
- 배열과 연결리스트
- 배열은 데이터의 최대 개수가 고정된다.
- 연결리스트는 데이터의 개수가 가변적이다. - 방문한 지점의 물리적인 위치는 중요하지 않고, 논리적인 위치가 중요하다.
- 단순연결리스트, 이중연결리스트
- 큐 : 리스트의 특별한 구조, 선입선출 - 서비스를 받기 위한 대기열
- 우선순위 큐 : 우선순위가 높은 사람이 우선적으로 서비스를 받는다. 힙을 이용해 구현한다. - 응급환자 먼저치료
- 스택 : 데이터가 쌓여있는 형상 - 미로에서 시작 지점으로 되돌아 가기위해 지나온 지점의 위치를 저장한다.(되추적)
- 그래프 : 에지와 노드로 표현됨 - SNS 의 친구관계
- 트리 : 데이터의 계층적인 구조를 나타낼 수 있는 자료구조
- 이진트리 : 트리의 단순한 형태, 각 노드는 최대 2개의 자식노드를 가질 수 있음
- 인코딩 : 정보를 코드로 표현 / 디코딩 : 코드로 표현된 것으로부터 정보를 추출
- 압축 : 인코딩 시 가능한 저장공간을 줄임
- 팩스를 전송할때, black pixel 의 갯수 , white pixel 의 개수, black pixel 의 개수…. 이런식으로 보내면 압축 가능
- Run-Length
- 하나의 문자는 여러번 나타날 수 있으므로, 반복된 문자열을 반복된 문자, 반복 횟수로 대체한다. (bbbbb -> b5)
- kk -> k2 는 이득이 없으므로 인코드하지 않아도 된다.
- 이미지 압축에 효과적이다.
- LZSS 인코딩 - 텍스트 압축
- 동일한 문자열을 앞부분에서 찾아 재활용
- 너무 멀리 있는 패턴을 찾으려면 시간 소요 - search window 크기제한
- 너무 긴 패턴을 찾으려면 시간 소요 - 패턴 길이제한
- 일정한 크기 이상의 패턴에 대해서 재활용해야 압축 효과가 나타난다.
- 동일한 문자열을 앞부분에서 찾아 재활용
[image:A36DC014-2405-4CC9-A591-4C043E4B2216-848-0000019C3F17CA00/7022A7D1-28C0-4C50-A1C1-06BEC09BAB77.png]
- 후프만 코드
- 영문 알파벳으로 구성된 텍스트를 인코딩할 때 인코딩된 파일의 크기를 최소로 하는 인코딩 방법을 설계
- 한 문자의 코드가 다른 문자의 코드의 앞부분이 될 수 없다.
- a:11, b:0, c:01 이면 0 을 어떻게 해석할 지 결정할 수 없다.
- 트리 구조를 이용해 코드를 부여하고, 전치 코드에 따라 인코딩된 파일의 크기가 달라진다. -> 최적 전치코드를 구하는 방법이 필요하다.
- 후프만 코드 생성방법
- 인코딩하려는 n 개의 데이터에 대해 빈도수를 표시하여 n개 노드 생성
- 두 노드의 빈도수 합이 최소가 되는 두 노드를 찾는다.
- 두 노드를 합병시켜서 이진트리로 만든다.
- 모든 노드가 하나의 이진트리로 합쳐질 때 까지 2,3 을 반복한다.
- 후프만 코드 생성방법
- 송신자가 보낸 정보는 제 3의 악의적인 조작 또는 통신오류에 의해 전송 중간 단계에서 변해 수신자에게 전달될 수 있다.
- 종류
- 반복 코드 - 정보를 정해진 수만큼 반복해 전송 - 정보가 모두 같으면 변조 없음 확인
- 패러티 비트 - 추가된 패러티 비트에 의해 1의 개수가 짝수가 되도록 (짝수 패러티 비트)
- 데이터가 일치하지 않는걸 알수 있지만, 위치는 확인 불가능하다.
- 두군데에서 동시에 오류가 발생하면 오류발생을 알 수 없다.
- -> 2차원 패러티 비트
- 데이터를 끊어서 2차원으로 배치한 후, 행 패러티와 열 패러티를 추가한다.
- 패러티 오류가 겹치는 행, 열 위치에 오류가 발생하면, 오류 위치를 정확히 알아낼 수 있다.
- 만일 서로 다른 행, 열에서 두 곳의 변조가 발생하면?
- 가능성만 확인 가능하다. 정확한 위치는 확인 불가
- 만일 하나의 행에서 두곳의 비트에 변조가 발생하면?
- 해당 열만 찾을 수 있지만, 정확한 위치 확인 불가
- 체크 디지트
- 데이터에 대해서 약속된 연산을 통해 나온 숫자를 뒤에 붙임
- 체크 디지트를 통해 오류를 확인할 수 있다.
- 체크섬
- 각 행의 데이터들에 대해서, 모두 더해 행을 하나 더 만든다.
- 이를 통해 변조 사실을 확인할 수 있다.
- 과목의 성적과 체크섬을 동시에 변조하면 변조사실을 확인할 수 없다. -> 체크섬을 계산하는 방식을 예상하기 어렵게 만든다. -> 각 과목 성적의 체크섬을 추가한다. - 모든 과목 성적의 합 체크섬이 과목 성적과 일치하더라도, 각 과목의 체크섬 확인으로 과목 성적 변조를 확인할 수 있다.
- 메시지 다이제스트
- 그림파일 A 와 그림파일 B 가 동일한지 확인하는 방법
- 복잡한 해시함수에 A 데이터를 입력으로 주어 결과값 (b) 이 생성
- 그림파일 A와 메시지 다이제스트 b 를 송신
- 수신자는 미리 공유한 해시함수 h 에 입력으로 B 를 주고, 결과값이 b 가 되는지를 확인
- 동일 여부를 확인해 위변조 여부를 확인 가능
- 메시지 다이제스트 : 암호화 해시함수
- 체크섬보다 더 긴 데이터 길이의 메시지 다이제스트를 생성한다.
- 생성된 메시지 다이제스트를 이용해 원래의 데이터를 재현하는 것이 거의 불가능하다.
- 데이터가 바뀌면 메시지 다이제스트도 바뀐다.
- 이상적인 메시지 다이제스트의 해시함수
- 어떤 데이터가 주어지더라도 해시 값을 쉽게 계산
- 해시값으로부터 원래 메시지를 생성하는 것이 불가능
- 문서 일부가 수정되면 원래 문서의 메시지 다이제스트와 동일한 메시지 다이제스트를 생성 불가
- 배열과 연결리스트
- 배열
- 사용할 공간을 초기 설정 후 변경 불가, 더 많은 데치터가 입력될 경우 저장 불가
- 크기가 고정된 데이터 저장에 사용
- 데이터가 저장된 위치(인덱스)를 알 경우 데이터 값을 쉽게 확인
- 연결 리스트
- 데이터의 개수가 가변적일 때 사용, 메모리 크기의 한도에 도달하지 않는 한, 데이터의 추가 가능
- 어느 위치에도 추가 가능, 삭제가 쉽다.
- 특정 데이터를 찾기 위해서는 처음 데이터부터 확인하고, 링크를 따라 이동하면서 확인
- 배열
- 선형검색
- 왼쪽부터 쭉 찾는다.
- 최소 1회, 최대 n 회, 평균 n/2 (n=짝수) , (n+1)/2 (n=홀수)
- 이분검색
- 정렬되어 있어야 한다. [image:886A94CF-0203-466B-AF48-BA1A1DB639F1-848-000003B13BB03017/8AB37B4F-CBD5-4116-9D09-F0F64B7E2B98.png]
- 색인 순차검색
- 먼저 색인을 확인하고, 해당 위치에서 순차적으로 검색 (도서관)
- 해싱
- 체크섬의 일종으로, 특정 연산으로 나온 새로운 번호로 자리를 배정하는것
- 같은 자리로 배정되는 충돌이 일어날 경우, 새로운 해시함수를 고안하거나 충돌 해결방법이 필요하다.
- 이진트리 : 트리의 단순한 형태, 각 노드는 최대 2개의 자식노드를 가질 수 있다.
- 트리 구조를 이용해서 데이터의 성질을 고려한 저장구조
- 노드 A 의 왼쪽 하위트리의 노드들에는 A 보다 작은 데이터가 저장, 오른쪽에는 큰데이터가 저장. 이 성질을 각 노드마다 재귀적으로 적용한 트리
- 데이터를 이진검색트리로 만드는 방법 - 한줄로 나열된 이진검색트리가 생성될수도 있다.
- 이진검색트리에서 데이터를 삭제하는 방법
- 이진검색트리에서 inorder 로 방문하면 정렬된 데이터의 순서를 얻을 수 있다.
- 이진검색트리를 만들때, 자주 검색하는 단어를 뿌리노드쪽으로 배치한다.
- 최적 이진검색트리 찾는 문제는 매우 어려운 문제이다.
- 선형적으로 최대 / 최소값 찾기
- MIN-MAX
- 최대값과 최소값을 모두 찾는 문제에서
- 최소값을 찾고 -> 최대값 찾기 - 2n-3 회 비교
- MIN-MAX -> 3/2 n - 2 (n=짝수), 3/2 n - 3/2 (n=홀수) 의 비교 필요
- 선택정렬
- 매 단계에서 정렬된 부분 A 와 정렬되지 않은 부분 B 로 나눈다.
- B 부분에서 가장 작은 데이터를 찾아 B 의 제일 왼쪽 데이터와 교환한 후 그 부분을 A 부분으로 편입힌다.
- 제일 처음 데이터부터 끝까지에 적용한다.
- n(n-1)/2 회의 데이터 비교가 필요, 이미 정렬되어있어도 n(n-1)/2 회 필요
- 삽입정렬
- 매 단계에서 정렬된 부분 A 와 정렬되지 않은 부분 B 로 나눈다.
- B 에서 가장 왼쪽 데이터를 A 부분 윈쪽으로 이동하면서 위치할 수 있는 자리를 찾아준다.
- 찾았으면, 그 데이터를 A 로 통합한다.
- 이 방법을 제일 처음(왼쪽) 데이터부터 끝까지 적용한다.
- 최대 n(n-1)/2 회의 데이터 비교, 최소 (n-1) 의 데이터 비교
- 평균 n(n-1)/4 회로 선택정렬보다 우수하다.
- 분할정복의 일반적인 해결단계
- 문제를 작은 문제로 분할한다.
- 분할된 문제의 해를 구한다.
- 분할된 문제의 해를 이용해서 원래의 분할 이전 문제의 해를 구한다.
- 이분검색, 퀵소트, 머지소트 등에 분할정복 알고리즘이 적용
- 퀵소트
- 임의의 데이터를 A 라 하고, 나머지 데이터들과 비교한다.
- 각 데이터에 대해, A 와 비교해 데이터가 무거우면 그룹 H 에 넣는다.
- 각 데이터에 대해, B 와 비교해 데이터가 가벼우면 그룹 L 에 넣는다.
- 돌들은 그룹 L,A,H 로 나뉜다.
- 그룹 L 과 H 에 대해 단계를 각각 수행한다.
- 데이터 비교 횟수는 nlogn 으로, 정렬 알고리즘 중에서 우수한 성능을 보인다.
- 단계별로 문제를 해결할때, 이후에 발생하는 상황을 고려하지 않고, 형재 단계에서 가장 좋다고 판단되는 해를 선정하는 방식
- 탐욕적 알고리즘이 항상 문제의 최적해를 찾는 것은 아니다.
- 구성요소
- 선택과정
- 적정성 점검
- 해 점검
- 최소 동전개수 문제에서
- 동전이 큰 순서로 확인 - 선택과정
- p 를 초과하는지 확인 - 적정성 점검
- p=0 인지 확인 - 해 점검
- 탐욕적 알고리즘이 최적해를 찾지 못하는 경우 - 최단경로
- 탐색해야 할 해 공간이 클때, 될수 없는 상황을 만나게 되면 이전단계로 되돌아 가는것
- 미로탐사
- 스택과 배열로 해결 [image:2522B0FC-7C63-4C1B-B90A-31F720D69446-848-000007047FD27D26/775E58BF-3AAD-4491-A130-D2BE891CBEC2.png]
- Queen 배열
- 상태공간 트리의 뿌리노드부터 출발해서, 아래로 이동하고, 더이상 이동할 수 없을때 위로 올라가서 오른쪽 다음으로 이동
- 노드를 방문하면서 해를 만들어낼 수 있는지 확인
- 해를 만들어낼 수 없는 상황이라면, 검색 순서의 전 지점으로 돌아간다.
- 큰 상태공간의 가지는 여러 문제에 대해 되추적 방법은 효율적으로 해를 찾을 수 있게 해준다.
- 해밀토니안 회로문제, 그래프 칠하기, 배낭문제, 부분집합의 합 문제 등에도 활용가능
- 도시의 한 지점에서 출발하여 모든 다리를 한번씩만 지나간 후 출발점으로 돌아오는 경로 -> 하나의 노드에서 출발하여, 그래프의 모든 에지를 한번씩만 방문한 후 출발 노드로 돌아오는 경로가 존재하는가?
- 오일러 회로가 존재하기 위해서는 모든 노드의 연결도(차수)가 짝수여야 한다.
- Fleury 알고리즘 - 오일러회로 찾는 알고리즘
- 홀수 연결도를 갖는 노드가 k 개인 경우, k/2 개의 연속된 stroke 로 모두 그릴 수 있다.
- 그래프 이론의 최초이론, 육지와 다리의 연결관계를 그래프의 노드와 에지로 표시
- 그래프 내의 모든 노드를 포함하는 트리에 포함된 에지들의 길이의 합이 최소가 되는 트리
- Kruskal 알고리즘
- 그래프에 있는 에지들을 에지 길이의 오름차순으로 정렬
- 에지의 길이가 짧은 순서로 에지를 선정 선택과정
- 선정된 에지를 최소신장트리에 넣을 수 있는지 판단 (구축 중인 최소신장트리 내에서 사이클을 만드는지 확인) 적정성 점검
- 만들지 않으면, 최소신장트리에 그 에지를 추가, 구축된 최소신장트리의 에지 수가 노드수 -1 이 되었는지 확인하여 맞으면 종료, 아니면 단계 2 로 이동 해 점검
- 만들면, 에지는 포함시키지 않는다.
- 하나의 함수를 정의할 때, 자신의 형태가 그 정의 안에 또 나타나는것
- 하노이타워 -> T(n) = 2T(n-1) + 1, T(1) = 1
- 초기 조건을 잘 정의해야 한다.
- 다이젝스트라 - 그리디 알고리즘
- 이분그래프
- 노드들은 두개의 그룹 G1, G2로 나눈다.
- 에지들은 두 그룹간의 노드들 사이에만 존재한다. (그룹 내 노드간에는 존재하지 않는다. )
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ