1)자료 구조의 개념
1.자료 구조 정의
– 프로그램에서 쉽게 활용될 수 있도록 놀리적으로 설계된 데이터 구조 및 관계
2.자료 구조 특징
– 같은 데이터라도 데이터 구조를 어떻게 구성하는지에 따라 성능에 많은 영향을 미친다.
2) 자료 구조의 유형
1. 단순 구조
– 프로그래밍 언어에서 제공하는 기본 데이터 타입을 사용하는 구조
2. 선형 구조
– 데이터들의 대응 관계가 1:1로 구성되는 구조
– 선형 구조의 유형은 크게 순차 구조와 연결 구조로 구분된다.
– 순차(Sequential): 데이터 탐색 속도 우선
– 연결(Linked): 데이터 이동(삽입, 삭제 등) 속도 우선
– 스택, 큐, 데크, 선형 리스트, 연결 리스트 등
3. 비선형 구조
– 대응 관계가 1:N, N:M 등으로 구성되는 구조
– 트리와 그래프
4. 파일 구조
– 보조기억 장치에 실제 데이터가 기록될때 활용되는 자료 구조
– 종류는 순차 파일, 직접 파일, 색인 순차 파일 등
3) 알고리즘(Algorithm)
1. 알고리즘 정의
– 문제를 해결하기 위해 수행해야 할 기능들의 효율적인 해법
2. 알고리즘 원칙
– 입력을 없을 수 있지만 출력은 반드시 1개 이상 존재한다.
– 모든 기능은 명확한 의미를 가지며 완벽히 구성되어 있어야 한다.
3. 알고리즘 성능 판단 기준
– 정확성, 명확성, 수행량, 메모리 사용량 등의 기준을 통해 알고리즘의 최적성을 판단
– 정확성: 올바른 입력에 대해 기대 출력값이 동일한지 판단
– 명확성: 알고리즘이 이해와 변경이 용이한지 판단
– 수행량: 단위 시간 대비 주요 연산의 수행 횟수
– 메모리 사용량: 문제 해결에 사용된 메모리 공간
4. 알고리즘의 표현
– 순서도와 의사코드
– 일관성 있는 표현 양식 사용
– 순서도(Flow Chart): 약속된 도형과 기호로 표현
– 의사코드(Pseudo Code): 일반적인 언어로 코드와 유사하게 표현
4) 알고리즘 설계 기법
1. 동적 계획법(Dynamic Programming)
– 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하는 방식(Bottom-up)
– 작은 문제의 풀이를 활용하여 큰 문제의 해를 찾는다.
2. 탐욕적 알고리즘(Greedy Algorithm)
– 분기마다 가장 최적의 해를 선택하여 결과를 도출하는 방식
– 반드시 종합적인 최적 해를 보장하지는 않는다.
3. 재귀적 알고리즘(Recursive Algorithm)
– 풀이 도중 같은 풀이를 다시 불러오는 과정을 반족하는 방식
– 호출의 역순으로 결과가 출력
4. 근사 알고리즘(Approximation Algorithm)
– 최적화되는 답을 구할 수는 없어도 비교적 빠른 시간에 계산이 가능하다록 근사 해법을 수행하는 알고리즘
5. 분할 정복법(Divide and Conquer)
– 크고 방대한 문제를 효율적으로 풀 수 있는 단위로 작게 누나느(Top-down)방식
– 계산된 결과를 다시 합쳐서 큰 문제의 결과를 구한다.
6. 퇴각 검색법(Backtracking)
– 분기구조 탐색에서 탐색에 실패하는 경우, 탐색이 성공했던 이전 분기로 되돌아가는 방식
– 새로운 탐색이 가능한 분기까지 과정을 되돌려 진행하는 알고리즘
– 대표적으로 깊이 우선 탐색 알고리즘(DFS)이 있다.