자료구조_ 자료구조 & 알고리즘

 

 

[1] 자료구조 

---

(1) 자료구조의 정의

• 자료를 효율적으로 사용할수 있또록 특성에 따라 분류, 정렬, 저장, 처리하는 표현 방법 

 

(2) 자료 구조의 구성

1. 선형구조

• 데이터 항목 관계 1:1 
• 선후 관계가 명확한 선 형태를 가지는 리스트 구조 
• 종류 : 배열 Arrays, 리스트 List , 스택 Stack , 큐 Queue , 데크 deQueue

2. 비선형구조 

• 데이터 항목 관계 1 : n 또는 n : m 
• 직선형태가 아닌 구조 
• 종류 : 트리 , 그래프 

(3) 자료구조 선택시 고려사항 

• 데이터의 양
• 데이터의 특성
• 데이터의 활용빈도
• 사용 시스템의 프로그램 난이도
• 데이터의 저장방식 및 기억용량
• 최선, 최악, 평균의 처리시간
• 데이터 저장방식

 

[2] 알고리즘

---

(1) 알고리즘 정의

• 문제를 해결하기 위해 컴퓨터로 구체적인 방법과 논리적 절차를 해결하는 것
• 논리적 절차를 수행하기 위한 명령어들의 집합
• 프로그램 = 자료구조 + 알고리즘 

※ 최대값 찾기 프로그램의 경우 자료구조 (배열) + 알고리즘(순차검색)을 사용한다 

(2) 알고리즘의 조건 

• 입력하는 데이터가 있어야하고 그 입력에 대해 최소 1개의 출력이 나와야한다 
• 명령어의 집합은 의미가 정확하고 명확해야한다 
• 논리적 절차대로 수행하면 반드시 종료되야한다 
• 논리적 절차는 반드시 실행가능해야하고 유효한 결과가 산출되어야한다 

 

 

[3] 알고리즘 기법

---

(1) 동적 계획법 알고리즘

• 복잡한 문제를 간단한 여러개의 문제로 나누어 산출된 결과값을 이용하여 해결해간다 
• 최단 경로문제 , 행렬의 제곱문제, 배낭 문제에 사용

 

(2) 탐욕적 알고리즘

• 최적해를 구하는데 사용되는 근사적인 방법
• 여러 경우 중 하나를 결정해야할때마다 그 순간에 최적인 것을 선택해 해결해간다 

 

(3) 재귀 알고리즘

• 하나의 함수에서 자신을 다시 호출하여 작업을 수행하여 문제를 해결한다 
• 프로그램 코드 작성이 단순해지나 기억 공간의 낭비가 우려된다 
• 반복문보다 프로그램 이해와 구조 단순화를 위해 사용한다 
• 퀵 알고리즘은 반복문보다 재귀적 호출을 사용하는것이 이해와 단순화에 용이하다 

 

(4) 근사 알고리즘 

• 문제에 대해 해의 근삿값을 구하는 알고리즘
• 비교적 바른 시간에 계산할수 있고 어느정도 보장된 근사해를 계산할수 있음
• NP-완전 문제 , 최적화 알고리즘이 없는 문제에 주로 사용한다 

 

(5) 배낭 알고리즘

• 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 
• 분할 가능 배낭 문제 : 그리다 알고리즘으로 해결
• 0-1 배낭 문제 : 동적 계획법으로 해결 

 

(6)NP문제

• P 문제 : 각 단계에서 1가지의 가능성만 고려할수 있는 다항식 시간 이내에 해결할수 있는 문제 
• NP 문제 : 각 단계에서 여러가지 가능성을 고려하는 비결정적 알고리즘으로 다항식 안내에 해결할수 있는 문제 

 

 

[4] 복잡도

---

(1) 공간 복잡도

• 공간복잡도 = 프로그램의 필수적으로 필요한 고정공간 + 프로그램 실행과정에서 필요한 가변공간
• 프로그램을 실행하여 오나료하는데 필요한 총 저장 공간
• 어떤 문제를 해결하기 위한 알고리즘의 필요한 메모리 사용량 (메모리 MB 단위 기준)
• 공간복잡도와 시간복잡도는 반비례하여 메모리는 사용하더라도 시간복잡도를 줄이는 방법으로 알고리즘을 선택해야한다

 

(2) 시간복잡도 

• 시간복잡도 = 컴파일하는데 걸리는 컴파일 시간 + 명령문을 실행하는데 걸리는 실행시간
• 프로그램을 실행하여 완료하는데 소요되는 총 시간
• 빅오메가 표기법 , 빅 세타 표기법 , 빅오 표기법 
• Big-O 표기법 : 실행빈도수를 이용하여 실행 시간 함수 찾기

연산시간↓						연산시간↑
O(logN)	O(N)	O(N logN)	O(N⌒2)	O(N⌒3)	O(2⌒N)	O(N⌒!)

 

Bio O 표기법	설명	내용	시간복잡도 빠른순
O(1)	상수시간	입력자료의 수에 관계없이 일정한 실행시간을 갖음 한번 연산하는 것  저장된 값 그대로 한번에 반환	1
O(log N)	로그시간	입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가 입력값에 대해서 log n번 만큼만 연산한다  log 수만큼 반복하고 반환	2
O(N)	선형시간	입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 - 입력자료마다 일정 시간 할당 n번 반복하고 n번 반환	3
O(N log N)	로그 선형시간	큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우 n 번 반복 +  log n 만큼 반복하고 반환	4
O(N⌒2)	이차시간	중첩 반복문 내에서 입력 자료를 처리할 때	5
O(N⌒3)	삼차시간	3차 중첩 반복문 내에서 입력자료 처리할 때	6
O(2⌒N)	지수시간		7
O(n!)			8

 

 

시간복잡도는 상수는 제외한다 

연산이 O(2n)이라면 O(N)으로 본다 

연산을 1번 하는것과 2번 하는것은 크게 차이가 없다 

O(N⌒2)은 연산한 값을 다시 연산하는것이기 때문에 차이가 크다 

 

 

 

 

[5] 추상 데이터와 순환

---

(1) 데이터와 데이터 타입

• 데이터 : 프로그램에서 처리할 대상의 값
• 데이터 타입 : 정수형, 실수형, 문자형 등 , 데이터 집합과 데이터에 적용할수 있는 연산의 집합 (int, char,float,double,array,struct)

 

(2) 추상 데이터 타입 ADT

• 추상데이터 : 데이터 타입을 추상적으로 정의한 것
• 추상화 : 데이터, 연산이 무엇인가 논리적으로 정의
• 구체화 : 어떻게 구현할것인지 정의 

 

(3) 추상화와 구체화와의 관계

	데이터	연산
추상화	추상 데이터 타입 ADT	알고리즘
구체화	데이터 타입	프로그램

 

 

(4) 순환 함수

• 실행중인 함수가 자기자신을 다시 호출하는 형태 
• 순환함수는 반복문으로 대체 가능하다. 반복문을 사용시 제어 흐름, 실행과정 인식이 쉽고 복잡도가 감소할수 있다 
• (코드는 길어지지만 풀어서 작성하여 추후 코드 분석시 이해가 쉽다 , 오히려 다른 함수를 이용할경우 시간복잡도가 증가하는경우가 있더라)