dkim's devlog dkim's devlog

학습 키워드: binary tree, binary search tree, heap, binary heap, red-black tree, b+ tree 2024-08-12 면접 카타 질문이진트리, 이진 검색트리, 힙이 각각 무엇인지 설명하고, 차이점을 설명해주세요: 이진 트리(Binary Tree)는 트리 구조에서 한 개의 노드가 항상 두 개 이하의 자식 노드를 가지는 구조를 말합니다. 일반적으로 부모 노드가 자식 노드로의 reference만 가지고 있는 방향성 그래프의 형태지만, 자식 노드가 부모 노드를 저장하는 경우는 무방향 그래프가 될 수도 있습니다.  이진 검색 트리(Binary Search Tree, BST)는 이진 트리 구조에서 모든 노드의 두 개의 자식 노드 중 왼쪽에는 현재 노드보다 작은 값..

학습 키워드: graph, tree 2024-08-07 면접 카타 질문그래프(Graph)와 트리(Tree)를 설명하고, 둘의 차이점을 설명해주세요: 그래프는 정점(vertex) 노드가 간선(edge)으로 연결되어있는 데이터 구조입니다. 간선의 방향 유무에 따라 directed/undirected 그래프로 나뉘고, 간선의 가중치 유무에 따라 weighted/unweighted 그래프로 나뉩니다. 하나의 노드에서 다른 노드까지 가는 길이 하나 이상일 수 있는 순환 구조가 발생하기도 합니다.  트리는 하나의 루트(root) 노드가 여러개의 자식(child) 노드를 가져 마치 나무가 가지를 뻗어나가는 형태를 띄는 일종의 그래프 구조입니다. 각 노드가 한 개의 부모 노드에서 파생되기 때문에 순환 구조가 발생하지 ..

학습 키워드: stack, queue 2024-08-07 면접 카타 질문Stack과 Queue를 비교설명해주세요: Stack은 마지막에 들어온 항목이 먼저 빠져나오는 후입선출(LIFO) 구조이며, 함수의 콜 스택 관리, undo 메커니즘, 백트래킹 알고리즘 등에 사용됩니다. 기본적으로 스택의 가장 위에 있는 항목만 접근이 가능합니다.  Queue는 먼저 들어온 항목이 먼저 나가는 선입선출(FIFO) 구조로, 작업 스케쥴링이나 BFS 알고리즘 구현 등에 사용됩니다. 기본적으로 LinkedList로 구현되며, 맨 앞의 HEAD 노드와 맨 뒤의 TAIL 노드에 접근이 가능합니다.  --

학습 키워드: selection sort, bubble sort, merge sort, insertion sort, quick sort, heap sort 2024-08-01 면접 카타 질문다음의 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해주세요:1. 선택 정렬(Selection Sort): 배열의 정렬되지 않은 부분에서 가장 낮은 값을 가진 항목을 선택하여 정렬된 부분으로 하나씩 옮겨나가는 방식입니다. O(n^2)의 시간 복잡도를 가지며 O(1)의 보조 공간을 사용합니다. 보조 공간 BigO에서 알 수 있듯이 추가적인 메모리 사용이 적다는 장점이 있으나, O(n^2)의 시간복잡도로 인해 규모가 큰 데이터 셋에 사용하기는 적합하지 않습니다.// Javavoid selectionSort..

학습 키워드: Array, LinkedList, fixed size, dynamic size, memory allocation, node, pointer, reference 2024-07-25 면접 카타 질문Array과 LinkedList를 비교설명해주세요: 일반적으로 Array는 고정된 크기를 가지며 메모리에 저장될 때 배열의 모든 항목이 연속된 공간에 할당되기 때문에 메모리 접근 효율이 좋습니다. Array의 각 항목을 access할 때 항목의 index를 알면 O(1)의 시간 복잡도로 접근이 가능하다는 특징이 있습니다. JS에서는 Array가 가변크기를 가지기 때문에 처음 언급한 연속된 메모리 공간이라는 특징이 유효하지 않습니다. LinkedList의 경우 Node와 Pointer를 기반으로 하는 ..

학습 키워드: DFS, BFS 2024-08-01 면접 카타 질문DFS와 BFS의 차이를 말해주세요: 트리나 그래프 구조의 데이터에서 루트 노드부터 한 방향으로 깊이 우선 탐색하고, 원하는 결과를 찾지 못했다면 상위 노드로 돌아가 방문하지 않은 다른 갈림길에 있는 노드를 탐색하는 방식을 DFS라고 부릅니다. DFS는 스택이나 재귀 함수로 구현되며, 깊이 우선으로 방문한다는 특징으로 인해 최초 방문한 노드까지의 경로가 최단거리가 아닐 수 있습니다.  BFS는 루트 노드에서 시작하여 같은 depth의 인접 노드 전체를 훑고 그 다음 depth를 훑는 방식입니다. BFS는 queue를 사용하여 구현되며, 가장 가까운 노드부터 탐색한다는 특징으로 인해 최초 방문한 노드까지의 경로가 항상 최단거리가 됩니다. 그렇..