소프트웨어 개발 - 2 자료구조

🔸 자료 구조  : 논리적으로 설계된 데이터구조 , 관계

어떻게 구성하는지에 따라 성능에 많은 영향을 끼친다
데이터 용량과 실행시간을 최소한으로 사용
데이터의 추가 삭제 탐색을 효율적으로 연산하게 설계 한다

🔹 단순구조

• 기본 데이터 타입을 사용하는 구조
• 단순구조를 확장하여 자료구조가 구성된다

🔹 선형구조 : 대응관계가 1:1로 구성되는 구조  , 순차구조와 연결구조로 구분

• 배열
• 선형리스트
  • 연속 리스트 : 배열처럼 연속되는 기억장소에 저장  , 중간에 삽입 ,삭제시 자료의 이동이 필요하다  ,  탐색속도 우선
  • 연결리스트  : 연속적으로 배열시키지는 않고 임의의 공간에 기억, 순서에 따라 연결시킨 구조
                            데이터  이동 (삽입 , 삭제) 속도 우선   , 연속적이지 않아도 저장할 수 있다
• 스택 LIFO
• 큐  FIFO   
• 데크 
• 연결 리스트

스택 

1. 데이터의 입출력이 반대쪽에서 일어나는 구조 LIFO  
2. 삽입 - PUSH , 추출 POP  
3.  오버플로 언더플로 발생

큐

1. 데이터의 입출력이 각각 반대쪽에 일어나는 구조 FIFO
2. 삽입 Rear , 삭제 Front 
3. 대기 행렬에 적합한 자료구조 

데크

1. 입출력이 양쪽 모두에서 일어나는 구조  (양방향 큐)
2. 각각 포인터가( Left , Right) 데이터 삽입 , 삭제에 따라 1씩 증감
3. 입력제한 (Scroll) - 출력은 양쪽에서 , 입력한 한쪽에서만 가능
4. 출력제한 (Shelf) - 입력은 양쪽에서 , 출력은 한쪽에서만 가능 

선형 리스트

1. 같은 유형 데이터가 연속된 공간에 저장
2. 가장단순 , 접근속도가 빠르다
3. 삽입 삭제시 위치 이동 때문에 시간이 오래걸린다
4. 대표적인 배열이 있다

연결 리스트

1. 데이터의 삽입 , 삭제가 어려운 배열의 단점을 보완
2. 노드 : 데이터와 자신이 연결된 데이터 포인터
3. 다른 위치의 노드와 노드의 연결로 구성
4. 기억공간이 추가로 필요 , 배열보다 느리다

🔹 비선형구조 :  1 : M   ,  M : N  등으로 구성

• 트리
• 그래프 
  • 무방향 그래프
  • 방향 그래프
  
  

---

 

🔹 수식 prefix infix postfix

a * ( b + c ) * d

1. 중위식 -> 전위식

1. ( ( a * ( b + c ) ) * d )
2. ( * ( * a (+ bc ) ) d )
3. 괄호제거  ** a * bc d   

2. 중위식 -> 후위식

1. ( ( a * ( b + c ) ) * d )
2. ( ( a ( b c + ) * ) d * )
3. 괄호제거 a b c + *d*

3. 전위식 ( - / * a + b c d e ) 를 후위식으로 변경

1. 연산자 , 피연산자 , 피연산자 형태로 묶는다 + 피연산자 형태도 묶으면 피연산자됨
2.  - / * a (+ b c ) d e 
3. - / (* a ( + b c ) ) d  e
4.  - ( / ( * a ( + b c ) ) d ) e
5. ( - ( / ( * a ( + b c ) ) d ) e )
6. 기호들을 괄호 안에서 가장 뒤로 
7. ( ( ( a ( b c + ) * ) d / ) e -)
8. 괄호 제거  a b c + * d / e -

 

🔸 알고리즘 :  문제를 해결하기 위한 효율적인 해법
알고리즘 과 데이터 구조가 결합하면 프로그램이 완성된다

🔹 원칙 

• 입력은 없을 수 있지만 출력은 반드시 1개 이상 존재 
• 모든 기능은 명확한 의미를 가지며 완벽히 구성 되어 있어야 한다
• 모든 기능은 지정된 횟수만큼 반복되어야 하며 , 실제 연산이 가능해야 한다

성능 판단기준 : 정확성 , 명확성 , 수행량 , 메모리 사용량

🔹 알고리즘 표현 

• 순서도 : 도형과 기호로 표현
• 의사코드 : 일반적인 언어로 코드와 유사하게 표현
• 이해할수 있게 일관성 

