스택은 서브루틴 호출, 인터럽트 처리, 수식 계산 및 수식 표기법에 응용된다.
맞습니다. 스택은 데이터를 저장하고 관리하는 데에 사용되는 추상 자료 구조입니다. 이것은 주로 후입선출(LIFO) 방식으로 작동합니다. 스택은 프로그램의 서브루틴 호출과 반환, 인터럽트 처리, 재귀적 알고리즘, 수식 계산 및 수식 표기법 등에 널리 사용됩니다.
서브루틴을 호출하면 현재 실행 위치를 스택에 저장하고, 서브루틴이 끝나면 스택에서 이전 실행 위치를 복원하여 호출 위치로 돌아갈 수 있습니다.
인터럽트 처리에서는 인터럽트 발생 시 프로그램 상태를 스택에 저장하고, 인터럽트 처리가 끝나면 스택에서 이전 상태를 복원하여 프로그램이 중단된 지점부터 계속 실행할 수 있습니다.
수식 계산에서는 중위 표기법의 수식을 후위 표기법으로 변환한 다음 스택을 사용하여 계산할 수 있습니다. 수식을 후위 표기법으로 변환하면 연산자 우선순위 문제를 해결하고 스택을 사용하여 계산할 때 괄호를 제거할 수 있습니다.
따라서 스택은 다양한 프로그래밍 문제를 해결하기 위한 중요한 자료 구조 중 하나입니다.
서브루틴은 프로그램에서 반복적으로 사용되는 일련의 명령문 집합을 하나의 논리적인 단위로 묶은 것을 말합니다. 이를 함수, 프로시저, 메서드 등 다양한 용어로 부르기도 합니다.
서브루틴은 프로그램의 모듈화와 재사용성을 증가시키는 데 중요한 역할을 합니다. 반복적으로 사용되는 코드를 서브루틴으로 추출하면, 코드의 중복을 줄이고 유지 보수성과 가독성을 향상시킬 수 있습니다.
서브루틴은 호출되어 실행되고, 실행이 끝나면 호출자로 되돌아갑니다. 서브루틴이 호출되면 호출자의 실행 위치와 데이터를 스택에 저장하고, 서브루틴이 끝나면 스택에서 이전 상태를 복원하여 호출자로 되돌아갈 수 있습니다. 이 과정을 서브루틴 호출과 반환이라고 합니다.
서브루틴은 다양한 프로그래밍 언어에서 지원되며, 프로그램의 구조를 설계하는 데 있어서 매우 유용합니다.
인터럽트(Interrupt)는 컴퓨터에서 하드웨어나 소프트웨어에서 발생하는 예기치 않은 상황을 말합니다. 예를 들어, 입출력(I/O) 작업이 완료되었거나, 타이머 인터럽트, 외부 인터럽트(하드웨어 장치의 상태 변화 등) 등이 발생할 수 있습니다.
인터럽트는 실행 중인 프로그램을 중단하고, 인터럽트 처리 루틴(Interrupt Service Routine, ISR)이라는 특별한 코드를 실행합니다. 이때 프로그램의 상태(레지스터 값, 명령어 포인터 등)는 스택에 저장됩니다.
인터럽트 처리는 인터럽트 우선순위에 따라 처리되며, 우선순위가 높은 인터럽트가 발생하면 현재 실행 중인 인터럽트 처리를 중지하고 높은 우선순위의 인터럽트 처리를 수행합니다.
인터럽트 처리가 끝나면, 이전 상태로 되돌아가기 위해 스택에서 저장된 프로그램의 상태를 복원합니다. 그리고 인터럽트 처리 이후에는 중단된 프로그램이 이어서 실행됩니다.
인터럽트는 시스템의 실시간 처리와 다양한 장치 드라이버의 구현에 중요한 역할을 합니다. 인터럽트 처리는 하드웨어적으로 지원되며, 운영체제와 드라이버에서 이를 제어하고 사용합니다.
큐(Queue)는 선형 자료구조의 일종으로, 선입선출(First-In-First-Out, FIFO)의 특성을 가지고 있습니다. 즉, 먼저 들어온 데이터가 먼저 처리되고, 나중에 들어온 데이터는 나중에 처리됩니다.
큐는 선형적인 형태로 데이터가 쌓이지만, 선형 자료구조의 종류 중에서는 비선형 구조에 해당합니다. 이는 큐에 데이터를 추가하거나 제거할 때, 선형적으로 이동하는 것이 아니라, 큐의 끝에서만 추가하고, 앞에서만 제거하기 때문입니다.
큐는 대기열(Queue)이나 버퍼(Buffer) 등으로 많이 사용되며, 운영체제나 네트워크 등에서 프로세스나 데이터를 처리할 때 많이 활용됩니다. 또한, BFS(Breadth-First Search)와 같은 그래프 탐색 알고리즘에서도 사용됩니다.
로킹(Locking)은 여러 개의 스레드 또는 프로세스에서 공유하는 자원에 대한 접근을 동기화하는 기술입니다. 다시 말해, 여러 스레드나 프로세스가 동시에 같은 자원에 접근할 때, 이들 간의 상호작용을 조절하고 충돌을 방지하는 기술입니다.
로킹의 주요 목적은 상호배제(Mutual Exclusion)입니다. 상호배제란, 한 스레드나 프로세스가 어떤 자원을 사용하는 동안 다른 스레드나 프로세스가 그 자원에 접근하지 못하도록 막는 것을 의미합니다. 이를 위해 뮤텍스(Mutex), 세마포어(Semaphore), 모니터(Monitor) 등의 동기화 기법을 사용합니다.
로킹은 또한 교착상태(Deadlock) 방지를 위해서도 사용됩니다. 교착상태란, 둘 이상의 프로세스나 스레드가 서로 다른 자원을 점유하고 대기하면서 아무것도 진행되지 않는 상태를 말합니다. 로킹을 이용하여 프로세스나 스레드가 자원을 사용한 후 반드시 로킹을 해제하도록 하여 교착상태를 방지할 수 있습니다.
로킹은 데이터베이스, 운영체제, 멀티스레드 환경 등에서 사용됩니다. 로킹은 전체 시스템의 성능에 큰 영향을 미치므로 적절한 로킹 전략을 수립하여 자원의 동시 접근 문제를 해결해야 합니다.
로킹 단위는 로킹의 대상이 되는 객체의 크기를 의미합니다. 객체는 보통 데이터 구조의 형태로 표현되며, 예를 들어 배열, 링크드 리스트, 트리, 데이터베이스 레코드 등이 로킹 단위가 될 수 있습니다.
로킹 단위의 크기는 로킹 전략의 성능에 영향을 미치며, 로킹 단위가 작을수록 병행성 수준이 높아져서 더 많은 스레드나 프로세스가 동시에 접근할 수 있게 됩니다. 하지만 로킹 단위가 작아질수록 로킹 오버헤드가 증가하게 되므로, 적절한 로킹 단위를 선택하는 것이 중요합니다.
또한 로킹 단위는 동시에 여러 스레드나 프로세스에서 접근 가능한 자원의 단위를 결정합니다. 예를 들어, 로킹 단위가 전체 데이터베이스인 경우, 데이터베이스의 어떤 부분에 접근하더라도 전체 데이터베이스가 로킹되므로 다른 스레드나 프로세스가 접근하지 못합니다. 반면에 로킹 단위가 레코드인 경우, 다른 스레드나 프로세스는 다른 레코드에 접근할 수 있습니다. 따라서 로킹 단위를 적절하게 선택하여 병행성 수준과 로킹 오버헤드를 균형 있게 유지해야 합니다.
로킹 단위가 작아질수록 로킹 오버헤드가 증가하는 이유는 다음과 같습니다.
먼저, 로킹을 수행하면서 다른 스레드나 프로세스가 해당 자원에 접근할 때 대기해야 합니다. 로킹 단위가 작아질수록 동시에 접근 가능한 자원의 수가 줄어들게 되므로, 다른 스레드나 프로세스들이 대기할 확률이 높아지게 됩니다.
또한, 로킹을 수행할 때마다 적어도 하나의 로크(락을 획득한 상태)를 유지해야 합니다. 로킹 단위가 작아질수록 로크의 수가 증가하게 되므로, 로크 관리 오버헤드도 증가합니다.
따라서 적절한 로킹 단위를 선택하는 것이 중요합니다. 로킹 단위가 작으면 병행성 수준이 높아져서 동시에 접근 가능한 자원의 수가 늘어나지만, 로킹 오버헤드가 증가하게 됩니다. 반면에 로킹 단위가 커지면 로크 수가 작아지므로 로킹 오버헤드는 감소하지만 병행성 수준이 낮아져서 동시에 접근 가능한 자원의 수가 줄어들게 됩니다. 적절한 로킹 단위를 선택하여 병행성 수준과 로킹 오버헤드를 균형 있게 유지해야 합니다.
데이터베이스의 3층 스키마는 외부 스키마, 개념 스키마, 내부 스키마로 구성됩니다. 각각의 스키마는 데이터베이스 시스템에서 다른 관점에서 데이터베이스를 볼 수 있도록 하는 역할을 합니다.
개념 스키마는 모든 응용 시스템과 사용자들이 필요로 하는 데이터를 통합한 조직 전체의 데이터베이스 구조를 논리적으로 정의하는 스키마입니다. 즉, 데이터베이스 시스템에서 전체적인 데이터베이스 구조를 정의하는 스키마로, 데이터의 논리적 구조를 기술합니다.
반면에 내부 스키마는 개념 스키마에 의해 정의된 데이터 구조를 물리적인 저장장치의 관점에서 기술하는 스키마이며, 외부 스키마는 사용자나 응용 프로그램이 접근할 수 있는 데이터의 논리적 구조를 기술하는 스키마입니다.
외부 스키마(External Schema)는 데이터베이스에서 사용자나 응용 프로그램이 접근할 수 있는 데이터의 논리적 구조를 기술하는 스키마입니다. 즉, 개념 스키마에서 정의된 전체 데이터베이스 구조 중에서 특정 사용자나 응용 프로그램이 필요로 하는 부분만을 추출하여 정의하는 것입니다.
외부 스키마는 각각의 사용자나 응용 프로그램이 필요로 하는 데이터의 구조와 내용을 정의하므로, 각 사용자 또는 응용 프로그램의 요구사항에 맞게 데이터를 구성할 수 있습니다. 이렇게 외부 스키마를 사용하면, 사용자나 응용 프로그램은 개념 스키마나 내부 스키마에 대한 지식 없이도 데이터에 접근할 수 있으며, 데이터의 논리적 구조를 변경해도 사용자나 응용 프로그램에 영향을 미치지 않습니다.
릴레이션(Relation)은 데이터베이스에서 가장 기본적인 데이터 구조 중 하나로, 행과 열로 이루어진 2차원 형태의 테이블을 말합니다. 각 행은 레코드(Record) 혹은 튜플(Tuple)이라고 불리며, 열은 속성(Attribute)이라고 불립니다. 릴레이션은 관계형 데이터베이스에서 가장 기본적인 데이터 저장 구조로 사용되며, SQL을 비롯한 대부분의 관계형 데이터베이스 관리 시스템(RDBMS)에서 사용됩니다.
관계형 데이터베이스에서 정규형은 데이터의 중복을 최소화하고 삽입, 갱신, 삭제 이상(Anomalies)을 방지하기 위한 일련의 규칙을 의미합니다. 보다 정규화된 데이터 모델은 적은 양의 데이터로 목표를 달성할 수 있으며, 데이터 일관성을 유지할 수 있고 데이터베이스의 성능을 향상시킬 수 있습니다.
① 제 3 정규형(3NF) : 어떤 릴레이션의 모든 속성이 기본키에 대해 이행적 함수 종속을 갖지 않는 정규형입니다. 이는 테이블에서 중복된 정보를 제거하며, 동일한 정보를 갖는 복수의 행을 허용하지 않습니다. 이 정규형을 만족하면, 각 속성이 독립적으로 변화할 수 있고 데이터베이스의 크기를 줄일 수 있습니다.
② 보이스-코드 정규형(BCNF) : 모든 결정자가 후보키인 정규형입니다. 이 정규형은 제 3 정규형을 만족하면서, 모든 함수 종속이 결정자가 되는 최소한의 키로 분해된 릴레이션입니다. 이를 통해 삽입, 갱신, 삭제 이상을 방지하고, 데이터 일관성과 정확성을 보장할 수 있습니다.
③ 제 4 정규형(4NF) : 어떤 릴레이션의 다중값 종속을 처리하는 정규형입니다. 다중값 종속이란, 한 릴레이션의 튜플이 하나 이상의 복수값(multivalued) 속성에 의해 종속되는 경우입니다. 이를 분해하여 더 작은 릴레이션들을 만들어 데이터의 중복을 제거하고, 테이블 간 조인 작업을 최소화합니다.
④ 제 5 정규형(5NF) : 어떤 릴레이션에서 조인에 의해 발생하는 종속 관계를 처리하는 정규형입니다. 이를 위해 다중값 종속을 이용하여 릴레이션을 분해합니다. 이러한 분해를 통해 삽입, 갱신, 삭제 이상을 방지할 수 있습니다. 제 5 정규형은 BCNF와 유사하지만, 좀 더 세부적인 분해를 수행합니다.
보이스-코드 정규형은 다치형 튜플이 없는 정규형으로, 릴레이션 R의 모든 조인 종속성이 후보키에 대해서만 성립되는 정규형입니다.
보이스-코드 정규형의 예시를 들어보면, 학생과 과목 간의 점수를 저장하는 테이블이 있다고 가정해봅시다. 이 테이블에서는 학생과 과목을 기본키로 사용하고, 점수를 저장하는 속성을 포함합니다.
하지만 이 테이블에서는 하나의 학생이 여러 과목을 수강하는 다치형 튜플이 존재할 수 있습니다. 예를 들어, "John" 학생이 "Math", "Science" 두 과목을 수강한다면, 해당 테이블에는 다음과 같은 튜플이 존재할 수 있습니다.
```
John | Math | 80
John | Science | 90
```
이러한 다치형 튜플은 보이스-코드 정규형을 위반하며, 이를 해결하기 위해서는 학생과 과목을 기본키로 하는 테이블과, 학생별 점수를 저장하는 별도의 테이블을 생성해야 합니다. 이렇게 하면 다치형 튜플을 없앨 수 있고, 보이스-코드 정규형을 만족할 수 있습니다.
해시 함수는 데이터베이스에서 효율적인 데이터 검색을 위해 사용됩니다. 이때 해시 함수는 데이터를 특정 위치에 매핑하여 데이터를 저장하고 검색하는 과정에서 시간과 메모리를 절약할 수 있도록 도와줍니다.
중첩 방법은 주어진 키를 여러 부분으로 나누어 해시 주소를 계산하기 때문에 해시 값의 분포를 더 균등하게 할 수 있습니다. 또한 중첩 방법은 키의 길이가 가변적인 경우에도 적용이 가능하며, 입력된 데이터의 크기가 해시 함수의 크기보다 클 때에도 처리가 가능합니다. 따라서 중첩 방법은 키의 분포가 고르지 않거나 가변적인 경우에 사용됩니다.
1. 중간 제곱 방법(Mid-square method): 키 값을 제곱한 후, 중간 부분의 몇 개 숫자를 취해 해시 값을 만드는 방법입니다. 예를 들어, 키 값이 3465이면 3465² = 11982225이 됩니다. 여기서 중간의 두 숫자 82를 취하여 해시 값을 만들 수 있습니다. 중간 제곱 방법은 무작위로 분포된 키 값에 대해서는 잘 작동하지만, 일정한 패턴을 갖는 키 값에 대해서는 충돌이 발생할 수 있습니다.
2. 제산 방법(Division method): 해시 테이블의 크기로 나누어 나머지 값을 해시 값으로 취하는 방법입니다. 예를 들어, 해시 테이블의 크기가 10이고 키 값이 1234이면, 1234 % 10 = 4가 됩니다. 제산 방법은 간단하고 빠르지만, 일부 키 값에 대해서는 충돌이 발생하기 쉽습니다.
3. 중첩 방법(Folding method): 키 값을 여러 부분으로 나누어 각 부분을 더하거나 배타적 논리합(XOR) 연산을 통해 해시 값을 만드는 방법입니다. 예를 들어, 키 값이 123456이고 해시 테이블의 크기가 100이면, 키 값을 12, 34, 56으로 나누어 각 부분을 더하면 12 + 34 + 56 = 102가 됩니다. 102를 100으로 나눈 나머지인 2가 해시 값이 됩니다. 중첩 방법은 키 값에 대한 패턴을 잘 반영하며 충돌이 적은 편입니다.
4. 기수 변환법(Radix conversion method): 키 값을 어떤 기수(진법)에서 다른 기수로 변환하여 해시 값을 만드는 방법입니다. 예를 들어, 키 값이 1234이고 해시 테이블의 크기가 100이면, 1234를 16진법으로 변환하여 4D2가 됩니다. 이 값을 100으로 나눈 나머지인 42가 해시 값이 됩니다. 기수 변환법은 키 값에 대한 패턴을 잘 반영하며 충돌이 적은 편입니다.
이진 검색(binary search)은 정렬된 리스트에서 특정한 값을 찾아내는 검색 알고리즘 중 하나입니다. 이진 검색은 주어진 리스트를 두 개의 sub-list로 나누어서, 찾고자 하는 값이 sub-list의 중간값보다 크면 뒷 부분의 sub-list에서, 작으면 앞 부분의 sub-list에서 검색을 계속하며 값을 찾아냅니다.
주어진 레코드에서 이진 검색으로 14를 찾는 경우, 처음 리스트의 중간값은 8입니다. 14는 8보다 크기 때문에 뒷 부분의 sub-list에서 검색을 계속해야 합니다. 뒷 부분의 sub-list에서 중간값은 12이고, 14는 12보다 크기 때문에 다시 뒷 부분의 sub-list에서 검색을 계속합니다. 이때 중간값은 15이며, 14는 15보다 작기 때문에 앞 부분의 sub-list에서 검색을 계속합니다. 마지막으로 중간값이 13인 앞 부분의 sub-list에서 14를 찾게 됩니다. 이 과정에서 비교되는 횟수는 3회입니다.
제 5 정규형은 다중값 종속(multivalued dependency)을 해결하기 위한 정규형 중 하나입니다. 다중값 종속은 한 릴레이션의 튜플에서 여러 개의 속성 값들이 함께 다른 릴레이션에 종속되는 현상입니다.
예를 들어, 학생 릴레이션에서 학생 이름, 과목명, 성적이라는 속성들이 있을 때, 하나의 학생이 여러 개의 과목을 수강하면 그 학생에 대한 정보가 여러 개의 튜플에 중복되어 저장될 수 있습니다. 이 경우, 학생 이름과 성적이라는 속성 값은 과목명이라는 속성 값에 종속되는 다중값 종속이 성립합니다.
제 5 정규형은 이러한 다중값 종속을 해결하기 위해, 다중값 종속을 갖는 속성들을 각각 새로운 릴레이션으로 분리하는 과정을 거칩니다. 이를 통해 릴레이션 간에 일대다 관계가 성립하게 되고, 이러한 분해 과정을 통해 모든 릴레이션은 후보키에 의해서만 결정되도록 만들어집니다.
SQL의 뷰(view)에는 다음과 같은 장점이 있습니다:
1. 데이터 보안 향상: 뷰를 사용하면 사용자가 직접 테이블에 접근하는 것을 허용하지 않고, 뷰를 통해 필요한 데이터만 제공하여 데이터 보안을 향상시킬 수 있습니다.
2. 데이터 독립성: 뷰를 사용하면 테이블의 물리적 구조나 테이블간의 관계가 변경되어도 응용 프로그램에 영향을 주지 않고 뷰를 변경함으로써 데이터 독립성을 유지할 수 있습니다.
3. 데이터 무결성 유지: 뷰를 통해 필요한 데이터만 조회하므로, 뷰를 사용하면 테이블의 데이터 무결성을 보장할 수 있습니다.
4. 간편한 데이터 접근: 뷰를 사용하면 특정 조건을 만족하는 데이터에 쉽게 접근할 수 있으며, 복잡한 SQL 쿼리를 작성하지 않고도 데이터를 쉽게 조회할 수 있습니다.
5. 성능 향상: 뷰를 사용하면 불필요한 데이터를 제외한 필요한 데이터만 조회할 수 있으므로, 쿼리의 처리 속도가 빨라질 수 있습니다.
6. 재사용성: 뷰를 만들면 다른 쿼리에서도 재사용할 수 있으며, 쿼리 작성 시간이 줄어듭니다.