2021. 3. 1. 23:28ㆍ필요/전자공학
소프트웨어학과에서는 자료구조 과목, 알고리즘 과목을 구분해서 배운다.
허나 전자공학과에서는 한번에 배운다.
아무래도 실습적인 부분보다는 이론 위주로 얕게 배우는 것이라고 생각된다.
주변에 물어본 결과, 타학교 전자과의 경우 이러한 프로그래밍 심화 전공이 선택 과목인 경우도 꽤 있다.
대강 나눠서 생각하면 다음과 같은 것을 배운다.
자료구조 : 배열, 구조체, 포인터, 리스트, 스택, 큐, 트리, 힙, 그래프
알고리즘 : 순환, 정렬, 탐색, 해싱
매우 방대한 양이다..
간단히 어떤 것인지만 단원별로 요약해서 리뷰하겠다.
Ch1 자료구조 & 알고리즘
자료구조는 Data Structure라고 부른다.
정보인 Data를 정리하는 구조로써, 정보를 조직화하여 편하게 사용할 수 있다.
알고리즘은 계산과 데이터 처리에 사용되는 유한한 일련의 지시사항이다.
컴퓨터로 문제를 풀기위한 절차적 방법이다!
프로그램은 자료구조를 사용해서 알고리즘을 구성하는 방식으로 짜여진다.
알고리즘은 여러방식으로 기술될 수 있는데, flow chart (흐름도)나 유사코드를 사용하면 설명하기 좋다.
알고리즘의 성능은 구현전에 시간 복잡도를 비교해서 분석할 수 있다.
빅오표기법을 주로 사용하는데, 이는 함수의 상한(최대)을 표시한다.
동일 기능을 구현할 때, 당연히 시간이 오래 걸릴수록 좋은 알고리즘이 아니다.
코딩 테스트에서도 종종 O(n^2) 의 시간복잡도로는 시간초과가 발생하는 경우가 많다!
n의 개수가 커지면서 O(n^2)은 기하급수적으로 커지기 때문이다.
알고리즘의 수행시간은 입력되는 자료에 따라 다르기 마련이다.
Best, Average, Worst 케이스 중에서 Worst 케이스가 가장 중요한 의미를 가진다.
Ch2 순환
Recursion (순환)은 자기자신을 호출해 문제를 해결하는 방법이다.
무한히 호출되면 안되므로, 반드시 끝나는 조건을 구현해야한다.
예시를 들자면 팩토리얼 값, 피보나치 수열 등을 표현하는데 활용된다.
사실 순환으로 풀 수 있는 모든 문제는 반복으로 풀 수 있다.
그렇다면 왜 순환을 사용할까?
문제 자체가 순환적인 경우, 더 좋은 해법이 될 수 있다.
하지만 자칫 함수 호출의 오버헤드가 커질 수 있는 단점이 있다.
위 사진을 보면 fib(6)을 호출했을 때, fib(3)을 세번이나 부르게 된다..
훨씬 큰 수를 호출한다고 가정했을 때, 이러한 불필요한 호출은 감당이 안되게 많아진다.
이를 해결하는 방법으로, memory 배열을 지정해서 호출시 값을 대입하고, 값이 들어 있을 때, 호출을 생략하게 구현할 수 도 있다.
어쨋든 default는 반복으로 생각하고, 순환은 가끔 유용하게 사용하면 좋다!
Ch3 배열, 구조체, 포인터
배열
배열은 같은 데이터형의 변수를 여러개 만드는 것이다.
int array[6];
변수가 많아지면 필수적이다.
2차원 배열 역시 마찬가지로 유용하다.
int array[3][4];
입력받을 때와 출력 등에서 행과 열이 종종 헷갈릴 수 있어 주의가 필요하다.
배열 그 자체는 대입이나 비교가 불가능하다.
a와 b가 배열일 때, a = b a==b 등의 계산은 불가능하다.
반복문을 사용하여 항목별로 진행되는 대입 또는 비교는 가능하다!
a[i] = b[i] a[i] == b[i] 는 가능하다.
문자열은 1차원 배열의 특수한 형태이다.
char s[] = “game set”;
<string.h> 라이브러리를 include하면 대입에는 strcpy(), 비교에는 strcmp()를 사용할 수 있다!
call by value 와 call by reference를 구분해야된다.
콜바벨은 단순히 값을 복사해서 사용하는 것이다. 따라서 복사당한 원본은 바뀌지 않는다.
콜바레는 주소를 전달하기 때문에 원본도 바뀐다.
구조체
구조체는 타입이 다른 데이터를 하나로 묶는 방법이다.
struct Human {
char name[10];
int age;
};
이런 식으로 표현이 가능하다.
구조체 변수 자체는 대입은 가능하나, 비교는 불가능하다.
물론 마찬가지로 각 항목별 대입과 비교는 가능하다. (ex. Human a, b; 이면 a.age == b.age 비교가능)
자체 참조 구조체는 자신을 가리키는 포인터가 존재하는 구조체이다.
typedef struct ListNode {
int data;
struct ListNode *link;
} ListNode;
연결리스트나 트리에 많이 사용된다.
포인터
포인터는 필요한 내용만 언급해도 될 것 같다.
구조체의 요소에 접근 시 -> 연산자를 사용한다.
s.i == 2, s.f == 3.14 인 경우
ps = &s;
ps->i = 2;
ps->f = 3.14;
동적 메모리 할당
int A[10];
이게 정적 메모리 할당이다.
동적 메모리 할당은 프로그램을 실행할 때, 필요한 만큼 그때그때 메모리를 할당받는 것이다.
효율적인 메모리 사용이 당연히 가능하다.
<stdilb.h> 라이브러리의 malloc 함수를 사용해서 나타낼 수 있다.
사용이 끝나면 반드시 명시적 해제를 해주어야한다.
free 함수로 해제하고, 향할 곳이 없어진 포인터 변수를 NULL로 변경한다.
C++ STL의 vector와 비슷한 방식인 것 같다!
다만 사용 후 처리가 좀 더 번거롭다.
Ch4 리스트
리스트는 순서를 가진 항목 모임이다.
구현하는 방법은 두가지이다.
1. 배열 사용
- 구현간단
- 삽입 삭제 오버헤드
- 크기 제한
2. 연결리스트 사용
- 구현 복잡
- 삽입 삭제 효율적
- 크기 제한X
배열
삽입 삭제 시 자료를 많이 이동해야 한다.
연결 리스트
연결리스트의 노드는 data 필드와 link 필드로 이뤄져 있다.
link는 어디를 향하는지 주소가 들어간다.
또한 노드는 필요할 때마다 동적 메모리를 통해 생성된다.
배열과 달리 임의의 위치를 참조할 수 있으므로, 삽입 삭제가 용의하다!
단순 연결리스트는 한쪽방향으로 노드를 따라간다.
그렇기 때문에 앞 노드를 찾기 위해서는 처음부터 반복해야한다.
그리고 노드 앞 포인터를 알아야 하므로 임의의 노드를 삭제하기 힘들다.
따라서 다른 연결 리스트를 사용한다.
원형 연결 리스트는 다음과 같이 헤드 포인터를 위치해서, 처음과 끝 모두 참조하기 쉽다.
이중 연결 리스트는 하나의 노드에 link가 두 개 존재한다.
선행 노드, 후속 노드가 모두 연결되므로 양방향 검색이 가능하다.
실제로는 위와 같이 헤드노드 + 이중연결 리스트 + 원형연결 리스트를 많이 사용한다.
연결 리스트 응용
다항식
- 하나의 다항식을 하나의 연결리스트로 표현
Ch5 스택
스택
스택은 쌓아놓은 더미를 의미한다.
후입선출 (LIFO)- Last In First Out 의 성질을 가진다.
최근에 넣은 데이터가 가장 먼저 나가는 것이다.
스택과 같은 원리로, 입력과 반대되는 출력이 필요한 경우에 주로 사용한다.
되돌리기, 미로탐색 또는 컴퓨터에서 함수호출 시 복귀하는 방식에서 활용된다.
스택의 응용
괄호검사
- [ ], { }, ( ) 등이 올바르게 사용됬는지 확인한다.
실제로 if 문이 구현될 때 다음과 같이 확인한다고 한다.
수식 계산
- 전위, 중위, 후위 연산을 표기할 때 스택을 사용한다.
우리가 사용하는 표기법이 중위 표기법이다.
컴퓨터에서는 중위 -> 후위표기식으로 변환해서 계산을 진행한다.
각 변환들이 이뤄지는 방법은 스택을 따른다.
한번 수식을 반복할 때 피연산자와 연산자 등 조건에 따라 값을 stack에 저장한다.
stack이 모두 pop() 되면 변환이 완료된다.
미로탐색
- 방문하지 않은 곳의 위치를 스택에 저장한다.
Ch6 큐
큐
큐는 먼저 들어온 데이터가 먼저 나가는 구조이다.
선입선출 (FIFO)- First In First Out 의 성질을 가진다.
삽입은 front에서, 삭제는 rear에서 이뤄진다.
배열을 이용한 큐
선형큐
앞서 언급한 배열을 이용한 스택과 동일한 문제가 있다!
삽입을 위해 요소를 계속 이동시켜야하므로 잘 쓰지 않는다.
원형큐
계속 회전할 수 있는 구조라서, front와 rear가 유연히 위치할 수 있다.
요소들을 이동시킬 필요가 없어서 선형큐의 문제가 해결된다.
연결리스트를 이용한 큐
메모리가 유동적이므로, 연결리스트를 사용해도 문제없이 큐를 구현할 수 있다.
덱
Double-Ended Queue의 줄임말로, front와 rear 모두에서 삽입, 삭제가 가능하다.
앞서 본 이중 연결 리스트와 형태가 비슷하다.
실제로 이중 연결 리스트를 사용해서 구현한다!
큐의 응용
버퍼
- 서로 다른 속도로 실행되는 프로세스간의 조화를 위한 역할
잠시 대기하는 기능이다.
은행 시뮬레이션
- 큐잉이론을 통해 시뮬레이션
큐를 사용해 고객 들어오는 시간 등 계산
Ch7 트리
트리
트리는 계층적 구조를 나타내는 자료구조이다.
부모-자식 관계의 노드로 이뤄진다.
이진 트리
이진 트리는 모든 노드가 2개의 서브 트리를 갖는 트리이다.
사실 서브트리는 0개, 1개일 수도 있다.
이진 트리는 여러가지 성질을 갖는다.
노드 개수 (n)에 따라 간선의 개수 (n-1)가 정해진다.
그리고 노드 개수에 따라 높이를, 높이에 따라 노드 개수의 범위를 구할 수 있다.
포화 이진 트리
트리의 각 레벨에 노드가 모두 차 있는 이진 트리이다.
완전 이진 트리
높이가 h일 때, 1~h-1 레벨까지 노드가 가득 채워져 있고, h 레벨에서는 왼쪽-> 오른쪽으로 순서대로 노드가 채워져 있는 이진 트리이다.
이진 트리의 표현
배열표현법
포화 이진 트리에 해당하는 배열에 트리를 대입한다.
링크 표현법
부모노드가 자식 노드를 가리키게 하는 방법이다.
순회
위 문제의 개념에서 설명했다.
이진 트리 응용
수식 트리
- 산술식을 트리로 표현한 것이다.
단말노드 : 피연산자(숫자), 비단말노드 : 연산자(+-x%/)
스레드 이진 트리
보통 이진트리는 순환 호출을 통해 노드를 순회한다.
하지만 단말노드의 링크가 NULL인 점을 활용해서, 이 링크를 이용해 트리 노드를 순회할 수 있다.
스레드 이진 트리는 NULL 링크에 중위 순회의 후속 노드인 중위 후속자를 저장하는 방식이다.
이진 탐색 트리
효율적인 탐색작업을 위한 자료구조이다.
모든 원소의 키가 유일하며, 키의 크기 : 왼쪽 서브트리 < 루트 < 오른쪽 서브트리 이다.
중위 순회 시 오름차순의 정렬 값을 얻을 수 있다.
이진 탐색 트리의 성능은 좌우의 균형에 따라 달라진다.
최선의 경우, 이진트리가 균형적으로 생성되어, 높이에 직접 영향을 받아서 O(log n)의 시간복잡도를 가진다.
최악의 경우, 이진트리가 한쪽으로 치우쳐서 높이 = 노드의 개수이므로 O(n)의 시간복잡도를 가진다.
Ch8 히프
우선순위큐
우선순위를 가진 자료를 저장하는 큐이다.
기존의 큐가 가장 먼저 들어온 데이터부터 삭제가 이뤄진다면, 우선순위큐는 우선순위에 따라 삭제가 이뤄진다.
이러한 우선순위큐를 구현하는 방법으로는 큐와 같이 배열, 연결리스트를 사용할수도 있다.
하지만 가장 효율적인 시간복잡도(O(log n))를 갖는 방식은 히프를 이용한 방식이다.
히프
히프는 완전이진트리 형태의 자료구조이다.
최대 힙(max heap)은 키 : 부모 >= 자식 이고, 최소 힙(min heap)은 키 : 부모 <= 자식 이다.
히프는 배열을 통해 구현한다. ( 완전이진트리 특성 상 메모리 손해가 거의 없음 )
Upheap
- 히프에서의 삽입 방법
①새로운 값을 가장 말단 노드를 만들어서 저장
②부모노드와 비교해서 조건만족 시 교환
③교환 후에 다시 부모노드와 비교
Downheap
- 히프에서의 삭제 방법
①루트 삭제
②가장 말단 노드를 루트로 이동
③루트~단말노드 경로의 모든 노드 비교/교환
히프 응용
힙 정렬
- 정렬해야할 요소를 힙에 삽입. 각 요소들을 삭제해서 저장하면 정렬이 이뤄짐.
이산 이벤트 시뮬레이션
- 큐가 자주 사용되는 경우
많은 이벤트 발생, 우선순위에 따라 처리
허프만 코드
- 각 글자의 빈도가 알려진 메시지 내용 압축하는데 이진트리 사용
빈도수 높으면 적은 bit 를 사용한 코드로 메시지를 압축함.
고정길이코드 (ex. 3bit) -> 가변길이코드 (ex. 빈도↑시 2bit)
Ch9 그래프
그래프
연결되어 있는 객체간의 관계를 표현하는 자료구조이다.
정점 (Vertex)과 간선 (Edge) 로 구성된다.
그래프는 간선에 따라 두 종류로 나뉜다.
간선이 양방향 통행이면 무방향 그래프이며 이 경우 간선 (A, B) = 간선 (B, A) 이다.
간선이 일방 통행이면 방향 그래프이고, 간선 <A, B> != <B, A> 이다.
또한 간선에 가중치나 비용이 할당되는 경우에, 가중치 그래프라고 부른다.
그래프 표현법
인접행렬 방법
- 대각선 성분은 모두 0
- 무방향 그래프의 경우 인접행렬 대칭
인접리스트 방법
- 정점에 연결된 정정들을 연결리스트로 표현
그래프 탐색
DFS
- 깊이우선탐색은 트리의 전위 탐색 방법과 같다.
- 한 방향으로 끝까지 이동 후, 다시 돌아와서 탐색하는 방법이다.
BFS
- 너비우선탐색은 트리의 레벨 우선 탐색과 같다.
-시작정점과 가까운 정점들 먼저 순회하는 방법이다.
신장트리
그래프 내의 모든 정점을 포함하는 트리이다.
무방향 연결 그래프이며, 모든 정점이 연결되어 있고 사이클이 포함되면 안된다.
n개의 정점, n-1개의 간선을 가진다.
최소 신장트리 (Minimum Spanning Tree)
모든 정점을, 최소한의 간선과 비용으로 연결하는 신장트리이다.
신장트리 중 하나이고, 한 그래프에서 여러개의 MST가 존재할 수 있다.
MST 알고리즘
① Kruskal 알고리즘
- 그 때 그 때 가장 작은 가중치를 갖는 간선을 선택하는 방식
- 그리디 알고리즘
- 사이클 형성시 간선 제외
② Prim 알고리즘
- 시작 정점에서 신장 트리 집합을 단계적으로 확장해나가는 방법
- 앞 단계에서 만든 신장 트리 집합과, 인접한 정점 중 최저 간선으로 연결된 정점 선택
최단경로 알고리즘
- 정점 i에서 정점 j 까지 연결하는 경로 중 가중치 합이 최소가 되는 경로 찾기
Dijkstra의 최단경로 알고리즘
- 매 단계에서 가장 가중치가 적은 정점을 추가
위상정렬
- 그래프를 이용한 정렬 방법
- 각 노드의 선행 순서를 유지하면서 모든 정점 나열
위상 정렬 수행 단계
① 자신을 가리키는 변이 없는 정점 찾음
② 그 정점을 출력 및 제거, 그 정점과 연결된 간선 제거
③ 그래프에 정점이 남아있으면 ①->② 반복, 없으면 종료
Ch10 정렬
정렬
자료를 오름차, 내림차순으로 나열하는 것.
레코드>필드 이며, 레코드를 정렬한다.
정렬 알고리즘은 간단하게 단순비효율, 복잡효율 두 부류로 나뉘어진다.
문제마다 최적인 알고리즘이 다르다.
알고리즘은 비교횟수, 이동횟수에 따라 평가한다.
단순비효율
선택정렬
- 최소값을 선택해서 첫번째~다음 요소와 교환
삽입정렬
- 정렬된 부분에 레코드를 삽입하는 방식
버블정렬
- 인접한 레코드 순서대로 교환
복잡효율
분할정복법 : 문제를 2개의 문제로 분리해서 해결한 뒤, 결과를 모아서 원래 문제를 해결함
쉘정렬
- 전체 리스트를 일정 간격 부분으로 나눠서 부분 리스트 정렬
합병정렬
- 리스트를 균등 크기로 나눠서 부분 리스트 정렬
퀵정렬
- 전체 리스트를 균등 크기로 나누고, 각 부분 리스트에 퀵정렬 재귀호출
기수정렬
- 레코드(값)를 비교하지 않고 정렬 수행
정렬할 수 있는 레코드 타입이 정해져 있으나, O(dn)의 시간복잡도를 가짐
Ch11 탐색
탐색
여러 자료 중 원하는 자료를 찾는 작업이다.
항목들을 규별해주는 키인 탐색키가 존재한다.
순차 탐색 : 가장 간단하고 직접적인 탐색법 O(n)
이진탐색 : 정렬된 배열 탐색에는 이진탐색이 적합하다.
색인순차탐색(Indexed Sequential Search)
- 인덱스 테이블을 사용해서 탐색 효율성 증대
- 주, 인덱스 테이블은 모두 정렬이 되어 있어야 함
보간탐색(Interpolation Search)
- 탐색키 존재 위치 예측해서 탐색
- 불균등하게 분할하는 것이 특징
균형 이진 탐색 트리(AVL 트리)
- 이진 탐색 트리의 단점인, 불균형 상태가 되었을 때 효율 떨어지는 것 해결
- 삽입 삭제 시 균형 -> 불균형 을 막고자 회전 사용
Ch12 해싱
해싱
- 기존처럼 키 값의 비교 X
- 키 값에 직접 산술, 테이블의 주소를 계산해서 접근
해시테이블
- M개의 버켓으로 이뤄진 테이블
- 각 버켓은 s개의 슬롯을 가짐
충돌 : 서로 다른 두 탐색키가 동일 버켓의 주소에 저장
이런 충돌이 커져서 슬롯 수보다 늘어나면 오버플로우 발생
좋은 해시 함수의 조건
- 충돌 적음
- 해시함수 값이 해시테이블에 고르게 분포하게 됨
- 계산 빠름
충돌해결책
- 선형조사법 : 충돌 시 다른 위치에 저장
- 체이닝 : 연결리스트로 해시테이블 구조 변경
과목에서 배운 범위가 너무 방대해서 요약하기가 어려웠다.
원리만 알게되면, 실습 및 구현은 그리 어렵지 않다.
2-2 과목들은 이정도로 정리를 마친다..
'필요 > 전자공학' 카테고리의 다른 글
| [전공선택] 컴퓨터 네트워크 (0) | 2021.07.11 |
|---|---|
| [전공필수] 신호 및 시스템 리뷰 (0) | 2021.02.09 |
| [전공필수] 전자회로1 리뷰 (0) | 2021.01.31 |
| [전공선택] 현대물리학 리뷰 (1) | 2021.01.08 |
| 오토마타 교육 (0) | 2020.08.07 |