[W03] 자료형과 자료구조, 알고리즘

옆 팀의 코어타임을 귀동냥하며 듣다가 갑자기 나도 궁금해져서 2학년 때 전공 자료들을 뒤져서 찾아본 자료형과 자료구조, 자료구조와 알고리즘

자료구조: 여러 데이터를 효율적으로 처리할 수 있도록, 자료를 어떤 방식으로 저장하고 관리할지 체계적으로 구조화한 것

자료구조의 필요성
− 컴퓨터에서 처리할 자료들을 효율적으로 관리하기 위해 구조화
− 자료의 특성에 따라 자료의 형태를 구성하고 처리하고 저장함

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

알고리즘
− 문제를 해결하기 위해 컴퓨터가 따라야 할 순서를 구체적으로 기술하는 것
− 컴퓨터로 문제를 풀기위한 단계적인 절차
− 특정한 일을 수행하는 명령어들의 집합

알고리즘의 조건
− 입력: 0개 이상의 입력이 존재해야 함
− 출력: 1개 이상의 출력이 존재해야 함
− 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 함
− 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함
− 각 명령어들은 실행 가능한 연상이어야 함

알고리즘의 기술 방법
− 자연어
: 인간이 읽기 쉬움.
△ 자연어의 단어들을 정확하게 정의하지 않으면 의미전달이 모호해질 우려가 있음

− 흐름도(flow chart)
: 직관적이고 이해하기 쉬움.
△ 복잡한 알고리즘의 경우 많이 복잡해짐

− 의사코드
: 알고리즘 기술에 가장 많이 사용
프로그램 구현할 때의 여러가지 문제들을 감출 수 있음
알고리즘의 핵심적인 내용에만 집중 가능

− 프로그래밍 언어
알고리즘의 가장 정확한 기술이 가능
△ 실제 구현 시 많은 구체적인 사항들이 알고리즘의 핵심적인 내용에 대한 이해를 방해할 수 있음

자료형: 데이터의 종류
− 데이터의 집합 + 연산의 집합
− 자료형을 정의할 때는 실행가능한 연산에 대해서도 고려해야 함

• 기초 자료형 - int / float / double / char
• 파생 자료형 - 배열 / 포인터
• 사용자 정의 자료형 - 구조체 / 공용체 / 열거형
  

추상 데이터 타입
− 데이터 타입을 추상적(수학적)으로 정의한 것
− 데이터나 연산이 무엇인가는 정의되지만, 데이터나 연산을 어떻게 컴퓨터상에서 구현할 것인지는 정의되지 않음
-> 구현 세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개함.

ex) Wallet의 ADT

Operations : 

    • int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
        - 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다. 
        - 두 번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수 를 전달한다. 
        - 지갑에서 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

    • int PutMoney(Wallet * pw, int coinNum, int billNum)
        - 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
        - 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달한다. 
        - 지갑에 넣은 만큼 동전과 지폐의 수가 증가한다. 

추상 데이터 타입의 유래
: 추상화 -> 정보 은닉기법 -> 추상 자료형
− 추상화랑 사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거하는 것

추상 데이터 타입의 정의
− 객체 : 추상 데이터 타입에 속하는 객체가 정의됨
− 연산 : 객체들 사이의 연산(추상 데이터 타입과 외부를 연결하는 인터페이스의 역할)이 정의됨.

추상자료형(ADT) 특징
− 사용자들은 ADT가 제공하는 연산만을 사용할 수 있다
− 사용자들은 ADT가 제공하는 연산들을 사용하는 방법을 알아야 함
− 사용자들은 ADT 내부의 데이터를 접근할 수 없다
− 사용자들은 ADT가 어떻게 구현되는지 모르더라도 ADT를 사용할 수 있음
− ADT 구현을 변경하더라도 인터페이스가 변경되지 않으면 사용자들은 ADT를 같은 방식으로 사용할 수 있음

자료형 이면서 자료구조 역할도 하는 것( 파이썬 기준)

• list → 자료형이면서 순차 자료구조
• dict → 자료형이면서 해시 테이블 기반 자료구조
• set → 자료형이면서 해시 기반 집합 자료구조
• tuple → 자료형이면서 순차적으로 데이터를 저장하는 구조
• deque → collections에서 제공하는 자료형이면서 덱 자료구조
• heapq → 조금 다름. 별도 자료형은 아니고, list를 힙 자료구조처럼 사용하게 해주는 모듈

	ex) a=[1,2,3]

	a의 자료형 : list
	알고리즘/자료구조 관점 : 데이터르 ㄹ순서대로 저장하는 선형 자료구조

• 자료형(값의 종류 + 그 값에 가능한 연산)
  : int,float,bool,char

	a = 10        # int
	b = 3.14      # float
	c = True      # bool
	d = "hello"   # str

• 자료구조
  : 스택,큐,트리,그래프,연결리스트
  ⁎ 스택,큐 : 파이썬에 기본 자료형이 있는 건 아니고, list나 deque를 이용해서 구현함

• 자료형인 동시에 자료구조 역할
  : list,dict,set

	a = [10, 20, 30]

	print(type(a))
	# <class 'list'>

− 리스트: 자체가 여러 데이터를 순서대로 저장하고 관리
-> 자료구조 관점에서는 데이터를 저장하는 구조
-> 파이썬 관점에서는 자료형

⇒ 스택도 자료형이 될 수 있을까?
: 프로그래밍 언어에서 Stack이라는 타입을 따로 만들어 제공한다면 그 언어에서는 자료형이 될 수도 있음.

ex) 
class Stack:
	...
    
s=Stack() 
# -> Stack은 파이썬에서 사용자 정의 자료형(ADT)인 동시에 스택 자료구조를 구현함

⇛
자료형 : 'PL에서 어떤 값과 연산을 제공하는가'에 초점
자료구조: '데이터를 어떤 구조로 조직해서 저장하고 처리하는가'에 초점