데이터 구조 - (1) 자료구조, 알고리즘, 재귀

ㅈ자료구조

데이터를 저장, 조직, 관리할 때 사용하는 방법을 말한다.

컴퓨터 프로그래밍 언어에서는 효율적인 데이터의 형태를 사용하는 것이 중요하다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

​

자료구조는 아래와 여러 종류로 나뉘어진다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

​

동일한 type을 가지는 배열,

리스트 중간에 데이터를 삽입하거나 삭제할 때 사용하는 링크드 리스트,

행과 열을 가진 2차원 데이터를 사용할 때는 행렬,

LIFO 방식의 스택, FIFO 방식의 큐 등 다양한 형태가 있다.

 

자료구조와 알고리즘

자료구조는 부품으로, 알고리즘은 설계도 정도로 표현할 수 있다.

이 둘이 합쳐져 완성품 즉 프로그래밍 언어로 나타낼 수 있다.

​

알고리즘은 자연어, 순서도, 프로그래밍 언어, 가상코드 등

다양한 형태로 표기한다.

​

자료구조는 추상 데이터 타입(ADT)으로 표현할 수 있다.

이는 데이터 타입이 어떤 작업으로 이루어지는지 추상적으로 표현하는 방법이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

 

재귀

 

자기호출 알고리즘이라고 부르기도 한다.

자신과 성격은 같지만 크기만 작은 알고리즘을 호출하는 알고리즘이다.

정렬, 탐색, 수열에 효과적이지만, 피보나치 수열이나 최적 행렬곱 경로 등을 다룰 때

사용하면 엄청난 시간 복잡도를 가지기에 잘 선별해서 사용해야 한다.

seq(n):
    if(n==1):
        return 1
    else:
        return seq(n-1)+3

 

위 코드와 같이 등차수열을 구할 때 재귀 방식을 사용해서 간단하게 나타낼 수 있다.

반대로 아래와 같이 피보나치 수열을 구현한 경우 엄청난 시간 복잡도를 가지게 된다.

fib(n):
    if(n==1 or n==2):
        return 1
    else:
        return fib(n-1)+fib(n-2)

 

그 이유는 중복 호출로 인해 비효율적으로 시간이 걸리기 때문이다.

이런 경우는 재귀 방식을 사용하지 않는 것이 좋다.

​

대표적인 재귀 예시로 하노이 탑 문제를 풀 때 사용되곤 한다.

아래 영상을 참조하면 좋을 것 같다.

 

출처 : 쉽게 배우는 자료구조 with 파이썬

​

이외에도 선택 정렬을 할 때, 제일 큰 값을 리스트의 맨 오른쪽값과 변경한 후

길이를 줄여가며 원소가 1개 남을 때까지 반복하면 작은 수부터 큰 수 순서로 정렬할 수 있다.

이를 재귀 방법을 활용해서 구현하면 효과적이다.

 

표현법

수식을 표현할 때 연산자의 위치에 따라

전위 표현, 중위 표현, 후위 표현법으로 나뉜다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

중위 표현 방식이 가장 익숙하지만 우선순위의 문제가 발생하기에,

이를 해결할 수 있는 전위 혹은 후위 표현법을 사용하는 것이 좋다.

​

참고로 재귀 알고리즘은 꼭 종료 조건이 있어야 한다.

그렇지 않으면 무한 루프를 돌게 되어, 문제를 해결할 수 없다.

​

이를 수학적 귀납법으로

경계조건, 귀납적 가정, 귀납적 전개를 통해서

재귀 알고리즘이 정상적으로 실행 가능한 지 증명할 수 있다.

아래는 하노이 탑에 수학적 귀납법을 적용한 내용이다.

출처 : 쉽게 배우는 자료구조 with 파이썬