1. 자료구조와 알고리즘

• 일상 생활에서 자료를 정리하고 조직화하는 이유는?
• 자료구조와 알고리즘의 관계
  자료구조는 알고리즘 과목의 직전 단계이기도 하고, 그 자체로 여러 알고리즘을 포함

자료구조

컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조

선형 자료구조

항목들을 순서적으로 나열하여 저장하는 창고
항목 접근 방법에 따라 다시 세분화

• 리스트 : 가장 자유로운 선형 자료구조
• 스택, 큐, 덱 : 항목의 접근이 전단이나 후단으로 제한

비선형 자료구조

항목들이 보다 복잡한 연결관계

• 트리 : 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조
  ㄴ힙 트리는 우선순위 큐
  ㄴ이진 탐색트리나 AVL트리 : 탐색을 위한 트리 구조
• 그래프 : 가장 복잡한 연결 관계를 표현
  다양한 문제를 해결하기 위한 기본 구조로 사용된다.

알고리즘

컴퓨터로 문제를 풀기 위한 단계적인 절차 ex)사전에서 단어 찾기

알고리즘의 조건

• 입력 : 0개 이상의 입력이 존재하여야 한다.
• 출력 : 1개 이상의 출력이 존재하여야 한다.
• 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야한다.
• 유한성 : 한정된 수의 단계 후에는 반드시 종료 되어야 한다.
• 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.

알고리즘의 기술 방법

• 자연어 : 읽기 쉬움. 단어들을 정확하게 정의하지 않으면 의미 모호.
• 흐름도 : 직관적. 이해하기 쉬움. 복잡한 알고리즘→상당히 복잡!(대형프로그램에서 사용불편)
• 유사코드
  프로그램을 구현할 때의 여러가지 문제들을 감출 수 있음
  알고리즘의 핵심적인 내용에만 집중 가능
• 특정 언어
  알고리즘의 가장 정확한 기술 가능
  구현시의 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해
  파이썬: C나 자바보다 훨씬 간결한 표현 가능

2. 추상자료형

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

프로그래머가 추상적으로 정의한 자료형

• 데이터 타입을 추상적으로 정의한 것
  ㄴ 데이터나 연산이 무엇인가를 정의함
  ㄴ 데이터나 연산을 어떻게 구현할 것인지는 정의하지 않음
• 시스템의 정말 핵심적인 구조나 동작에만 집중

예 Bag의 추상 자료형

bag = []

def contains(bag,e):
    return e in bag #boolean

def insert(bag,e):
    bag.append(e)
    
def remove(bag,e):
    bag.remove(e)
    
def count(bag,e):
    return bag.len()

insert(bag,"휴대폰")
insert(bag,"지갑")
insert(bag,"손수건")
insert(bag,"빗")
insert(bag,"자료구조")
insert(bag,"야구공")
print(f"mybag: {bag}")
insert(bag,"빗") #중복
remove(bag,"손수건")
print(f"mybag: {bag}")
contains(bag,"빗")

3. 알고리즘의 성능 분석

1. 실행 시간을 측정하는 방법

• 두개의 알고리즘의 실제실행시간을 측정하는것
• 실제로 구현하는 것이 필요
• 동일한 하드웨어를 사용하여야 함

import time

my_bag = []
start = time.time()

#...
insert(bag,"휴대폰")
insert(bag,"지갑")
insert(bag,"손수건")
insert(bag,"빗")
insert(bag,"자료구조")
insert(bag,"야구공")
print(f"mybag: {bag}")
insert(bag,"빗") #중복
remove(bag,"손수건")
print(f"mybag: {bag}")
print(contains(bag,"빗"))
#
end = time.time()

print(f"실행시간 = {end - start}")

2. 알고리즘의 복잡도를 분석하는 방법

• 직접 구현하지 않고서도 수행 시간을 분석하는 것
• 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
• 일반적으로 연산의 횟수는 n의 함수

시간복잡도분석 : 수행시간분석
– 산술, 대입, 비교, 이동의 기본적인 연산 고려
– 알고리즘 수행에 필요한 연산의 개수를 계산
– 입력의 개수 n에 대한 함수->시간복잡도 함수, T(n)

• 빅오표기법: 대부분 채택되는 표기법

  ex: 등교 시간 분석
  • 집을 나와서 지하철역까지는 5분, 지하철을 타면 학교 까지 30분, 강의실까지는 걸어서 10분 걸린다
  • 최선경우Ω(n^2): 수행시간이 가장 빠른 경우
  집을 나와서 5분 후 지하철역에 도착하고, 운이 좋게 바로 열차를 탄 경우를 의미한다. 따라서 최선경우 시간은 5 + 20 + 10 = 35분
  • 최악경우O(n^2): 수행시간이 가장 늦은 경우 가장 널리 사용된다.
  열차에 승차하려는 순간, 열차의 문이 닫혀 서 다음 열차를 기다려야 하고 다음 열차가 10분 후에 도착한다면, 최악경우는 5 + 10 + 20 + 10 = 45분
  • 평균경우θ(n^2): 대략 최악과 최선의 중간이라고 가정했을 때, 40분이 된다.

공간복잡도분석:수행시 필요로하는 메모리공간분석

4. 시간 복잡도 분석 : 순환 알고리즘

순환알고리즘이란

알고리즘이나 함수가 수행도중에 자기자신을 다시 호출하여 문제를 해결하는 기법
정의자체가 순환적으로 되어 있는 경우에 적합

팩토리얼 계산

def factorial(n):
	if n == 1:
    	return 1
    else :
    	return n * factorial(n-1) 

함수안에 함수를 배치하면 순환 함수이다.

거듭제곱

피보나치 수열(반복이 우세)

처음에 작은 값을 넣었을때는 순환이 내용과 다르게 더빨랐지만 큰수를 넣었더니 차이가 확연히 난다.

하노이의 탑

반복함수는 만들어봐야할 것 같다.