KDT TIL Note/알고리즘3 [알고리즘 자습] 대표적인 데이터 구조: 해쉬 테이블(Hash Table) 1. 구조 : 키(key)에 데이터(value)를 저장하는 데이터 구조 key를 가지고 해싱 함수를 통해 데이터의 주소를 알아내, 데이터를 순차적으로 검색할 필요없이 바로 받아올 수 있어 접근 속도나 처리 속도가 획기적으로 빨라짐 대표적인 예로 파이썬의 딕셔너리 자료형이 이 해쉬 테이블로 내부구조가 되어 있음 => 파이썬에서는 딕셔너리 타입을 사용하면 되므로 해쉬를 별도로 구현할 필요가 없다. 배열로 미리 Hash Table 2. 용어 해쉬: 임의 값을 고정 길이로 변환하는 것 해쉬 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수: key에 대해 산술 연산을 하여 데이터의 위치를 찾을 수 있는 함수 해쉬 값 또는 해쉬 주소: key를 해싱 함수로 연산해 해쉬 값을 알아내고, 이 .. 2022. 12. 23. [알고리즘 자습] 문제 해결 접근법 알고리즘이란? 특정 작업을 달성하기 위한 혹은 문제를 해결하기 위해 수행해야 하는 일련의 과정이나 단계를 의미한다. 알고리즘 문제를 풀기 위해, 1. 문제 해결을 위한 계획을 생각해본다. 2. 일반적인 문제 해결 패턴을 파악하고 익힌다. 1. 문제의 이해 ① 내 자신의 말로 문제를 다시 파악하고 설명해보도록 한다. ② 문제에 사용되는 입력값들은 무엇인지 파악한다. ③ 문제의 해답으로 나와야하는 출력값들은 무엇인지 파악한다. ④ 입력값이 출력값을 결정하게 되는지, 문제를 해결할 정보가 충분히 주어졌는지 생각해본다. ⑤ 문제로 제시된 데이터들 중 중요한 부분들이 무엇인지, 어떻게 분류해야 할지, 어떤 이름(용어)을 붙일지 생각해본다. ex) 두 수를 가지고 그들의 총합을 반환하는 함수를 작성하라. ① 내 자.. 2022. 11. 30. [알고리즘 자습] 빅오 표기법(big O notation), 로그(Logarithms) 프로그램의 연산자의 개수로 계산 1. 상수 개의 연산자 : O(1) ... 처리할 자료 개수 n개에 영향받지 않음. ex) 산술 연산자, 변수 할당, 인덱스를 사용한 배열 요소로의 접근이나 키를 이용한 객체 요소로의 접근, 2. 계수 x의 크기에 상관없이 xn 개의 연산자 : O(n) => 빅오 표현식의 단순화 ... ex) 반복문 but 반복문 조건에 따라 다름 ! 3. 계수 x의 크기에 상관없이 x*n*n 개의 연산자 : O(n^2) => 빅오 표현식의 단순화, 최고차항 ... ex) 중첩(nested) 반복문 입력(n)이 커질수록 알고리즘이 얼마나 얼마나 공간을 많이 사용하게 되는지 cf. 보조 공간 복잡도(auxiliary space complexity) : 입력(n)은 제외하고 알고리즘 자체가 .. 2022. 11. 25. 이전 1 다음
