본문 바로가기
반응형

Study with Yedol/코딩테스트 준비12

이코테 강의 몰아보기 | 6. 다이나믹 프로그래밍 [1] 다이나믹 프로그래밍: 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹  프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 1. 피보나치 수열: 피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2)print(fibo(4))  2. 메모이제이션(Memoization): 다이나믹 프로그래밍을 구현하는 방법 중 하나로 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.- 같은 문제를 다시.. 2024. 5. 8.
이코테 강의 몰아보기 | 5. 이진 탐색 [1] 이진탐색 알고리즘 1. 순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞으로부터 데이터를 하나씩 확인하는 방법 2. 이진탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법- 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 2-1. 이진 탐색의 시간 복잡도: 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2^n에 비례한다.즉, 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장한다. # 이진 탐색 소스코드 구현(재귀 함수)def binary_search(array, target, start, end): if start > end: return None mid = (sta.. 2024. 5. 7.
이코테 강의 몰아보기 | 4. 정렬 알고리즘 [1] 정렬 알고리즘 1. 정렬(Sorting): 데이터를 특정한 기준에 따라 순서대로 나열하는 것.- 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 2. 선택 정렬(Selection Sort): 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.즉, 매번 현재 범위에서 가장 작은데이터를 골라서 가장 앞쪽으로 정렬하는 것# 선택 정렬array = [7,5,9,0,3,1,6,2,4,8]for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): min_index = j array[i], array.. 2024. 4. 25.
이코테 강의 몰아보기 | 3. DFS & BFS [1] 그래프 탐색 알고리즘 :DFS/BFS 1. 그래프 탐색 알고리즘1) 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정- 대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있다. 2) 스택 자료구조: 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조stack = []# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()stack.append(5)stack.append(2)stack.append(3)stack.append(7)stack.popstack.append(1)stack.append(4)stack.pop()# 최상단 원소부터 출력(가장 나중에 들어온 것부터)print(stack[::-1])# 최하단 원소부터 출력(.. 2024. 4. 25.
반응형

티스토리툴바