240830
- 자료구조와 알고리즘
- 학습목표 자료구조의 정의와 분류에 대하여 설명하고, 선형/비선형구조를 활용할 수 있다. 알고리즘의 역할을 이해하고 상황에 따라 적합한 알고리즘을 선택할 수 있다.
- 핵심 키워드 배열, 리스트, 스택, 큐, 데크, 트리, 그래프
알고리즘의 정의, 알고리즘 성능분석, 정렬/탐색 알고리즘
- 자료구조
- 정의 자료구조란 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로
다양한 자료를 효율적으로 표현하고 활용할 수 있도록
자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것
- 분류 자료구조는 크게 선형구조와 비선형구조로 나눌 수 있다.
선형구조는 자료가 일렬로 연결되어 있는 형태로 구성하는 방법이고
비선형구조는 자료의 구성이 계층구조나 망구조의 특별한 형태를 띠는 구조- 자료구조의 분류(표)
물리적 설계 정보저장소에 저장분류 설명 선형구조 원시코드로부터 정보를 추출하여
물리적 설계자료들이 직선 형태로 나열되어
자료들 간의 순서를 고려한 구조로
전후/인접/선후 자료들간의 1:1 관계로 나열됨 |
| 비선형구조 | 한 자료 뒤에 여러 개의 자료들이 존재하는 구조로
인접/전후 자료들 간의 1:다 또는 다:다 관계로 배치됨
종류로는 트리와 그래프 등이 있음 | - 자료구조의 분류(그림)
선형구조 배열 리스트 선형리스트 / 연결리스트 스택 큐 비선형구조 트리 그래프 - 순차자료구조와 연결자료구조의 비교
빈자리가 없기 때문에구분 순차자료구조 연결자료구조 메모리 저장 방식 메모리저장 시작위치부터 빈자리 없이 자료를 순서대로 연속적으로 저장하는 방식 메모리에 저장된 물리적 위치나 순서에 상관없이 링크에 의해 논리적인 순서를 표현하는 방식 논리 / 물리 순서 일치 여부 논리적인 순서와 물리적인 순서가 일치하는 방식 논리적 순서와 물리적 순서가 일치하지 않음 연산특징 삽입*삭제 연산을 해도
자료가 순서대로 연속하여 저장 | 삽입*삭제 연산으로 논리적인 순서가 변경되어도
링크정보만 변경되어
물리적 순서는 변경되지 않음 |
| 프로그램 기법 | 배열을 이용한 구현 | 포인터를 이용한 구현 |
- 자료구조의 분류(표)
- 스택과 큐
- 스택 스택은 선형리스트의 하나로
데이터가 입력된 순서로 기억공간에 저장되어
출력 시 가장 나중에 쌓인 데이터가
가장 먼저 출력을 하게 되는 자료구조
즉, 스택에 저장된 원소는
top으로 정한 곳에서만 접근이 가능하여
top 위치에서만 원소를 삽입하고 마지막에 삽입한 원소는
맨 위에 쌓여 있다가
가장 먼저 출력되게 된다.- 스택의 연산의 종류
top()스택의 맨 위에 있는 데이터 값을 반환push()스택에 데이터를 삽입pop()스택에서 데이터를 삭제하여 반환isempty()스택에 원소가 없으면 true 값을 반환하고 있으면 false 값을 반환isfull()스택에 원소가 없으면 false 값을 반환하고 있으면 true 값을 반환
- 스택의 연산의 종류
- 큐 스택과 유사하게 삽입과 삭제의 위치가 제한되어 있지만
스택과 달리 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료구조
큐는 뒤에서만 삽입되고
앞에서는 삭제만 할 수 있는 구조로
삽입된 순서대로 원소가 나열되어
가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제됨
- 스택 스택은 선형리스트의 하나로
- 정의 자료구조란 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로
- 학습목표 자료구조의 정의와 분류에 대하여 설명하고, 선형/비선형구조를 활용할 수 있다. 알고리즘의 역할을 이해하고 상황에 따라 적합한 알고리즘을 선택할 수 있다.
개발자