| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
1. 정의
資料構造 / data structure컴퓨터과학에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론, 혹은 과목. 컴퓨터과학에서 알고리즘과 함께 가장 중요한 기초이론이다. 이것을 공부하지 않고 상위 과목을 공부하는 건 사실상 불가능하다. 영어로 치면 알파벳을 모르는 상태로 독해를 공부하겠다는 것과 마찬가지로 볼 만큼 프로그래밍에서 중요한 부분이다.
컴퓨터의 메모리는 1차원 구조이기 때문에[1] 현실 세계의 다차원 데이터를 다루기 위해서는 이것을 1차원인 선 형태로 바꾸는 것이 필요하다. 대학교 학부과정에서 배우는 기초 알고리즘들은 바로 이 방법을 학습한다. 2차원 배열, 이진 트리, 그래프 등의 자료구조가 2차원 데이터를 1차원으로 욱여넣는 방법을 배우는 것이다. 더 나아가 3차원 데이터를 다루고, 더 지나면 3차원 데이터 이상의 다차원 데이터를 처리하는 자료구조를 만날 수 있다. 물론 B트리나 R트리의 경우처럼 같은 2차원 데이터도 어떻게 조직화하느냐에 따라 자료구조가 달라진다.
리스트, 스택, 큐, 환형 큐, 힙, 트리, 그래프 7가지 개념을 숙지하면 자료구조 대부분 이해한 것이라 보면 된다.
2. 추상적 자료형과의 관계
추상적 자료형은 알고리즘이 문제를 해결하는데 필요한 자료의 형태와 자료를 사용한 연산들을 수학적으로 정의한 모델이다. 그리고 자료구조는 추상적 자료형이 정의한 연산들을 구현한 구현체를 가리키는 말이다.스택의 예를 들면, 함수 호출을 관리하기 위해 후입선출의 성질을 가진 추상적 자료형이 필요하니pop과 push를 가지도록 스택이라는 추상적 자료형을 정의하고, 그것을 구현해서 함수 호출을 관리하는데 사용하는 구현체, 즉 자료구조를 콜 스택이라고 부르는 것이다. 따라서 자료구조와 추상적 자료형은 구분해 쓰는 것이 맞지만, 자료구조라는 단어가 광범위하게 쓰이다보니 추상적 자료형을 가리키는 데 쓰이는 일도 부지기수다. 혼란의 가장 큰 원인은 추상적 자료형과 그것을 구현한 자료구조의 이름이 비슷하거나 아예 같은 경우가 아주 많다는 것. 콜 스택이 스택을 구현한 자료구조의 이름이고, 연결 리스트가 리스트를 구현한 자료구조 중 하나라거나. 게다가 추상적 자료형을 구현하는 데 하위에 다른 추상적 자료형들을 정의해서 그것들을 자료구조로 구현한다거나, 자료구조를 구현할때도 마찬가지로 다른 자료구조를 가져다 쓰는 경우가 많다보니 쉽게 헷갈린다.
제대로 구분하는 방법은 조금이라도 구현 방법이 정해져 있는지 보는 것. 스택은 구현방법이 전혀 정의되어 있지 않으니
3. 컴퓨터공학과의 과목
학교에서는 주로 기초 컴퓨터 프로그래밍 언어를 익힌 후 배우므로, 대학교 컴퓨터 계열 학과의 1학년 2학기에서 2학년 1학기 쯤 대부분 수강하게 되며, 가끔가다 1학년 1학기에 같이 시작하는 곳도 있다. 다만 정보계열 실업계 고등학교 학생들의 경우 2학년부터 배우게 되는데 덕분에 프로그래밍 기초나 작업과 같은 과목에 대해선 의외로 강세를 보이기도 한다. 다만, 과목 이름만 자료구조이고, 엑셀, 파워포인트 등을 하는 경우도 있다.간단한 리스트부터 수업에 따라 B-트리까지 익히는 편이다. 이 과목이 자료구조를 직접 활용하기 때문에 중요하다기 보다는, 프로그램을 작성할 때 되는대로 막 짜는 게 아니라 한 번이라도 전체적인 프로그램의 흐름(혹은 구조)에 대해 생각하게 만들기 때문에 중요하다. 한국에서 거의 이러한 일이 일어나지 않지만, 운영체제 또는 특정 목적으로 동작하는 프로그램 엔진 등을 제작하게 될 때에는 정말 잘 알아야 하는 과목이다. 자료 구조에 따라 프로그램 자체의 지원 가능한 기능과 성능 자체가 확확 바뀌는 경우가 발생하기 때문이다. 이러저러한 이유로 여러 컴퓨터과학 전공과목 중에서 전공심화 과목들은 기본적으로 이 과목을 요구하는 경우가 많다.
정렬과 이진 탐색은 엄밀히 말해 자료구조가 아닌 알고리즘에 속하지만, 배열 등의 자료구조와 밀접하게 연관되고 알고리즘 중에서도 비교적 쉬운 축에 속하므로 대부분 함께 배우는 경우가 많다. 자료구조도 좀 깊이 들어가 보면 어떤 알고리즘을 사용하기 위해 개발된 것들이 많다.
강의에서는 주로 다음과 같은 내용을 다루게 된다.
- 알고리즘 분석 방법: 시간 복잡도. Big-O 기호를 정의한다. 예: O(n), O(n2)
- 선형 리스트: 스택, 큐
- 힙 정렬
- 연결 리스트: 단일 연결 리스트, 이중 연결 리스트
- 정렬 알고리즘: 병합 정렬, 퀵 정렬 등
- 이진 탐색 트리
- 그래프: 순회 (DFS, BFS), Minimum Spanning Tree (크루스칼 알고리즘, Prim)
- Hashing Table
4. 자료구조의 예
- 혼합 자료구조(Composite Data Structure)
- 배열 (Array)
- 선형 자료구조(Linear Data Structure)
- 추상적 자료구조(Abstract Data Structure)
- 딕셔너리 자료구조 (Dictionaries)
- 연관 배열 (Associative array.) Map이라고 칭하기도 한다.
- 연관 리스트
- 해시 테이블
5. 여담
데이터를 컴퓨터로 처리하는 방식을 다루는 것이기 때문에, 구현을 생각하지 않는 아주 추상적인 이론이 아닌 이상 반드시 사용해야만 하는 기초 이론이다.자신이 프로그래머가 되고 싶다면 최소한 연결 리스트와 이진 트리는 평생 머릿속에 담아두고 있어야 한다. 이 두 자료구조를 이해하지 못하면 스스로 알고리즘을 설계하는 데 엄청난 애로사항이 꽃핀다. B트리나 AVL트리 같은 건 몰라도 된다. 따지고 보면 B트리와 AVL트리는 그냥 균형이 자동으로 잡히는 이진 트리로, 전용 알고리즘에 의해 관리되는 특수 자료구조에 불과하다. 즉 이진 트리의 응용형이다. 그래프는 연결 리스트의 응용형. 이진 트리는 그래프에 어떤 제약이 가해진 특수 형태. 이런 식으로 가지쳐 나가는 거라(책에 따라 반대로 서술하는 경우가 있다. 그래프는 이진 트리에서 제약을 제거한 거라는 식으로) 저 두 자료구조는 가장 중요하다.
Python이 인기 있는 이유 중 하나는 파이썬의 기본 자료구조인 리스트, 튜플, 딕셔너리가 사용하기 편리하며 데이터를 다루는 데 효과적이기 때문이다. 하지만 Python은 정작 자료구조 구현 실습에는 좋지 않은 언어인데 리스트, 튜플, 딕셔너리 같은 기본 자료구조들이 C로 빠르게 구현되어 있고, Python에서 만든 프로그램 만으로는 절대로 저런 기본 자료구조들의 속도를 따라잡을 수 없기 때문에 Python에서 직접 연결 리스트 같은 것을 구현하는 것은 실용성이 없다. 그래서 Python으로 자료구조나 알고리즘을 실습한다면 최소한 그래프, 트리, 혹은 추상대수학에서 쓰이는 군, 다항식, 텐서 자료구조 이상은 가야 Nontrivial하게 구현해야 할 의미가 있고 이건 이런 자료구조들이 리스트, 튜플, 집합, 클래스 위에 파생해야 만들 수 있기 때문이다. 면접 등의 상황에서 Python을 쓴다는 것을 어필하려면 Python을 써서 Nontrivial하게 풀 수 있다는 것을 증명해야 하기 때문에 Python으로 시작했다면 그만큼 수학적으로 어려운 문제를 건드려야 한다는 점을 명심하자.
전산직 공무원 (전산 개발) 시험에서는 9급의 경우 컴퓨터일반 과목에서, 7급의 경우 자료구조론 과목에서 다뤄지는 내용이다.
컴퓨터 관련 학과 학생들을 굉장히 힘들게 하는 과목 중 하나인데, 기초 프로그래밍에 비해 난이도가 확 뛰는 데다가 자료구조를 모르면 이후 과목을 이해할 수도 없기 때문에 좋건 싫건
6. 관련 항목
[1] 메모리 하드웨어는 2차원 또는 3차원 구조이지만 CPU에서 논리적으로 바라보는 메모리 공간은 1차원이다.[2] 자료구조를 모르면 알고리즘을 이해하는 거 자체가 불가능하고, 이 두 과목을 통달하지 못한다면 코딩 테스트 문제는 건드릴 수도 없다. 그래도 혼자 자료를 찾아 공부하다 보면 프로그램을 빌드할 수는 있지만, 최적화 능력이 매우 떨어지거나 취업 시 전공면접에서 대차게 박살날 가능성이 높다. 어찌저찌 취업은 성공하더라도 CS지식이 딸린다면 커리어에 한계가 있다.[3] 보통 자료구조 미이수자는 이후 과목 수강신청이 아예 시스템상으로 거부되거나, 수업 첫날에 교수가 쫒아낸다.