자료구조와 알고리즘

1 자료구조(data structures)

1.1 파이썬의 기본적인 데이터 타입

• 문자열 (str) “This is a string”
• 리스트 (list) [1, 4, 3, 2]
• 사전 (dict) {’A’:1, ‘B’:2}
• 순서쌍 (tuple)
• 집합 (set)
• 등...

1.2 자료구조를 왜 알아야 하는가?

• 리스트 속 최대값을 찾는 max() 함수의 실행 시간을 측정하는 코드

  import time
  
  n = int(input("Number of elements: "))
  haystack = [k for k in range(n)]
  
  print("Searching for the maximum value...")
  
  ts = time.time()
  maximum = max(haystack)
  elapsed = time.time() - ts
  
  print("Maximum element = %d, Elapsed time = %.2f" % (maximum, elapsed))

  • 실행할 때, 10만개, 100만개, 1000만개, 1억개 .. 까지 입력할 수록 0.00, 0.02, 0.29, 40… 개수에 비례하는 시간이 든다.
    → 더 시간을 절약할 수 있는 방법은 없을까?
• 기본적으로 제공하는 자료구조가 아닌, 우리가 또다른 효율적인 자료구조를 직접 만든다면 시간을 절약할 수 있다
• 풀어야하는 문제에 따라 활용하는 자료구조의 성질이 어떤지에 대해 생각해보고 선택할 수 있어야 한다

2 알고리즘(algorithm)

2.1 알고리즘(algorithm) 이란?

• 사전적 정의: 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
• 프로그래밍: 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

해결하고자 하는 문제에 따라 (응용 종류와 범위에 따라) 최적의 해법은 서로 다르다
→ 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 한다!