TIL (35) 썸네일형 리스트형 (자료구조) 힙 1. 힙 (Heap) 이란? 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리. 무조건 왼쪽부터. (아래 힙 기본동작 그림 참조) 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 최대 힙과 최소 힙 존재 각 노드의 값은 해당 노드의 자식 노드 값보다 크거나 같다(최대 힙) 완전 이진 트리의 형태를 가짐 3. 힙과 이.. (자료구조) 트리구조 (Tree) 1. 정렬된 배열과 해시 테이블의 단점 - 정렬된 배열은 삽입과 삭제가 느리다. 최악의 시나리오(배열 앞에 값 삽입, 배열 첫번째 값 삭제)의 경우 O(N) 시간복잡도 - 해시 테이블은 순서 유지가 안된다. - 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료구조 -> 이진 트리 - 이진 트리와 정렬된 배열의 탐색 비교 2. 트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용 브랜치가 최대 2개인 트리구조가 이진 트리이다. 3. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 .. exception error handling 1. 기본 exception handling begin x = 1/0 rescue Exception x = 0 puts( $!.class ) puts( $! ) end puts( x ) -------실행결과------- ZeroDivisionError divided by 0 0 $! 는 마지막에 발생한 exception을 뜻한다. 2. exception타입에 따라 다양한 액션을 취할 수 있다. def calc( val1, val2 ) begin result = val1 / val2 rescue TypeError, NoMethodError => e puts( e.class ) puts( e ) puts( "One of the values is not a number!" ) result = nil rescu.. Encapsulation and Information Hiding encapsulation and information hiding class MyClass def initialize return @test = 500 end end ob = MyClass.new p ob.@test # error 위의 코드는 에러가 발생한다. 인스턴스 변수에 직접 접근하려 했기 때문이다. 내부 데이터에 접속하기 위해선 반드시 메소드를 사용해야한다. 이러한 접근방식의 장점 중 하나는 데이터에 대한 통제가 가능하다는 것이다. 예를 들어 보자. class MyClass def initialize(num) return @test = num end def test if @test < 0 val = 0 else val = @test end return val end end num = 500 ob .. (자료구조) 해쉬테이블 1. 해쉬테이블 소개 - 엄청난 룩업 속도를 자랑한다. - 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시맵, 딕셔너리 등이다. - 해쉬테이블의 값 룩업은 평균적으로 O(1)이다. - 원래 해쉬의 뜻은 임의 값을 어떤 고정된 길이의 값으로 변환하는 것을 말한다 - 해쉬함수가 유효하려면 딱 한가지 기준을 충족해야한다. 해쉬 함수는 동일한 문자열을 해쉬 함수에 적용할 때마다 항상 동일한 숫자로 변환해야한다. 2. 해쉬 구조 - Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를.. 알고리즘 복잡도 1. 알고리즘 복잡도 계산이 필요한 이유 - 하나의 문제를 푸는 알고리즘은 무수히 많다. 이를 정량적으로 비교할 수 있어야 어떤 알고리즘이 효율적인지 알 수 있다. 이때 사용하는 것이 바로 알고리즘 복잡도 이다. 2. 알고리즘 복잡도 종류 - 시간복잡도 : 알고리즘 실행 속도, 반복문에 가장 큰 영향을 받는다. - 공간복잡도 : 알고리즘이 사용하는 메모리 용량 - 시간복잡도가 가장 많이 쓰인다. 3. 알고리즘 성능 표기법 - Big 0 표기법: O(N) - 입력 n에 따라 결정되는 시간복잡도 함수 - O(1), O(log n), O(n), O(nlog n), O(n2), O(2n), O(n!)등으로 표기함 - O(1) 반복문이 없는 알고리즘. 아래에서는 n이 100이든, 1000이든 무조건 2회만 실행.. (자료구조) 링크드리스트 (Linked List) 1. 링크드리스트란 - 일반적인 배열이 순차적으로 연결된 공간에 데이터를 나열하는 구조라면, 링크드 리스트(혹은 연결 리스트)는 떨어진 곳에 존재하는 데이터를 포인터로 연결하여 관리하는 데이터 구조이다. - 사용자가 어떤 애플리케이션에서 배열을 사용 중이라면 아마 배열 대신 링크드 리스트를 쓰고 있을 가능성이 크다. 기본구조는 아래와 같다. - Node : 데이터 저장 단위. 실제 데이터값과 포인터로 구성되어있다. 아래 그림 왼쪽이 데이터값, 오른쪽이 포인터이다. - Pointer : 각 노드 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간이다. 아래 그림에서는 다음 노드의 정보만 들어가나 만약 이전, 다음 노드정보가 들어간다면 이를 더블링크드리스트라 부른다. 1. 아래는 파이썬으로 구현한 .. Section2-33~37 Function "A function is a piece of code that we can reuse over and over again in our code" Function declarations vs. expressions // function declarations function calcAge1(birthYear) { return 2021-birthYear; } const age1 = calcAge1(2000); // function expressions const calcAge2 = function(birthYear){ return 2021-birthYear; } const age2 = calcAge2(2000); function expressions부분에서 익명함수 부분은 statement가 아니라 (당연.. Section2-20 Type Conversion and Coercion "type conversion is when we manually convert from one type to another. On the other hand type coercion is when Javscript automatically converts type behind the scenes for us" type conversion 직접 타입을 바꿔주는 것을 뜻한다. const inputYear = '2020'; console.log(inputYear + 10); // 202010 console.log(Number(inputYear) + 10); // 2030 console.log(Number('hoho')); // NaN console.log(typeof NaN); // number 위에서 Nu.. Section2-13 let, const, var let 값이 변경될 가능성이 있는 경우, let을 통해 변수 선언을 한다. 예를 들어 'age'변수의 경우 고정값이 아닌 변동될 가능성이 있으므로 이 경우에는 let으로 선언하는 것이 타당하다. "we use the let keyword to declare variables that can change later so basically during the execution of our program" 변경 가능하므로 아래와 같이 값을 재할당할 수 있다. let age = 30; ... age = 31; 이를 reassigning 혹은 mutate라고 한다. 즉 mutate할 필요가 있는 변수는 let으로 선언한다. "when we need to mutate a variable, that's the per.. 이전 1 2 3 4 다음
