Always Be Wise

그래프(Grpah)란 연결 관계를 저장할 수 있는 자료 구조를 의미한다. 그래프에서 하나의 데이터 단위를 나타내는 객체를 노드라고 한다. 위 그림에서 하나의 유저가 하나의 노드다. 두 노드의 직접적인 연결 관계를 엣지라고 한다. 위 그림에서 흰 선들이 그래프의 엣지에 해당한다. 두 노드 사이에 엣지가 있을 때 두 노드는 인접해 있다고 표현한다. 엣지가 갖는 특성에 따라 그래프의 종류를 세부적으로 구분할 수 있다. 우선, 엣지들이 방향을 가지고 있을 경우 방향 그래프라고 한다. 방향 그래프를 통해 인스타그램의 팔로우 관계처럼 한 유저가 다른 유저를 팔로우하는 일방적인 관계를 나타낼 수 있다. 엣지들의 연결 관계뿐만 아니라 어떤 정보를 나타내는 수치를 갖는 그래프를 가중치 그래프라고 한다. 예를 들어, 인천..

트리(Tree)는 데이터 사이의 계층 관계를 표현하는 비선형 자료구조를 의미한다. 트리는 노드(Node)와 가지(Edge)로 구성된다. 아래 그림에서 A, B, C 등이 노드에 해당하며 해당 노드들을 연결하는 선들이 가지다. 트리의 가장 위쪽에 있는 노드를 루트(Root), 가장 아래쪽에 있는 노드를 리프(Leaf)라고 한다. 리프는 단말 노드(Terminal Node), 외부 노드(External Node)라고도 하며, 물리적으로 가장 아래쪽에 위치한다는 의미가 아니라 해당 노드 아래로 가지가 더 이상 뻗어나갈 수 없다는 의미이다. 리프를 제외한 노드(루프 포함)를 비 단말 노드(Non-Terminal Node), 내부 노드(Internal Node)라고도 한다. 어떤 노드와 노드가 가지로 연결되어 있..

DFS(Depth First Search)는 깊이 우선 탐색, 세로 검색, 수직 검색이라고도 한다. DFS는 트리의 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선하는 알고리즘을 의미한다. 리프에 도달해서 더 이상 검색할 곳이 없으면 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다. 그런데 DFS는 노드를 방문 하는 순서에 따라 3가지 순회 방식을 갖는다. Preorder(전위 순회) [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회 순회 순서 : A -> B ->D -> E -> G -> H ->C -> F -> I Inorder(중위 순회) [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회 순회 순서 : D -> B -> G -> E -> H -> A -> C -> I -> ..

BFS(Breadth First Search)는 너비 우선 검색, 폭 우선 검색, 가로 검색, 수평 검색이라고도 한다. BFS는 트리의 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 그 다음 레벨로 내려가 검색을 이어가는 알고리즘을 의미한다. ▶ 관련 링크

큐는 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로서, 가장 먼저 입력한 데이터를 가장 먼저 출력하는 선입선출(FIFO: First In First Out) 방식을 따른다. 데이터의 입출력이 한쪽 끝에서 이루어지는 스택과 달리 큐는 데이터의 입출력이 양쪽 끝에서 이루어진다. ▶ 관련 링크 2021.11.18 - [알고리즘] - 큐 : 뱀(백준 3190번) 2021.11.18 - [알고리즘] - 큐 : 요세푸스 문제 0(백준 11866번) 2021.11.18 - [알고리즘] - 큐 : 카드2(백준 2164번) 2021.11.18 - [알고리즘] - 큐 : 큐2(백준 18258번)

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로서, 가장 먼저 입력한 데이터를 가장 나중에 출력하는 후입선출(LIFO: Last In First Out) 방식을 따른다. ▶ 관련 링크 2021.11.17 - [알고리즘] - 스택 : 스택(백준 10828번) 2021.11.17 - [알고리즘] - 스택 : 제로(백준 10773번) 2021.11.17 - [알고리즘] - 스택 : 괄호(백준 9012번) 2021.11.17 - [알고리즘] - 스택 : 막대기(백준 17608번) 2021.11.17 - [알고리즘] - 스택 : 탑(백준 2493번) 2021.11.17 - [알고리즘] - 스택 : 원 영역(백준 10000번) 2021.11.17 - [알고리즘] - 스택 : 괄호의 값(백준 2504번)..

분할 정복법은 주어진 문제를 부분 문제로 나누고(Divide), 각각의 부분 문제들을 해결/정복(Conquer)하여 본래의 문제를 해결하는 알고리즘을 의미한다. # 분할정복을 이용하여 1부터 N까지의 합 구하기 def consecutive_sum(start, end) if start == end: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid+1, end) ▶ 관련 링크

이분 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값(X)을 찾는 알고리즘을 의미한다. X를 찾는 과정은 다음과 같다. 우선, 배열의 중간 값을 X와 비교한다. X가 해당 중간 값보다 작으면 탐색의 대상이 되는 배열을 중간 값 기준 좌측의 데이터로, 중간 값보다 크면 우측의 데이터로 조정한다. X를 찾을 때까지 이 과정을 반복한다. 이분 탐색의 시간 복잡도는 O(logN)이다. ### 직접 구현 ### def binary_search(target, A, left, right): if left > right: return False mid = (left + right) // 2 if target == A[mid]: return True elif target < A[mid]: return binary_s..

재귀 호출(Recursive Call)이란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위를 의미한다. ▶ 재귀 호출의 일반적인 형태 # 공통적으로 Base Case를 지정하고, # 조건에 맞는 경우가 아니라면 입력값을 조정하여 다시 함수 호출 # Ex_1 def function(입력값): if 입력값 > 일정값: return function(입력값 - 1) else: return 일정값 # Ex_2 def function(입력값): if 입력