DATA STRUCTURE/ALGORITHM
1.1장 자료구조/알고리즘[PYTHON]
목차 **1. 자료구조란? 알고리즘이란? 그림으로 이해하기 느낀점** > ### 자료구조란? 자료구조는 컴퓨터 과학에서 데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇이다. 코딩 문제를 풀 때 알고리즘 선택에 따라 어떤 자료구조를 사용할 것인지 판단해야 할 경우가 많다. 정말 많은 자료구조가 존재한다. 자료구조 종류 리스트(배열) 덱 힙 **. ...
2.2장 구간 합(Prefix Sum)[PYTHON]
**목차 구간 합 그림으로 이해 코드 느낀점** > ### 구간 합 구간 합 자체의 개념은 어렵지 않다. 이름 그대로 일정 구간의 합을 나타내는 말이다. 구간 합을 구하고자 하는 데이터를 받았을 때 각 원소를 일일이 합하면 시간 복잡도는 O(N^2)으로 비효율적이다. 하지만 합 배열을 이용하여 구간 합을 다시 구하고자 한다면 시간 복잡도는 O(1)이 된...
3.3장 투 포인터(Two Pointer)[PYTHON]
**목차 투 포인터 그림으로 이해 코드 느낀점** > ### 투 포인터 투 포인터는 간단한 알고리즘 기법 중 하나이다. 투 포인터는 두개의 포인트 지점을 지정한 후 조건에 맞게 유동적으로 움직일 수 있다는 특징이 있다. 말로 설명하기 보다 그림으로 바로 이해해도 무관하기 때문에 바로 그림과 예시 문제로 이해해 보자. > ### 그림으로 이해 문제를 ...
4.4장 슬라이딩 윈도우(Sliding Window)[PYTHON]
**목차 슬라이딩 윈도우 그림으로 이해 코드 느낀점** > ### 슬라이딩 윈도우 슬라이딩 윈도우는 투 포인터 개념과 매우 유사하다. 차이가 있다면 투 포인터는 그 길이가 유동적이지만 슬라이딩 윈도우는 유동적이지 않다는 차이가 있다. 말 그대로 윈도우의 크기를 지정해두고 그 윈도우 자체를 슬라이딩 한다는 개념이다. 투 포인터를 안다면 바로 그림으로 이해...
5.5장 스택/큐(Stack/Queue)[PYTHON]
**목차 스택 스택 그림으로 이해 큐 큐 그림으로 이해 느낀점** **알고리즘 공부를 하다보면 "스택을 이용해서 ..."이런 부분을 많이 듣게 된다. 앞으로 알고리즘 공부할 때 필요한 핵심적인 자료구조라고 생각한다. 스택과 큐의 개념은 그렇게 어렵지 않으니 그렇게 긴 포스팅이 될것 같지는 않다.** > ### 스택 스택은 자료구조의 일종으로 LIFO(...
6.6장 버블 정렬/선택 정렬(Bubble/Selection sort)[PYTHON]
**목차 버블 정렬 버블 정렬 그림으로 이해 선택 정렬 선택 정렬 그림으로 이해 코드 느낀점** **정렬에는 다양한 종류가 있다. 그중에서도 이번 장에서는 상대적으로 익히기 쉬운 버블 정렬과 선택 정렬에 대해서 공부해보자.** > ### 버블 정렬 버블 정렬은 데이터의 인접한 요소끼리 비교를 한 후 swap하여 정렬하는 알고리즘이다. 버블 정렬의 시간...
7.7장 삽입 정렬(Insertion Sort)[PYTHON]
**목차 삽입 정렬 그림으로 이해 코드 느낀점** > ### 삽입 정렬 삽입 정렬은 이미 정렬된 데이터에 선택된 데이터를 적절한 위치에 삽입하는 정렬이다. 삽입 정렬의 시간 복잡도는 O(n^2)이다. > ### 그림으로 이해 아래와 같은 데이터가 저장된 리스트가 있다고 하자. 우리는 이 데이터를 삽입 정렬을 이용하여 정렬하고자 한다. 우리는 오름차순...
8.8장 퀵 정렬(Quick Sort)[PYTHON]
**수를 정렬하는 방법에는 다양한 방법이 있다. 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬.... 등등 종류가 많고 어떤 방식을 사용하냐에 따라 시간복잡도 또한 달라지게 된다. 이번 시간에는 정렬중에서도 퀵 정렬에 대해 알아보도록 하겠다.** > 퀵 정렬? **퀵 정렬은 기준값을 정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정...
9.9장 병합 정렬(Merge Sort)[PYTHON]
**목차 병합 정렬 그림으로 이해 코드 느낀점** > ### 병합 정렬 병합 정렬은 분할 정복 기법을 사용한 정렬 알고리즘이다. 리스트를 1개의 리스트가 될 때까지 분할하는 과정과 병합하는 과정으로 이루어진다. 시간 복잡도는 O(nlogn)으로 다른 정렬에 비해 효율성이 좋다. > ### 그림으로 이해 아래와 같은 데이터가 담긴 리스트가 있다고 가정...
10.10장 깊이 우선 탐색(DFS)[PYTHON]
**목차 DFS 그림으로 이해 코드 느낀점** > ### DFS 이번에는 DFS에 대해서 알아보자. **DFS는 그래프 완전 탐색 기법중 하나이다. 기본적으로 그래프에서 시작노드부터 탐색할 부분을 정하여 먼저 끝까지 탐색을 한다.** DFS알고리즘 이용시 recursion error가 자주 뜨기도 한다. 이런 경우 보통 BFS를 이용하거나 메모이제이션 ...
11.11장 너비 우선 탐색(BFS)[PYTHON]
**목차 BFS 그림으로 이해 코드 4 느낀점** > ### BFS **BFS는 그래프를 완전 탐색하는 방법 중 하나이다. 출발 노드에서 시작해 가까운 노드를 먼저 다 방문하는 것이 DFS와의 차이점이다.** DFS에서는 재귀함수를 이용하는 반면 BFS에서는 큐 자료구조를 이용한다. 파이썬에서는 큐를 덱을 이용하여 구현한다. > ### 그림으로 이해 ...
12.12장 그리디(Greedy)[PYTHON]
**목차 그리디 알고리즘 문제 풀이 느낀점** > ### 그리디 알고리즘 **그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 다른 알고리즘에 비해 상대적으로 구현하기 쉽지만 항상 해를 구할 수 있는 것은 아니다. 따라서 문제를 보고 그리디 알고리즘을 적용할 수 있는 문제인가 판단하는 능력이 필요하다.** > ...
13.13장 트리(Tree)[PYTHON]
**이번 장에서는 트리가 무엇인지 알아보도록 하자. 트리는 그래프 개념을 이해한다면 그리 어렵지 않은 개념이다. 트리의 특징은 다음과 같다.** 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 1개의 부모 노드를 가진다. 트리의 부분 트리도 트리이다. 그림으로 이해하면 다음과 같다. 트리의 구성 요소에 대해 더 ...
14.14장 트라이(Trie)[PYTHON]
**목차 트라이 그림으로 이해 코드 구현 느낀점** > ### 트라이 트라이 자료구조는 문자열을 빠르고 쉽게 탐색하고 검색할 수 있게 해주는 자료구조이다. 입력되는 문자열을 트리 형태로 입력받아 저장한 후 탐색할 때 트리의 특징을 이용하여 탐색한다. 트라이 자료구조를 이용하면 길이가 M인 문자열이 들어왔을 때 검색하는 시간 복잡도는 O(M)으로 효율적이...
15.15장 이진 트리(Binary Tree)[PYTHON]
**목차 이진 트리 느낀점 참고자료** > ### 이진 트리 이진트리는 트리의 한 종류이다. 트리중에서도 각 노드의 자식 노드가 최대 2개인 경우를 '이진 트리'라고 한다. 트리 영역에서 가장 많이 사용되는 형태라고 한다. 이진 트리의 종류에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 존재한다. 편향 이진 트리 : 노드가 한쪽 방향으로 ...
16.16장 세그먼트 트리(Segment Tree)[PYTHON]
**목차 세그먼트 트리 느낀점 참고자료** > ### 세그먼트 트리 세그먼트 트리는 자료구조의 일종으로 구간 합, 구간 최대, 구간 최소, 구간 곱 과 같은 문제를 빠르게 풀 수 있도록 해준다. 이름에서도 알 수 있듯이 트리의 한 종류이다. 세그먼트 트리는 완전이진 트리로 구현할 수 있다. 구현 단계는 다음과 같이 나눌 수 있다. 초반 트리 만들기(트...
17.17장 최소 공통 조상(LCA)[PYTHON]
**목차 LCA 느낀점 참고자료** > ### LCA LCA라고도 불리는 최소 공통 조상은 트리의 두 노드가 자신을 포함하는 조상중 가장 가까운 공통 조상을 찾는 알고리즘이다. 예를 들어 아래와 같은 구조의 트리가 존재한다고 할 때 노드 5와 4의 LCA는 2이며 노드 5와 6의 LCA는 1이다. 간단하게 그림으로 그려보면 다음과 같다. **