자료구조 & 알고리즘4 [📚누구나 자료구조와 알고리즘] 12-1. 동적 프로그래밍 - 불필요한 재귀 호출 줄이기 재귀는 때로 O(2^N)과 같이 느린 빅오의 원인이 된다. 배열의 최댓값을 구하는 예제 코드로 재귀가 때로 얼마나 많은 비효율적인 호출을 만들어보는지 확인해볼 수 있겠다. def get_max_value(arr): if len(arr) ==1 : # 만약에 인수로 들어온 배열 원소의 갯수가 1개라면 return arr[0] # 최댓값은 해당 원소일 것이다 if arr[0] > get_max_value(arr[1:]) : # 만약 배열의 첫 원소가 나머지 모든 원소들의 최댓값보다 크다면 return arr[0] # 최댓값은 배열의 첫 원소일 것이다. else: # 만약 배열의 첫 원소가 나머지 원소들의 최댓값 보다 작다면 return get_max_value(arr[1:]) # 나머지 원소들 중의 최댓값이.. 2022. 10. 14. [📚누구나 자료구조와 알고리즘] 3. Big-O Notation : O(N), O(1), O(logN), O(N^2) 빅오 (Big-O) 컴퓨터 과학자들이 알고리즘의 효율성(시간복잡도)을 표기하기 위해 수학적 개념을 차용한 방법이 빅 오 표기법이다. [1] 원소가 N개일 때, 알고리즘에 최대 몇 단계가 필요할까? [2] 원소가 N개일 때, 원소가 늘어남에 따라 알고리즘에 필요한 단계 수가 어떻게 늘어날까? 중요 ! 빅오표기법은 결국 위의 질문에 대한 답을 O()의 괄호 내에 나타내는 것이다. O(N) 선형검색 알고리즘의 경우, 최악의 경우 원소 갯수 만큼의 단계가 필요하다. 예를 들어 100개의 원소 중 찾는 원소가 맨 마지막에 있거나, 없는 경우 100번을 모두 검색해야 하기 때문이다. 고로 선형검색을 위의 1번 질문에 대입해보자면 (= 원소가 N개일 때, 선형 검색에는 최대 몇 단계가 필요할까?) 답은 N 이다. 이.. 2022. 9. 13. [📚누구나 자료구조와 알고리즘] 2. 알고리즘이 중요한 까닭 - 선형검색과 이진검색 이전 포스팅에서는 자료 구조의 기본 연산과, 자료 구조에 따라서 각 연산의 효율성이 달라질 수 있다는 것을 다루었다. 자료 구조의 기본 연산과 속도 측정 (시간복잡도)의 이해 자료구조의 기본 연산 자료구조의 네 가지 기본 연산 방법은 읽기, 검색, 삽입, 삭제 이다. 읽기: 특정 '위치'의 '값'을 찾아내는 연산 e.g. A배열의 3번째 값은 무엇인가? 검색: 특정 '값'의 '위치'를 stay-present.tistory.com 이번 포스팅에서는 동일한 자료 구조에서도 더 효율적인 결과를 낼 수 있는 코드(알고리즘)를 사용할 수 있는 방법을 다루어보려고 한다. 알고리즘 Algorithm. 알고리즘은 어떤 일을 수행하기 위한 명령어들의 집합이다. 카카오톡 보내기 알고리즘이 있다고 가정한다면, 이 알고리즘은.. 2022. 9. 8. [📚누구나 자료구조와 알고리즘] 1. 자료 구조의 기본 연산과 속도 측정 (시간복잡도)의 이해 자료구조의 기본 연산 자료구조의 네 가지 기본 연산 방법은 읽기, 검색, 삽입, 삭제 이다. 읽기: 특정 '위치'의 '값'을 찾아내는 연산 e.g. A배열의 3번째 값은 무엇인가? 검색: 특정 '값'의 '위치'를 찾아내는 연산 e.g. 'iphone'이라는 값이 A라는 배열에 존재하는가? 있다면 몇번째 위치에 존재하는가? 삽입: 새로운 값을 추가하는 연산 e.g. 'ipad'라는 값을 A라는 배열에 추가 삭제: 특정 인덱스의 값을 제거하는 연산 e.g. 'iMac'이라는 값을 A라는 배열에서 삭제 자료구조 연산의 속도 측정 자료구조를 배우는 궁극적인 목적은 가장 효율적인 자료구조를 사용하기 위해서이다. 그렇다면, 효율성이란 어떻게 측정될 수 있을까? 우선 '속도가 빠른' 자료구조가 효율적이라고 할 수 있.. 2022. 9. 6. 이전 1 다음 반응형
