분류 전체보기31 [자료구조] AVL Tree(AVL 트리) - CS면접 대비 이번 글에서는 AVL 트리에 관한 내용을 정리해보고자 한다. 이전 글에서 언급했던 것처럼 BST는 공백인 상태에서 이미 정렬된 수를 연속으로 삽입하는 경우 편향(skewed) 문제가 발생한다. 따라서 최악의 경우 자료 탐색에 소요되는 시간이 리스트를 순차 탐색하는 것과 같아진다. 균형 탐색 트리의 일종인 AVL 트리는 이러한 BST의 편향 문제를 해결하기 위해 고안되었으며, 동적 검색을 O(log N) 시간 내에 할 수 있고, 새로운 키를 O(log N) 시간 내에 삽입하거나 삭제할 수 있다. AVL 트리(AVL Tree) [1] AVL 트리의 정의 어떤 이진트리 노드 T의 balance factor(균형인수)를 $BF(t) = h_L - h_R$ 라 할 때, 모든 노드 T에 대해 $BF(t)$= -1,.. 2021. 12. 7. LeetCode 937. Reorder Data in Log Files solution in python - 여러 개의 키로 리스트 정렬하기 리트코드 937번 문제는 주어진 로그를 조건에 맞춰 분류 및 정렬하는 문제이다. https://leetcode.com/problems/reorder-data-in-log-files/ Reorder Data in Log Files - LeetCodeLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.leetcode.com문제풀이1. sorted()파이썬에서는 sort() 혹은 sorted() 메서드를 이용해 리스트를 손쉽게 정렬할 수 있다. 둘의 차이라면 sort()는 정렬할 수 있는 대상이 list에 한정되.. 2021. 12. 7. [자료구조] BST(Binary Search Tree) 이진 탐색 트리 - CS면접 대비 이번 글에서는 탐색, 삽입, 삭제 연산에서 탁월한 성능을 보이는 BST(Binary Search Tree)에 관한 내용을 정리해보고자 한다. 1부터 100까지의 수 중 임의의 수 하나를 맞히는 게임을 한다고 가정해보자. 직관적으로 생각했을 때 가운데 값인 50을 가장 먼저 말하고 맞히려는 수가 그보다 큰 경우 75를 작은 경우 25를 외치는 식으로 답을 찾는 게 가장 효율적인 방법일 것이다. 이진 탐색 트리는 이와 유사한 방식으로 자료 탐색이 가능한 이진 트리 자료구조라고 할 수 있다. 이진 탐색 트리(BST, Binary Search Tree) [1] 이진 탐색 트리(BST)의 정의 이진 탐색 트리(BST)는 이진 트리로서 공백일 수 있으며, 만약 공백이 아니라면 다음 성질을 만족한다. 모든 원소는 키.. 2021. 12. 2. [자료구조] Binary Heap(히프)와 Priority Queue(우선순위 큐) - CS면접 대비 이번 글에서는 우선순위 큐(Priority Queue) 구현을 위해 사용되는 이진 히프(Binary Heap)에 관한 내용을 정리해보고자 한다. 일반적인 배열로 우선순위 큐를 구현하는 경우 삽입에 O(N) 정렬에 O(log N) 시간이 소요되는 반면, 히프로 구현하는 경우 enqueue와 dequeue 연산을 O(log N) 시간에 가능하게 해준다. 이진 히프(Binary Heap) [1] 최대/최소 히프의 정의 최대 히프(max heap)는 최대 트리(max tree)*이면서 완전 이진 트리(complete binary tree)이다. 최소 히프(min heap)는 최소 트리(min tree)*이면서 완전 이진 트리(complete binary tree)이다. * 최대(최소) 트리 : 각 노드의 키 값.. 2021. 11. 30. [자료구조] Binary Tree(이진 트리) - CS면접 대비 이번 글에서는 컴퓨터 프로그래밍에서 자주 사용되는 자료구조 중 하나인 이진 트리에 관한 내용을 정리해보고자 한다. 1. 이진 트리의 정의 및 성질 먼저, 이진 트리(binary tree)는 공백이거나 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리라고 하는 2개의 분리된 이진 트리로 구성된 노드의 유한 집합이다. 이진 트리와 일반적인 트리의 주요한 차이점은 다음과 같다. 일반 트리의 경우 0개의 노드를 가질 수 없으나, 공백 이진 트리는 존재함 일반 트리는 자식의 순서를 구분하지 않으나, 이진 트리는 왼쪽 자식과 오른쪽 자식을 구별함 또한, 이진 트리는 노드의 수와 관련하여 다음과 같은 성질을 갖는다. 레벨 i 에서의 최대 노드 수는 2^(i -1) → 예) 레벨 3에서 최대 노드의 수는 4개 깊이.. 2021. 11. 16. [NLP/Text classification] 데이콘(Dacon) 텍스트 분류 대회 도전기 이번년도를 시작하며 거창하게 Kaggle competition에 참가해 Expert를 달성해보겠다는 목표를 세웠다. 1월 경에 T아카데미에서 이수한 'Kaggle(캐글) 데이터분석 입문' 강의 덕분일거다. 결론부터 말하자면, 이 목표는 지키지도 못했고, 지킬 가능성도 매우 희박해졌다. 돌이켜보면 약 7달 전의 나는 이제 막 인공지능에 관심을 가지기 시작한 상태였고, 막연하게 캐글에서 좋은 성적을 내면 인공지능 전문가가 될 수 있을거라 생각했다. 그러나 막상 대학원에 진학해 인공지능을 공부하리라 마음을 먹고 보니 생각보다 좁은 영역(CV, NLP, Speech 등)에 초점을 맞추고 공부를 해야했고, 그렇게 출퇴근과 함께 Coursera 강의 듣고, 논문 아주 조금씩(초록과 결론정도?ㅎ) 읽다보니 연초에 세.. 2021. 10. 2. 이전 1 2 3 4 5 6 다음 반응형
