자료구조/알고리즘 0410

학습 주제

• 코딩 테스트 특강

• 선형배열

• 정렬, 탐색,

• 재귀 알고리즘

• 알고리즘의 복잡도

학습내용

데이터가 커짐에 따라 효율을 고려해야함.

작은 데이터는 처리에 큰 차이가 없지만 큰 데이터일수록 알고리즘이 중요해짐.

정렬된 구조가 찾기 편함.

최적의 해를 찾기 위해 자료구조를 이해해야함.

배열 – 같은 종류의 데이터

리스트 – 파이썬에서 사용하는 데이터 타입.

파괴적 함수와, 비파괴적 함수 구분하기

.insert, .pop 는 O(1) 상수 시간내 처리

.insert, del 는 O(n) – 리스트가 길수록 오래걸림, 선형시간

.index O(n)

정렬.

내장함수 sorted()

메서드 sort()

선형탐색 길이에 비례하는 시간 소요 – O(n)

이진탐색 정렬된 경우 사용

이진탐색 구현

def binary_search(L,target):
lower = 0
upper = len(L) - 1
idx = -1
while lower <= upper:
middle = (lower + upper) // 2
if L[middle] == target:
return middle
elif L[middle] < target:
lower = middle + 1
else:
upper = middle - 1

피보나치 반복적 구현

def solution(x):
answer = 0
dict = {
0:0,
1:1
}
for n in range(x+1):
if n in dict:
continue
else:
dict[n] = dict[n-1] + dict[n-2]
print(dict[n])
return dict[n]
어려운 점.

바로 코드가 구현될 정도로 숙달되지 않음. 좀 더 많이 풀어보고, 다양한 문제 접해보기