📖학습주제
자료구조/알고리즘 풀기(1)
자료구조(Data Structure) & 알고리즘(Algorithm)
자료형
Python에는 여러가지 자료형들이 있다. 예를 들어
문자열(str) : "This is a string"
리스트(list) : [5, 9, 2, 7]
사전(dict) : {'a' : 6, 'bc' : 4}
등 익숙하게 다뤘던 자료형들이 있다.
자료구조를 알아야 하는 이유?
여러가지 자료형들이 있으니 이를 활용하면 굳이 자료구조에 대해 알 필요가 없어보인다.
그런데도 자료구조에 대해 알아야 하는 이유?
기본적인 데이터 타입으로 해결이 어렵거나 불가능한 혹은 기본적인 데이터 타입을 이용하기에는 비효율적이거나 비효과적인 문제들을 해결하기 위해서 자료구조를 이용한다.
알고리즘
-
사전적 의미 : 어떤 문제를 해결하기 위한 절차, 방법, 명령들의 집합
-
프로그래밍 : 주어진 문제의 해결을 위한 자료구조와 연산방법에 대한 선택
해결하고자 하는 문제에 따라 최적의 해법이 서로 다르다. 따라서 어떤 해법을 사용할지를 알기 위해 자료구조를 이해해야한다.
배열(Array)
배열
원소들을 순서대로 늘어놓은 것을 뜻하며 각 원소에는 번호(index)가 붙는다. 많은 프로그래밍 언어에서 번호를 0부터 센다.
Python에서는 list가 있다. (동일한 타입의 원소만 줄세울 수 있는 다른 언어와는 달리 리스트는 서로 다른 타입의 원소들도 줄 세울 수 있다.)
리스트(배열) 연산
원소 덭붙이기 : .append(value)
끝에서 꺼내기 : .pop()
-> 빠르게 할 수 있는 일(리스트의 길이와 무관, 상수시간(O(1))
원소 삽입 : .insert(index, value)
원소 삭제 : del(L[index])
-> 리스트가 커지면 오래걸림(리스트이 길이에 비례, 선형시간(O(n))
정렬 & 탐색
배열 정렬
배열 내 원소들을 기준에 맞춰 재배열
sorted()
- 내장함수
- 정렬된 새로운 리스트를 얻어냄
sort
- 리스트의 메서드
- 해당 리스트 정렬
정렬순서 반대로 : reverse = True
문자열로 이루어진 리스트의 경우
정렬순서는 사전순서(알파벳순서)를 따른다.
key를 이용한 방법으로 정렬기준을 정할 수 있다.(key = lambda x : len(x) : 길이순 정렬)
탐색 알고리즘
선형탐색(Linear Search)
- 앞의 원소부터 순차적으로 탐색
- 리스트의 길이에 비례하는 시간 소모(O(n))
- 최악의 경우 모든 원소 비교
이진탐색(Binary Search)
- 리스트가 이미 정렬되었을 경우에만 적용가능(크기순으로 정렬됐음을 이용)
- 한번 비교가 일어날 때 리스트를 반씩 줄인다.(divide & conqure) (O(logn))
재귀 알고리즘(Recursive Algorithm)
재귀함수
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수
장단점
사람의 생각을 옮겨놓기에는 좋으나 반복함수와 비교했을 때 효율성이 떨어진다.
알고리즘 복잡도(Complexity of Algorithm)
시간복잡도
문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계
공간복잡도
문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계
BIG-O Notation
- 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현한 것
- 알고리즘의 복잡도를 표현할 때 주로 쓰인다.
O(1) : 입력의 크기와 상관없이 같은 시간 소모
O(n) : 입력의 크기에 비례하는 시간 소모
O(log n) : 입력의 크기의 로그에 비례하는 시간 소모
BIG-O Notation의 경우 개념은 이해가 가지만 코드를 봤을 때 이 코드가 얼마의 복잡도를 가지는지 알기가 어려운 것 같다. 특히 log 복잡도의 경우 많이 헷갈린다.