🔹 설계기법 

동탐재근분퇴
DGRADB

1. 동적 계획법 (Dynamic) - 플로이드 , 피보나치 
더 작은 문제의 연장선으로 생각하는 방식 - 쉬운단계 문제부터

피보나치

2. 탐욕적 알고리즘 (Greedy)
분기마다 가장 최적의 풀이를 선택 ,  반드시 최적의 풀이를 보장하지 않는다

3.  재귀적 알고리즘 (Recursive)
같은 풀이를 다시 불러오는 과정을 반복

4. 근사 알고리즘 (Approximation)  (근사치 값이라 생각하자)
비교적 빠른시간에 계산이 가능하도록

5. 분할 정복 (Divide) - 퀵정렬 , 병합 정렬
풀수있는 단위로 작게 나누는 방식

6. 퇴각 검색법(BackTacking)
탐색이 실패할 경우 탐색이 성공했던 이전분기로 되돌아가는 방식
새로운 탐색이 가능한 분기까지 되돌려 진행된다
대표 : 깊이우선 탐색 알고리즘 DFS 

 

---

🔸 시간 복잡도에 따른 알고리즘

• 문제를 해결하기 위한 시간의 횟수를 말한다
• 최적화를 위해 필요
• 자료의 수 n 이 증가할 때 시간이 증가하는 대략적인 패턴을 의미

🔹 시간복잡도 Big-O 표기법

O(1)	입력값(n)에 관계 없이 일정하게 문제 해결에 단 하나의 단계만을 거친다 (해시함수)
O(log2n)	로그시간 복잡도  입력값(n) 또는 조건에 의해 감소 (이진탐색) /
O(nlog2n)	선형로그 시간복잡도  입력값 n(log2n)번만큼 수행시간을 갖는다 - 증가 (퀵정렬 , 병합 정렬)
O(n)	선형시간 복잡도 입력값(n)이  1:1의 관계를 가짐(순차 탐색)
O(n^2)	제곱시간 복잡도 입력값(n)의 제곱만큼 수행(삽입, 선택,버블)
O(C^2)	주어진 상수값C의 n제곱

---

🔸 순환 복잡도

• 프로그램 이해 난이도는 , 제어 흐름 난이도의 복잡도에 따라 결정
• 싸이클로메틱의 개수와 , 원시프로그램의 오류 개수는 밀접한 관계

🔹 복잡도 계산방식

복잡도 = 화살표 수 - 노드 수 + 2

복잡도 = 영역수 (폐 구간) + 1

복잡도 = 의사결정 수 + 조건수 + 1 

순환 복잡도 : 화살표 수 6 - 노드 수4 + 2 = 4 
E - N + 2

---

🔸 해싱 함수

🔹 해싱

• 직접 접근 파일을 구성 할 때 사용
• 속도는 가장 빠름 , 충돌 현상시 오버플로 해결의 부담이 가중된다  , 많은 기억공간을 요구

🔹 제산방법 Division Method 

• 나머지 연산자 % 를 사용해 테이블 주소를 계산

🔹 중간 제곱방법 Mid-Squre

• 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 몇비트를 선택해 테이블 홈 주소로 사용

🔹 중첩 방법 Folding 폴딩

• 해싱함수 중 레코드 키를 여러부분으로 나누고 나눈부분의 각 숫자를 더하거나 XOR 한 값을 홈 주소로 사용

🔹 기수 변환방법 Radix Conversion

• 모든 키 내에서 자리별로 어떤 분포인지를 조사해 고른분포를 나타내는 자릿수를 필요한 만큼 선택해 홈주소로 사용 

 

---

🔹 퀵정렬

• 피벗
• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으러 나누어 가며 정렬
• 최적 O(nlog^n)
• 평균 O(nlog^n)
• 최악 O(n^)

🔹 합병정렬

• 전체 원소를 하나의 단위로 분할후 분할한 원소를 다시 합병해서 정렬
• 최적  O(nlog^n)
• 평균 O(nlog^n)
• 최악  O(nlog^n)

🔹 힙정렬

• 가장 큰 키 값을 갖는 루트노드를 제거하는 방식으로 반복해 정렬
• 최적  O(nlog^n)
• 평균 O(nlog^n)
• 최악  O(nlog^n)

🔹 버블정렬

• 2개의 레코드 키값을 비교해 그 크기에 따라 레코드 위치를 교환하는 알고리즘
• Pass = 요소개수 -1 번 수행된다