고려대,성균관대,서강대,건국대 컴퓨터공학과 편입면접 대비 자료

소개글

제가 대학 고려대포함 거의 대다수의 편입학 면접이 존재하는 학교의 컴퓨터학과 대비용으로 제작한 면접 준비용 자료입니다.

제작만 거의 2주가량 매일 입력하고 제가 공부하고 요약하고 했습니다.

면접 보실때 절때 후회 안하실 겁니다.

목차

없음

본문내용

1. 연결 리스트?
메모리의 동적 할당으로 구현된 리스트를 말한다. 배열과 비교했을 때 크기 조절이 자유롭고 요소를 추가하거나 삭제할 때 발생하는 오버헤드가 없다. 하지만 노드 내 변수들로 인해 배열보다 크기가 크고, 메모리 상에서 물리적으로 인접해있지 않아 속도가 느리고 캐싱에도 유리하지 않다. 또한 한번의 연산으로 임의의 항목으로 접근할 수 있는 배열과는 달리 순차적으로 접근해야 하므로 O(n)으로써 속도가 느리다.

2. 스택?
LIFO 속성을 만족하는 자료 구조이다. 배열과 비교했을 때 임의의 항목으로 접근이 불가능하지만 요소의 삽입과 삭제가 상수 시간 내 이루어지기 때문에 사용례에 따라 스택을 사용하는 것이 더 효율적일 수 있다. Depth first search, 수식의 괄호 검사, 후위 표기법 계산 등에 사용할 수 있다. 구현은 배열과 연결 리스트로 가능하다.

3. 큐?
FIFO 속성을 만족하는 자료 구조이다. 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있을 때 사용하며 Breadth first search, 대기열 구현 등에서 사용할 수 있다. 구현은 배열과 연결 리스트로 가능하며 요소를 삭제하고 삽입하는 과정에서 낭비되는 공간을 없애기 위해 원형 큐로써 변형을 가해 사용하기도 한다.

※ 두 개의 스택으로 큐를 구현하기 : 스택은 LIFO 속성을 만족하므로 첫 번째의 스택에 있는 모든 요소를 두 번째의 스택으로 옮기면 두 번째 스택은 FIFO를 만족한다.
※ Depth first search : 임의의 노드(트리는 루트 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색
※ Breadth first search : 임의의 노드(트리는 루트 노드)에서 시작하여 인접한 노드를 먼저 탐색

3-1. 원형 큐?
포인터가 맨 끝을 가리키고 있는 상태에서 증가시켰을 때 처음으로 되돌아가도록 변형하여 낭비되는 공간이 없도록 큐에서 변형된 자료구조이다.

참고 자료

없음