[(Programmers 강의) Algorithm with Data Structure 01강. 자료구조와 알고리즘(Data Structure & Algorithm)]

자료구조와 알고리즘

0. 들어가기에 앞서

• 대상 : Python 언어에 대해 어느정도 지식이 있는 사람(기초 문법, 구조, 자료형)

0-1. Python 언어의 몇가지 기초적인 자료형

"This is String"        # 문자열(str)
[5, 9, 2, 7]            # 리스트(list)
{'a' : 6, 'bc' : 4}     # 사전(dict)
# 이 외에 순서쌍(tuple), 집합(set), 등등 존재

{'a': 6, 'bc': 4}

웬만한 것들은

Python에서 이미 제공하는 데이터 타입으로

다 해결할 수 있을것 같은데…?

자료구조(Data Structure)는 대체 왜 알아야 하는걸까?

• Python에서 제공하는 기본적인 자료형들로 해결할 수 없는, 또는 어려운, 효율적이지 않은 문제들을 해결하기 위해서!

• 우리가 해결해야 할 문제의 종류에 따라 적합한 자료구조는 달라짐.

• 앞으로 어떤 문제 종류에 어떤 자료구조가 적합한지 예제를 보면서 학습할 예정

1. 알고리즘

# 작성된 리스트에서 최대치를 찾는데 걸리는 시간을 알아보자

import time

n = int(input("Number of elemnts : "))
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))

Number of elemnts : 100000000
Searching for the maximum value...
Maximum element = 99999999, Elapsed time = 1.44

• 어떤 리스트에서 최댓값을 찾기 위해서는 리스트의 모든 요소를 검사해야 한다.

  • 요소수가 백만, 천만, 억… 이면 요소수 만큼 검사를 진행하기 때문에

  • 점점 프로그램의 실행 시간이 늘어남

1-1. 알고리즘이란?

• [사전적 정의] : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합

• [프로그래밍] : 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

549를 찾아보세요 1.

---

549를 찾아보세요 2.

---

549를 찾아보세요 1. 정답

---

549를 찾아보세요 2. 정답

___

1번과 달리 2번은 정렬되어 있기 때문에 대부분 1번보다 일찍 찾아냈을 것이다.

• 순서대로 있기 때문에 더 쉽다!

• 이와 같이 무슨 일을 하냐에 따라서 최적의 해법은 다르다.

해결하고자 하는 문제에 따라(응용 종류와 범위에 따라)

최적의 해법은 서로 다르다.

• 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 함.

2. 과제 : 프로그래머스 테스트에 익숙해지기

1강 실습 : 리스트 원소 합

Link

입력으로 주어지는 리스트 x 의 첫 원소와 마지막 원소의 합을 리턴하는 함수 solution()을 완성하세요.

def solution(x):

    answer = 0

    answer = x[0] + x[(len(x) - 1)]

    return answer

# My answer

def solution(x):
    answer = 0
    answer = x[0] + x[-1]
    return answer

• 실행 결과

# Teacher answer

def solution(x):
    answer = 0
    answer = x[0] + x[len(x)-1]
    return answer