자료구조

요구사항 → 분석 → 설계 → 정제와 코딩 → 검증요구사항프로젝트의 목적을 정의한 명세들의 집합입력과 출력에 관한 정보 기술분석문제들을 다룰 수 있는 작은 단위들로 나눔상향식 bottom up / 하향식 top down설계추상 데이터 타입 생성알고리즘 명세와 설계 기법

Array 배열int \[] arr = new int \[10];선언할 때 크기와 데이터 타입 지정. 즉, 공간에 할당할 사이즈 미리 정해놓고 사용장점 : 검색 편리 → 랜덤 액세스. 임의접근 가능 → O(1)단점 : 데이터가 늘어날때나 최대사이즈를 알 수 없을때 사

스택 추상 데이터 타입top이라고하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트LIFO(Last In First Out) = 후입선출연산 : push, pop, peek시스템 스택프로그램 실행 시 함수 호출을 처리함수 호출 시 activa

연결리스트 : 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조노드 : 데이터 필드 + 다음 노드에 대한 참조원소의 수가 가변적이다삽입 / 삭제 용이 → O(1)랜덤 액세스 불가능하다. 순차접근 → O(n)포인터를 위한 여분의 메모리 공간이 필요하다sequenti

원소들 간에 1:N 관계를 가지는 비선형 자료구조원소들 간에 계층관계를 가지는 계층형 자료구조상위원소에서 하위원소로 내려가며 확장되는 트리(나무) 모양의 구조트리는 노드와 간선으로 구성트리에 사이클 존재 불가노드 : 트리의 원소 → A,B,…,L 전체 다루트 노드 :

그래프 : 선형 자료구조나 트리 자료구조로 표현하기 어려운 다:다의 관계를 가지는 원소들을 표현하기 위한 자료구조그래프 G는 객체를 나타내는 정점과 객체를 연결하는 간선의 집합 → G = (V, E)차수 : 정점에 연결된 간선의 수그래프의 제한 사항자기 간선 또는 자기

탐색리스트 : 하나 이상의 필드로 된 레코드의 집합키 : 레코드를 구분하기 위해서 사용되는 필드순차탐색 : 레코드 리스트를 왼→오 또는 오→왼으로 레코드를 검사하는 것 → O(n)이원탐색 : O(logn)보간법에 의한 탐색 : 리스트가 정렬되었을 때만 사용 가능.리스트

산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식키 값에 대해서 해싱함수를 계산하여 주소를 구하고구한 주소에 해당하는 해시 테이블로 바로 이동 → 해당 주소에 찾는 항목 있으면 검색성공, 없으면 실패O(1)안에 변환하는게 목표해싱 함수