학습 주제
-
코딩 테스트 특강
-
선형배열
-
정렬, 탐색,
-
재귀 알고리즘
-
알고리즘의 복잡도
학습내용
데이터가 커짐에 따라 효율을 고려해야함.
작은 데이터는 처리에 큰 차이가 없지만 큰 데이터일수록 알고리즘이 중요해짐.
정렬된 구조가 찾기 편함.
최적의 해를 찾기 위해 자료구조를 이해해야함.
배열 – 같은 종류의 데이터
리스트 – 파이썬에서 사용하는 데이터 타입.
파괴적 함수와, 비파괴적 함수 구분하기
.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]
어려운 점.
바로 코드가 구현될 정도로 숙달되지 않음. 좀 더 많이 풀어보고, 다양한 문제 접해보기
