자료구조와 알고리즘 학습 노트 기초 (1) 자료구조와 알고리즘

자료구조

데이터를 저장, 조직, 관리하는 방법

책들이 난잡하게 어질러져있음 -> 책을 카테고리에 맞게 분류

 

자료구조의 일상 생활과 프로그래밍 문제 해결과의 차이

건축물을 만들려면 : 건축 재료(철근, 시멘트, 벽돌)의 이해가 필요. 샤시, 철골, 인터넷 연결 구조

프로그래밍 : 데이터 구조와 모듈의 이해가 필요. 리스트, 스택, 트리 구조

즉 상황에 맞게 어떤 자료구조를 사용할지 판단해야함

 

자료구조의 종류

배열, 리스트, 스택, 큐, 그래프, 트리, 최대 힙, 행렬....

선형 자료구조 :리스트, 스택, 큐

색인 자료구조 :검색트리(이진 검색트리, 균형 검색 트리), 해시 테이블

효율적인 자료구조 :우선순위 큐: 힙

관계 처리 자료구조 :그래프

 

알고리즘

문제 해결 과정을 묘사하는 것

문제 해결 절차를 체계적으로 기술한 것

 

문제의 요구 조건: 입력과 출력으로 명시할 수 있다.

알고리즘은 입력에 대한 출력을 만드는 과정을 기술

 

프로그램 = 자료구조 + 알고리즘 + α

 

알고리즘의 기술 방법

1. 자연어를 이용한 서술적 표현

• 단어, 언어, 표현에 의존적
• 모호함
• 이해하기 쉬움

2. 흐름도를 이용한 도식화

• 직관적이고 이해하기 쉬움
• 알고리즘이 복잡할 수록 흐름도 또한 복잡해짐

3. 의사코드를 이용한 추상화 (가상 코드)

• 알고리즘 기술에 가장 많이 사용
• 핵심적인 알고리즘의 내용에 집중 가능
• 프로그래밍 언어에 대한 의존성이 없음

4. 프로그래밍 언어

• 알고리즘의 가장 정확한 기술이 가능
• 내용에 대한 이해를 방해할 수 있음
• 프로그래밍 언어에 대한 의존성 존재

 

추상 자료형 (ADT:Abstract Data Type)

추상 : 세세한 부분을 표현하지 않고 전체적인 이미지를 표현한 것

데이터 타입이 추상적 -> 데이터나 연산이 무엇인지 정의됨 그러나 어떻게 구현할 것인지는 정의되지 않음

추상화 : 중요한 정보는 강조되고 중요하지 않은 구현은 제거

 

ADT : 세부적인 부분에서 벗어나 추상적으로 정의한 데이터 타입

즉, 데이터 타입이 어떤 작업으로 이루어지는지 표현

 

알고리즘의 성능 분석

분석 기법

1. 수행 시간 측정

• 두 개의 알고리즘의 실제 수행 시간을 측정 및 비교
• 실제로 구현 해야함
• 동일한 하드웨어, 동일한 사용 환경에 적용

2. 알고리즘의 복잡도 분석

• 직접 구현하지 않으면서 수행시간을 분석
• 알고리즘이 수행하는 연산의 횟수를 측정

알고리즘 A는

n * n이라는 곱셈 연산을 한번 한다 (1)

그리고 sum이라는 변수이 곱셈한 결과를 한 번 대입한다 (1)

총 두 번의 연산를 한다

 

알고리즘 B는

sum과 n을 더하는 덧셈 연산을 한 번 한다 (1)

그리고 sum이라는 변수에 덧셈 결과를 한 번 대입한다 (1)

그런데 위 연산은 1부터 n번 반복하는 for문 안에서 동작한다

 

다시 덧셈 연산은 총 n 번 한다 (n)

대입 연산은 총 n 번 한다 (n)

그러니까 총 n * n = n^2의 연산을 한다

 

알고리즘 C는

덧셈과 대입 연산을 각각 한 번 한다

그런데 이연산은 N번 반복하는 FOR문 안에 있다

그런데 이 FOR문은 또 N번 반복하는 FOR문 안에 있다

그러니까 n * n + n * n 총 2n^2번 한다

 

빅오(O) 표기법

자료의 개수가 많은 경우 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시한다

 

예)

n = 1000 일 때

n^2 -> 99.9%, n+1 -> 0.1% 라는 결과가 나옴 즉, n + 1은 무시해도 됨

 

 

 

쉽게 말하면 빅오표기법의 시간복잡도는 O(최고차항에서 계수 땐 것)

f(n) = 5 일 때 O(1),

f(n) = n^2 일 때 O(n^2),

f(n) = 2n^2 + n + 1 일 때 O(n^2)