[자료구조&알고리즘] 1주차 - 1

자료구조 

• 데이터를 저장, 조직, 관리하는 방법
• 문제 해결에 사용할 부품
• 프로그래밍과 문제 해결
  • 데이터와 구조 모듈에 대한 이해
  • 프로그래밍 언어, 정수, 문자열,....
  • 리스트, 스택, 큐, 우선순위 큐, 검색트리, 그래프,.....
• 종류
  • 선형 자료구조 
    • 배열
      • 연속적인 메모리에 데이터를 저장하는 자료구조
      • 특징 : 같은 형태의 데이터 집합을 같은 사이즈의 메모리로 나열
    •  연결리스트
      • 데이터를 연결하는 방식으로 저장하는 자료구조
      • 특징 : 한 개의 노드가 데이터부분과 다음 데이터를 가르키는 포인터부분으로 나뉨
    •  행렬
      • 파이썬에서는 이중 리스트로 구현하게 되는 자료구조
      • 특징 : 행과 열로 이루어져있음
    •  스택
      • 특징 : 마지막에 들어온 데이터가 가장 처음으로 나가는(Last In First Out) 구조로 이루어짐
    •  큐
      • 특징 : 처음 들어온 데이터 처음으로 나가는(First In First Out) 구조로 이루어짐
  • 색인 자료구조
    • 트리
      • root로 부터 각각의 노드로 이어져 가는 형태의 자료구조
      • 최대 힙 : 트리의 한 종류로서 최대값을 쉽게 찾기 위한 자료구조
      • 이진 검색 트리, 균형 검색 트리
  • 효율적인 자료구조
    • 우선순위 큐 : 힙
  • 관계 처리 자료구조
    •  그래프
      • 각각의 노드들을 어떻게 연결하는지에 대한 정보를 저장

•  

알고리즘

• 문제 해결 과정을 묘사하는 것
• 문제 해결 절차를 체계적으로 기술한 것
  • 해결해야 할 어떤 문제가 주어졌을 때, 이 문제의 해답을 구하기 위한 절차를 순서대로 명확하게 나타낸 것
• 문제의 요구 조건
  • 입력과 출력으로 명시할 수 있다
  • 알고리즘은 입력에 대한 출력을 만드는 과정을 기술
• ex) 어떤 숫자의 절댓값 구하기
  • 입력 : 절댓값을 구할 실수 a
  • 출력 : a의 절댓값
  • 알고리즘 → a에 a를 곱하고 곱한 수의 양의 제곱근을 구한다.
• 특징
  • 여러 방법으로 표현 가능
  • 하나의 문제를 해결하기 위한 여러 가지 알고리즘이 존재할 수 있음
  • 동일한 문제에 대해 매우 다른 전략을 기반으로 알고리즘을 작성할 수 있고, 이 알고리즘들은 매우 다른 속도로 문제를 해결함
• 알고리즘을 공부하는 목적
  • 특정한 문제를 위한 알고리즘의 습득
  • 체계적으로 생각하는 훈련
  • 지적 추상화의 숙련

자료구조와 알고리즘

• 자료구조는 알고리즘 과목의 직전 단계이기도 하고, 그 자체로 여러 알고리즘을 포함
• 프로그램 = 자료구조 + 알고리즘 + a