mei 기술 블로그

1. DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 동작 예시 [Step 0] 그래프를 준비한다. (방문 기준: 번호가 낮은 인접 노드부터) 시작 노드: 1 [Step 1] 시작 노드인 ‘1’을 스택에 삽입하고 방문 처리한다. [Step 2] 스택의 ..

1. 정렬 알고리즘 비교 대부분의 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장 단, 퀵 정렬은 최악의 상황의 시간 복잡도 = O(N^2) 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때 가장 빠름 퀵 정렬 O(NlogN) O(N) 대부분의 경우 가장 적합하고 빠름 계수 정렬 O(N+K) O(N+K) 데이터의 크기가 한정되어 있는 경우에만 사용 가능하지만 매우 빠름

빠른 정렬 알고리즘 1. 퀵 정렬 일반적으로 데이터 특성과 관련 없이 표준적으로 사용할 수 있는 정렬 알고리즘 중 하나 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 동작 예시 [Step 0] 현재 피벗의 값은 ‘5’이다. 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’이 선택되고 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다. [Step 1] 현재 피벗의 값은 ‘5’이다. 왼쪽에..

1. 정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용 2. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 동작 예시 [Step 0] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 7과 위치 변경 [Step 1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 가장 앞의 5와 위치 변경 [Step 2] 처리되지 않은 데이터 중 가장 작은 ‘2’을 선택해 가장 앞의 9와 위치 변경 [Step 3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 가장 앞의 7와 위치 변경 이러한 과정 반복 매번 가장 작은 데이터를 찾기..

1. 바이너리 인덱스 트리 (Binary Indexed Tree) 2진법 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해줄 수 있는 자료구조 펜윅 트리(fenwick tree) 라고도 함 정수에 따른 2진수 표기 정수 2진수 표기 7 00000000 00000000 00000000 00000111 -7 11111111 11111111 11111111 11111001 0이 아닌 마지막 비트를 찾는 방법 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K & -K 계산 K & -K 계산 결과 예시 정수 K 2진수 표기 K & -K 0 00000000 00000000 00000000 00000000 0 1 00000000 00000000 00000000 00000001 1 2 00000000 ..

1. 트리 (Tree) 계층적인 구조를 표현할 때 사용하는 자료구조 관련 용어 루트 노드 (root node) 부모가 없는 최상위 노드 단말 노드 (leaf node) 자식이 없는 노드 크기 (size) 트리에 포함된 모든 노드의 개수 깊이 (depth) 루트 노드부터의 거리 높이 (height) 깊이 중 최댓값 차수 (degree) 각 노드의 (자식 방향) 간선 개수 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개 2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조 특징 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 부모 노드보다 왼쪽 자식 노드가 작음 부모 노드보다 오른쪽 자식 노드가 큼 예시 이진 탐색..

1. 우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 데이터를 우선순위에 따라 처리하고 싶을 때 사용 구현 방법 단순 리스트 이용 힙(Heap) 이용 시간 복잡도 비교 구현 방법 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 힙(Heap) 정렬 단순히 N개의 데이터를 힙(Heap)에 넣었다가 모두 꺼내는 작업 시간 복잡도: O(NlogN) 2. 힙(Heap) 완전 이진 트리(Complete Binary Tree) 자료구조 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree) 항상 루트 노드(root node) 제거 최소 힙(min heap) 루..

1. 스택(Stack) 선입후출(FILO) 자료구조 먼저 들어온 데이터가 나중에 나가는 형식 구현 방법 Python: append(), pop() 메소드 사용 stack = [] stack.append(1) # 삽입 stack.append(2) # 삽입 stack.append(3) # 삽입 stack.append(4) # 삽입 stack.pop() # 삭제 print(stack[::-1]) # 최상단 원소부터 출력, [3, 2, 1] print(stack) # 최하단 원소부터 출력, [1, 2, 3]​ C++: stack 라이브러리 사용 (push() / pop() / top()) #include using namespace std; stack stack; int main(void) { stack.pus..

채팅방 구현할 때 채팅 내용이 많이 쌓여 일정 크기를 넘어가면 스크롤을 적용할 필요가 있다. 이때, 새로고침하면 가장 최근 메시지를 보여줘야 하므로 스크롤의 가장 하단으로 이동해야 한다. scrollTop 함수를 사용하여 이동 가능하다. $('#allMsgList').scrollTop($('#allMsgList')[0].scrollHeight);

1. pull 2. merge 방법 1 - 바로 merge 방법 2 - History에서 merge할 원격 Repository와 메시지 선택 3. 특정 커밋한 내용만 pull하고 싶으면 해당 메시지 선택하고 Cherry-Pick 선택 4. main 내용 로컬로 가져온거 확인