파이썬의 특징 : 코드가 간결해서 짧게 짤수있지만 메모리를 많이 잡아먹고 실행시간도 긴편이다.
파이썬은 인터프리터 언어이다.
-> 컴파일 과정에서 기계어로된 목적파일이 있는게아닌
컴파일러를 거쳐도 바이트코드로 한줄한줄 실행되기에 10번째 줄에 오류가 있다고하면 9번째 줄까지는 실행된다.
그래서 코드수정시 맛탱이 간부분만 쉽게 들어내서 수정이 가능하다.
이러한 언어적 특징으로 동적언어이다
컴파일과정에 미리 자료형을 결정해놓는게 아닌 동적으로 바로바로 실행되는 순간순간(런타임)에 자료형이 결정된다.
파이썬의 변수 할당방식
-깊은복사와 얕은복사
얕은 복사: 값을 복사하는것
깊은 복사: 주소값을 복사시켜버림
immutable(불변형 숫자,문자열, 튜플)
immutable은 상식적으로 얕은 복사로 굴러간다.
mutable(가변형 딕셔너리,리스트,NumPy의 배열(ndarray)
이 코드에서는 깊은복사가 일어나서 주소값이 복사되기 때문에
2번과 같은 현상이 일어난다. 이를 해결하기위해 즉 우리가 생각하는 값만 복사해버리는 얕은복사를 위해서는
이런식으로 h=z[:] 이렇게 표현한다면 얕은복사가 일어난다.
대부분 우리는 얕은 복사를 쓰기 때문에 다음과 같은 얕은 복사 표현식을 사용하자
****다음 넘어가기전 참고자료!!! ******
파이썬에서는 리스트를 곱해버리면 곱한 숫자만큼의 횟수로 뒤에 같은 값 붙여줌
0 5개를 원소로 갖는 리스트를 만들고싶다 하면
a = [0]*5 이런식으로 표현가능하다
배열을 곱셈을 통해 2차원배열을 만들면 깊은 복사가되에 같은 주소값을 갖는 배열이 두개가 생성되는것이다.
이또한 우리가 아마 원하는게 아닐것이다.
이에 대한 해결책은
2차원배열을 선언할때 for문을 사용해서 만든다면 얕은복사가 되어 원하는 결과물을 얻을수 있을것이다.
시간복잡도란?
알고리즘의 성능을 말할 때
실행 시간 대신 시간 복잡도를 사용합니다.
실행시간의 경우 코드 실행 환경과 언어에 따라 매우 달라지기 때문에
명령어의 실행 횟수인 시간 복잡도를 사용합니다!
시간 복잡도가 다항식으로 나온다면 최고차항이 가장 중요!!
대부분 bigO표기법을 사용한다.
이진탐색 같은거 매번할때 단계를 거칠때마다 n/2로 해야할게 줄어듬 이런게 log n이다.
사실 이런경우 거의 없단다 brute force 빼고
이경우는 피보나치 수열처럼 재귀로 불러내서 단계를 들어갈때 마다 해야할일이 *2되는걸 뜻한다
참고 사항 -> 파이썬 내장함수의 시간 복잡도 -> 알고리즘짤때 내장함수 사용한다면 이거 고려하며 짜야한다.
https://daimhada.tistory.com/56
Python 내장 함수의 시간 복잡도
Python 컨테이너 메소드의 시간 복잡도(time complexity)는 어떻게 될까? 알고리즘을 풀면서 컨테이너를 조작하기 위해 기본 메소드들을 많이 활용하게 되었고, 메소드의 시간 복잡도가 궁금해졌
daimhada.tistory.com
자료구조란?
1. Stack
stack 같은경우 파이썬에서 기본제공하는 리스트로 구현가능하다
append()와 pop()로 삽입 삭제하고
Top즉 데이터 조회는 가장위에 있는것만 할수있으므로
위쪽 index -1로 조회한다.
2.Queue
요것도 peek는 index로 접근하고
여기서 볼것이 데이터 삽입의 경우append로 해주면 되지만
데이터 삭제의경우 list 쓰면 복잡해져서 시간복잡도가 O(n)이 걸릴것이다.
고로 시간복잡도를 낮추기위해 collections 모듈의 deque(덱)으로 구현하자 popleft()는 O(1)이니까
한마디로 사실 스택이든 큐든 다 deque로 구현해도된다.
3.deque
덱은 넣고 빼고 할수있는 부분이 양극단인것이다.
삭제, 삽입을 앞뒤에서 할수있다.
collection 모듈의 deque로 구현하자 모든 메서드가 O(1)이라 시간복잡도가 낮아서 좋다.
deque란
Deque(데크)는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다. 아래의 [그림1]은 deque의 구조를 나타낸 그림이다.
python에서 collections.deque는 list와 비슷하다. list의 append(), pop()등의 메소드를 deque에서도 제공한다. 예제 소스코드들을 통해 list와 deque의 차이를 알아보도록 하자. collections.deque의 자세한 설명은docs.python.org에서 확인할 수 있다.
여기서부터 추가공부 하자