리스트 리스트의 항목들은 순서 또는 위치를 가진다. cf) 집합 : 각 항목 간에 순서의 개념 x ADT 객체 : n개의 element형으로 구성된 순서 있는 모임 연산: insert(list, pos, item) ::= pos 위치에 요소를 추가 insert_last(list, item) ::= 맨 끝에 요소를 추가 insert_first(list item) ::= 맨 처음에 요소를 추가 delete(list, pos) ::= pos 위치의 요소를 제거 clear(list) ::= 리스트의 모든 요소 제거 get_entry(list, pos) ::= pos 위치의 요소를 반환 get_length(list) ::= 리스트의 길이를 구한다. is_empty(list) ::= 리스트가 비었는지 검사 is_f..

큐 FIFO(First In First Out) : 먼저 들어온 데이터가 먼저 나가는 자료구조 동작 삽입(enqueue) : 큐의 후단(rear) 삭제(dequeue) : 큐의 전단(front) ADT 객체 : 0 개 이상의 요소들로 구성된 선형 리스트 연산 create(max_size) ::= 최대 크기가 max_size인 공백큐로 생성한다. init() ::= 큐를 초기화한다. is_empty() ::= 큐가 비어있는지 검사한다. is_full() ::= 큐가 가득 찼는가를 검사한다. enqueue(e) ::= 큐의 뒤에 요소를 추가한다 dequeue() ::= 큐의 앞에 있는 요소를 반환한 다음 삭제한다. peek() ::= 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다. 큐의 활용 은행에서의 대..

스택 특징 Last in First Out(LIFO) → 가장 최근에 들어온 데이터가 가장 먼저 나감 입력의 역순 출력이 필요한 이유 에디터에서 되돌리기 기능 함수호출에서 복귀주소 기능 ADT 객체 : 0개 이상의 원소를 가지는 유한 리스트 연산 : create(size) ::= 최대 크기가 size인 빈 스택을 생성 is_empty(s) ::= 스택 s가 비어있는지를 검사 is_full(s) ::= 스택 s가 가득 찼는가를 검사 push(s, x) ::= 스택 s의 맨 위에 요소 x를 추가 pop(s) ::= 스택 s의 맨 위에 있는 요소를 삭제 peek(s) ::= 스택 s의 맨 위에 있는 요소를 삭제하지 않고 반환 구현 배열을 이용한 스택 1차원 배열 stack [MAX_STACK_SIZE] 사용 ..

배열 쌍의 집합 각 항목의 값은 인덱스 번호로 위치가 계산되어 참조 직접 접근 방식, 접근 시간 복잡도 : O(1) ADT 객체 : 쌍의 집합 연산 create(size) ::= size개의 요소를 저장할 수 있는 배열 생성 get(A, i) ::= 배열 A의 i번째 요소 반혼 set(A, i, v) ::= 배열 A의 i번째 위치에 값 v 저장 1차원 배열의 주소 가장 첫 번째 인덱스 base 인덱스를 n이라고 했을 때 arr [n] = base + nsizeof(자료형) ex) int A [6] A [0] : base A [2] : base + 2*sizeof(int) 2차원 배열의 주소 현재 사용하는 것은 행우선 배열(row-major order array) Call ..

순환 더보기 개념 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 정의 자체가 순환적으로 되어 있는 경우 적합 프로그램에서 되풀이 해결방법 순환(recursion) 순환적인 문제에서는 자연스러움 함수 호출에 오버헤드 발생 가능성 반복(iteration) 수행속도가 빠름 순환적인 문제에 관해서는 프로그램 작성이 어려워질 수도 있음 팩토리얼 순환(Recursive) 구현 int factorial_recur(int x) { if(x == 1) return 1; // 순환 비호출 부분 return x*factorial_recur(x-1); // 순환 호출 부분 } 반복(Iter) 방식 구현 int factorial_iter(int x){ if(x == 1) return 1; in..

성능 분석 기법 수행 시간 측정 - 두 개의 알고리즘의 실제 수행 시간을 측정하고 비교 가정 : 동일한 하드웨어 사용 복잡도 분석 공간 복잡도 : 수행 시 필요로 하는 메모리 공간 분석 시간 복잡도 분석 : 직접 구현하지 않고 수행 시간 분석 ← 수행하는 연산의 횟수를 측정하여 비교 수행시간 측정 - clock 함수 #include #include #include int main(){ clock_t start,end; double duration = 0; start = clock(); // clock() 현재 시간을 반환 // 코드 실행 // ... // 코드 종료 end = clock(); duration = (double)(end-start)/CLOCKS_PER_SEC; // 초 단위 환산 print..

자료구조와 알고리즘 자료구조 : 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조 알고리즘 : 컴퓨터에서 문제를 해결하기 위한 절차적 단계 프로그램 = 자료구조 + 알고리즘 알고리즘의 조건 입력(Input) : 0개 이상의 입력이 존재해야 한다. 출력(Output) : 1개 이상의 출력이 존재해야 한다. 명백성(Definiteness) : 각 명령어의 의미는 모호하지 않고 명확해야 한다. 유한성(Finiteness) : 한정된 수의 단계 후에는 반드시 종료되어야 한다. 유효성(Effectiveness) : 각 명령어들은 실행 가능한 연산이어야 한다. 알고리즘 기술 방법 자연어 장점 : 읽기 쉽다. 단점 : 의미 전달이 모호하다. 흐름도(flow chart) 장점 : 직관적이고 이해하기 쉽다 단점 : 알고..