1강: 안녕, 자료구조 & 알고리즘 ! // 2강 : 선형 배열(Linear Array)
- 웬만한 것들을 Python에서 이미 제공하는 데이터 타입으로 다 해결할 수 있는데 왜 자료구조를 알아야 하는건지
- 효과적으로 해결하고자 하는 문제가 무엇이냐에 따라서 적합하게 이용하려는 자료구조가 달라짐
- 기본적으로 제공되는 데이터 타입만으로는 해결할 수 없는 문제가 있다
- 알고리즘이란?
- 사전적 정의
- 어떤 문제를 해결하기 위한 절차, 방법, 명령어 들의 집합
- 프로그래밍
- 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
- 사전적 정의
- 해결하고자 하는 문제에 따라 (응용 종류와 범위에 따라) 최적의 해법은 서로 다르다
- 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 함
실습1 2 3
# 입력으로 주어지는 리스트 x의 첫 원소와 마지막 원소의 합을 리턴하는 함수 solution()을 완성하세요 def solution(x): return x[0] + x[-1]
- 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 함
2강 : 선형 배열(Linear Array)
선형배열이란?
- 데이터들이 선(line) 처럼 일렬로 늘어선 형태
-
보통 프로그래밍에서
배열(array)라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻하는데, Python에서는 서로 다른 종류의 데이터 또한 줄 세울 수 있는리스트(list)라는 데이터형이 존재한다 -
배열(Array)
- 원소들을 순서대로 늘어놓은 것
ex) 2 7 -2 5 10
-
리스트(List)
- 아무런 타입의 데이터라도 배열에 줄을 세울 수 있다.(융통성이 있다)
- 문자열들의 길이가 같지 않아도 된다
- 각 원소가 서로 다른 데이터 타입을 가져도 상관 없다
-
리스트(배열) 연산
-
리스트의 길이와 관계 없이 빠르게 실행 결과를 보게되는 연산들
- 원소 덧붙이기 :
append() -
끝에서 꺼내기:
pop() - 리스트의 길이와 무관(상수 시간)
- O(1)
- 원소 덧붙이기 :
-
리스트의 길이에 비례해서 실행 시간이 걸리는 연산들
- 원소 삽입하기 :
insert() - 원소 삭제하기 :
del() - 리스트의 길이에 비례(선형 시간)
- O(n)
- 원소 삽입하기 :
- 원소 탐색 :
index()- 리스트 원소들의 순서에 아무런 것도 가정할 수 없이 앞에서부터 발견될 때까지 찾아 나가야 하므로 어느 원소를 찾느냐에 대한 확률이 모두 같다면 평균
N / 2회수의 비교가 필요하다 (리스트의 길이를N이라 할 때). - 리스트의 길이가 길어지면 그에 비례하여 증가 : O(N)
실습1 2 3 4 5 6 7 8 9
# 정련된 리스트에 원소 삽입 def solution(L, x): for i in range(len(L)): if(x < L[i]): L.insert(i, x) break if(x not in L): L.append(x) return L
- 리스트 원소들의 순서에 아무런 것도 가정할 수 없이 앞에서부터 발견될 때까지 찾아 나가야 하므로 어느 원소를 찾느냐에 대한 확률이 모두 같다면 평균
-
1
2
3
4
5
6
7
8
9
# 리스트에서 원소 찾아내기
def solution(L, x):
res = []
for i in range(len(L)):
if(L[i] == x):
res.append(i)
if(len(res) == 0):
res = [-1]
return res
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.
