타입은(는) 여기로 연결됩니다.
유형(類型)에 대한 내용은
유형 문서 참고하십시오.|
'''
이론 컴퓨터 과학 {{{#!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 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[clearfix]
1. 개요
자료형(타입, type)이란 프로그래밍 언어에서 변수 또는 값이 가질 수 있는 데이터의 종류를 의미하며, 자료형의 연산, 변환, 해석 방법, 추론 등 일련의 규칙을 정의한 것을 타입 시스템이라고 한다. 타입은 각 언어의 문법적 요소와 실행 시의 안정성을 보장하는 중요한 역할을 한다.Low-level 관점에서 자료형 및 타입 시스템은 값을 해석하는 방법을 제공한다.
C++로 예를 들어 보면, int와 float 같은 자료형은 실제 하드웨어에서는 모두 1과 0으로 표현되는 바이너리 비트스트림에 불과하다. cout 등을 이용해 이 값을 출력한다고 할 때, 어떻게 int는 최종적으로 정수 꼴로 출력되도록 해석하고 float은 실수 꼴로 출력되도록 해석할 수 있을까? 이는 컴파일러가 타입 시스템을 바탕으로 int형 변수는 int에 맞는 출력이 일어나도록, float은 float에 맞는 출력이 일어나도록 미리 결정했기 때문이다. 즉, 타입 시스템이 바이너리 스트림으로만 존재하는 정보를 의미 있는 값으로 해석할 수 있는 방법을 제공한 것이다.High Level 관점에서 자료형 및 타입 시스템은 프로그램이 잘 정의된 의미를 가지는지 알려주는 역할을 한다. 예를 들어, x를 String 변수, y를 Boolean 변수라고 하자. 만약 다음과 같은 코드를 실행시킨다고 할 때, z의 값은 무엇이 되어야 할까?
#!syntax go z := x + y String과 Boolean을 합(+)하는 것은 통상적인 의미를 가지는 연산이 아니기 때문에, 대부분의 프로그래밍 언어에서는 이 연산을 의미가 없는, 잘못 작성된 프로그램이라고 생각하고 오류를 일으킬 것이다. (물론 프로그래밍 언어가 가지는 타입 시스템이 해석하기에 따라 이 연산도 정의될 수도 있다) 즉, 이 프로그램은 타입 시스템의 관점에서 의미가 제대로 정의되지 않은 것으로, 이 코드를 실행시킨 결과는 무의미 / 정의되지 않는 다는 것을 타입 시스템이 알려줄 수 있다.이 외에도, 타입 시스템은 코드의 문서 역할을 할 수 있다. 예를 들어, 함수의 파라미터와 반환 타입을 명시함으로써, 해당 함수의 사용 방법과 기대되는 결과를 이해하는 데 도움을 줄 수 있다.
1.1. 엄밀한 정의(Type Theory)
2. 타입 시스템의 종류
프로그래밍 언어에 대한 한 가지 오해는 어떤 언어는 '타입 시스템' 자체가 존재하지 않는다는 것이다. 그러나 실제로는 그렇지 않다. 타입 시스템은 프로그래밍 언어가 (코드나 메모리상에 존재하는) 값을 해석하고, 다루는 방식을 정의한 것이기 때문에 모든 언어는 어떤 형태로든 타입 시스템을 가질 수밖에 없다. 이것이 혼동되는 이유는 '컴파일 시간에 타입 체크'를 하지 않는 언어들은 타입을 굳이 달아줄 필요가 없어 사실상 타입이 존재하지 않는 것처럼 느껴지기 때문이다.2.1. 동적 타입 시스템
동적으로 타입되는 언어들은 변수의 타입이 실행 시간에 결정된다. 대표적인 예로 Python, JavaScript 등이 있다. 유연성이 높고, 빠르게 개발할 수 있다는 장점이 있으나 런타임에 타입 오류가 발생할 수 있으며, 타입 체크를 런타임에 실시하므로 속도에서 손해를 볼 수 있다.2.2. 정적 타입 시스템
정적으로 타입되는 언어들은 변수의 타입이 컴파일 시간에 결정된다. 컴파일러를 거치는 대부분의 언어가 포함되며, C++, Java, TypeScript, OCaml, Haskell 등이 이 범주에 속한다. 정적 타입 시스템의 가장 강력한 장점은 (타입 시스템이 sound한 type check를 한다는 기본적인 전제하에) 컴파일이 타입 체크를 통과했다면 런타임에 타입 오류가 발생하지 않는다는 것이다. 그러나 타입 추론 알고리즘이 충분히 강력하지 않으면 타입을 꽤 많이 명시해야 하므로 코드 작성이 귀찮아지며 코드의 유연성이 감소할 수 있다.3. 타입의 종류
3.1. 일반적인 타입
정수형(Integer), 실수형(Float), 문자열(String) 등은 대부분의 프로그래밍 언어에서 기본적으로 제공하는 타입들이다. 이들은 데이터의 가장 기본적인 형태를 나타내며, 일상적인 프로그래밍 작업에서 널리 사용된다.3.2. 특정 프로그래밍 패러다임, 언어의 타입
4. 다형성
4.1. 애드혹 다형성(Ad-hoc Polymorphism)
애드혹 다형성은 함수 오버로딩 또는 연산자 오버로딩을 통해 다양한 타입의 인자에 대해 같은 함수나 연산자를 사용할 수 있도록 하는 기능이다.4.2. 서브타입 다형성(Subtype Polymorphism)
서브타입 다형성은 하나의 타입이 다른 타입의 하위 타입으로 간주될 수 있는 경우를 의미한다. 예를 들어, 모든 클래스가 최상위 클래스인 Object의 서브타입인 Java에서는 Object 타입의 변수에 어떤 클래스의 인스턴스도 저장할 수 있다.4.3. 파라메트릭 다형성(Parametric Polymorphism)
파라메트릭 다형성은 타입을 매개 변수로 취급하여 다양한 타입에 대해 동일한 코드를 재사용할 수 있는 기능이다. 예를 들어, C++의 템플릿 또는 Java의 제네릭이 이에 해당한다.5. 타입 추론
타입 추론은 프로그래머가 명시적으로 타입을 선언하지 않아도 프로그래밍 언어의 컴파일러나 인터프리터가 자동으로 변수의 타입을 결정하는 기능이다. 정적 타입 시스템을 가진 언어는 런타임에 타입 오류가 발생하지 않는다는 매우 강력한 장점이 있지만 타입을 명시해 줘야 하는 부분 때문에 불편하게 느껴지기도 하는데, 강력한 타입 추론이 가능하다면 개발자가 따로 타입을 명시해 줄 필요가 없어 두 가지 장점을 모두 사용할 수 있게 된다.예를 들어, C++ 11부터는
auto 키워드를 활용해 자동으로 타입을 채우도록 할 수 있는데, 이 덕분에#!syntax cpp
vector<int>::const_iterator i = v.begin();
#!syntax cpp
auto i = v.begin();
let rec fib n =
if n < 2 then n
else fib (n-1) + fib (n-2)
fib가 int -> int 타입의 함수임을 추론해 주는데, 그 이유는 Ocaml에서 +와 -가 int -> int -> int 형식의 operator임을 기반으로 하여 함수의 타입 시그니처를 결정할 수 있는 강력한 타입 시스템인
HM 타입 시스템을 사용하고 있기 때문이다.