지금까지의 자료구조 복습

1. 자료구조란 무엇인가? (정의)
answer : 사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이를 자료 구조라고 한다. 맨 위에서 자료를 추가하고 제거하는 "스택" 혹은 먼저 도착한 자료가 먼저 빠져나가는 "큐" 등을 우리는 자료 구조라고 부른다.

2. 알고리즘이란 무엇이고 어떻게 표현하는가?
answer : 우리는 대부분의 프로그램에서 데이터를 처리하고 있고 이러한 데이터는 자료구조를 사용하여 저장된다. 또한 주어진 문제를 처리하는 절차가 필요한데 이를 알고리즘이라고 부른다. 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것으로 알고리즘은 특정한 일을 수행하는 명령어들의 집합으로 볼 수 있다. 또한 이러한 알고리즘은 한글이나 영어와 같은 자연어, 흐름도(flowchart), 의사 코드(pseudo code) 그리고 프로그래밍 언어로 표현된다.

3. 자료구조에서 보는 자료형은 어떤 것들이 있는가?
answer : 자료형이란 데이터으 종류를 의미하는데 정수, 실수, 문자열 등이 기조적인 자료형이다. 이러한 자료형은 프로그래밍 언어가 기본적으로 제공하고 스택, 큐, 리스트, 트리와 같은 새로운 자료형들을 추가할 수 있다. c언어 에서는 기초자료형인 char, int, float, double 등 이 있고 파생 자료형으로는 배열과 포인터를 예시로 들 수 있다. 또한 사용자 정의 자료형으로는 구조체, 공용체 그리고 열거형으로 나타낼 수 있다.

4. 추상화란 무엇인가?
answer : 추상화란 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다. 좋은 추상화는 사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거되는 것이다. 이를 위해 information hiding 이 개발되었고 추상 자료형인 ADT 의 개념으로 발전하였다.

5. 알고리즘의 성능 분석 방법에는 어떤 것들이 있는가?
answer : 알고리즘을 평가하는 두 가지 요소는 시간 복잡도와 공간 복잡도이다. 즉 얼마나 빠르고 얼마나 메모리를 적게 사용하는가 이다.

6. 시간 측정 방법에는 어떤 방법이 있는가?
answer : 수행시간을 측정하는 방법에는 대표적으로 두가지 방법이 있는데 p.22

7. 알고리즘의 성능을 표현하는 방법에는 어떤 것들이 있는가?
answer : 알고리즘의 성능을 표현하는 방법은 시간 복잡도 함수를 통해 나타내는 빅오 표기법을 예로 들 수 있다. 시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시하는 것이다. 입력의 개수 n 과 시간 복잡도 함수 T(n) 을 통해 두개의 함수 f(n) 과 g(n) 이 주어졌을 때 모든 n>n0 에 대하여 |f(n)|<=c|g(n)| 을 만족하는 2개의 상수 c 와 n0 가 존재하면 f(n) = O(g(n)) 의 정의를 통해 빅오 표시법으로 알고리즘의 성능을 표현할 수 있다.

8. 재귀(혹은 순환; Recursion) 기법의 장점과 단점은 무엇인가?
answer : 재귀함수는 반복문보다 상대적으로 간결하게 코드를 작성할 수 있다. 하지만 재귀함수를 사용하면 지속적으로 함수를 호출하게 되는데, 이 때 사용하는 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치등을 지속적으로 프로세스의 Stack에 저장해야 합니다. 이는 선언한 변수의 값만 변경해서 사용하는 반복문과 달리 많은 메모리 사용을 의미합니다. 또한 함수 호출과 복귀를 하기 위한 context switching 비용이 발생하기 때문에, 속도가 상대적으로 느립니다. 즉, 오버헤드가 발생하여 속도가 느리게 됩니다.

9. 또는 재귀 함수를 단순 반복구조로 변형하는 문제


10. 배열을 이용한 리스트, 스택, 큐의 장점과 단점은 무엇인가?
answer
리스트 : 내부 구조가 배열로 이루어져 있기 때문에 인덱스로 바로 접근이 가능하여 검색 속도가 빠르고 구현이 쉽다. 하지만 배열 리스트를 할당할 때 대략적인 자료의 양을 예측하여 할당하기 때문에 메모리 낭비가 존재하고 할당된 용량보다 데이터가 많을 시 더 큰 배열을 생성하고 데이터를 복사해야 해서 효율성이 떨어진다. 또한 연속적으로 데이터가 들어있어야 하는 특성 때문에 데이터를 추가, 삭제 시 빈 공간이 생기지 않도록 밀어주고 땡겨주는 작업이 필요하다.

스택 : 구현이 쉽고 원하는 데이터의 접근속도가 빠르며 내가 원하는 데이터를 인덱스로 바로 접근이 가능하다. 하지만 데이터의 최대 개수를 미리 정해야 하고 또한 데이터의 삽입과 삭제에 있어 매우 비효율적이다.

큐 : 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에서는 매우 유리하지만 크기가 제한적이고 큐의 앞 부분이 비어도 데이터를 삽입할 수 없을 뿐만 아니라 rear 가 맨 뒤에 있을 경우 큐가 empty 여도 empty 라고 판단하지 않는 오류를 내보낼 수 있다.

11. 환형큐(Circular Queue)를 고정 배열보다 동적 배열 혹은 동적 메모리 할당을 이용하는 것이 좋다는 이유는 무엇인가?
answer = 환형큐에서 동적 메모리 할당을 이용하면 초기에 메모리 공간을 정해두지 않고 필요할 때마다 할당하므로 데이터 삽입, 삭제하는 경우 O(1) 에 가능하고 최대 메모리 공간 내에서 리스트 크기 제한이 없기 때문에 메모리 할당을 사용하는 것이 좋다. 하지만 스택과는 달리 새로 배열의 크기를 늘려주면서 이미 원형 큐에 들어가있는 데이터들을 정리해주서야 한다.

12. 환형큐(원형큐)와 환형리스트(원형 리스트)의 차이는 무엇인가? 자료구조와 연산의 관점에서 차이점을 설명하시오. (상당히 어려움)
answer : 원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 즉 마지막 노드의 링크 필드가 NULL 이 아니라 첫 번째 노드 주소가 되는 리스트이다. 원형 연결 리스트에서는 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 하나의 노드에서 링크를 계속 따라 가면 결국 모든 노드를 거쳐서 자기 자신으로 되돌아 올 수 있는 것이다.
일반적인 배열을 사용하는 원형큐와 달리 연결리스트를 사용하면 배열을 이용한 리스트에서 가장 문제가 되었던 중간에 삽입하는 문제를 해결할 수 있다. 연결 리스트에서는 앞뒤에 있는 데이터들을 이동할 필요가 없이 줄만 변경시켜주면 된다. 삭제 시에도 마찬가지로 데이터들을 연결하는 줄만 수정하면 된다.
또한 원형큐와 달리 원형리스트를 구별하는 것은 첫 번째 데이터이다. 첫 번째 데이터만 알 수 있으면 연결 리스트의 나머지 데이터들은 포인터만 따라가면 얻을 수 있다. 연결 리스트의 또 하나의 장점은 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다는 것이다. 이것은 순차적인 표현 방법인 배열에 비하여 상당한 장점이 된다.