DOing

💡 Stack(스택) : 스택은 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조이다. : LIFO(Last In, First Out) 구조이다. 💡 스택의 특징 [ 장점 ] : 구조가 단순해서 구현이 쉽다. : 데이터 저장/읽기 속도가 빠르다. [ 단점 ] 1) 데이터 최대 갯수를 미리 정해야한다. -> 데이터를 무한정으로 쌓을 수는 없다. 쌓기위해서는 미리 최대 공간을 확보해야한다. -> 파이썬의 경우 재귀함수는 1000번까지만 허용한다. 1000개만큼의 공간 확보했단 소리기도 하다. 2) 저장 공간의 낭비가 발생할 수 있다. -> 최대 갯수를 미리 정해야하기때문이다. [ 스택 활용 ] : 프로세스 실행 구조 더보기 프로그램이 실행되는 상태를 프로세스라고 하는데 프로세스안에서 함수가 호출되는 형태다...

💡 이진 탐색 트리(Binary Search Tree) : 이진트리에 다음과 같은 추가적인 조건이 있는 트리 1) 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰값을 가진다. 2) 모든 노드는 오른쪽 가지에 포함되는 어떤 숫자보다도 작은값을 가진다. 해당 그림에서 볼 때 14를 예시로 들어보자. 1) 14는 왼쪽가지에 포함되는 11보다 큰값을 가진다. 2) 14는 오른쪽가지에 포함되는 15,18,19보다 작은값을 가진다. 💡 이진 탐색 트리 삽입, 탐색 동작과정 [ 탐색과정 ] 1. 찾는 숫자가 현재 노드 값과 같다면 탐색 성공! 2. 찾는 숫자가 현재 노드 값보다 작다면 왼쪽으로 간다. 3. 찾는 숫자가 현재 노드 값보다 크다면 오른쪽으로 간다. [ 삽입과정 ] 1. 삽입할 숫자가 현재 노드 값보..

💡 그래프 : 그래프는 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조이다. : 비선형구조로써, 연결 관계 표현에 초점이 맞춰져 있다. [ 선형구조 vs 비선형 구조 ] 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열되어있는 형태이다. 비선형 구조란 데이터가 계층적 혹은 망으로 구성되어있는 형태이다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 비선형구조에는 그래프, 트리가 있고 선형구조에는 스택, 큐가 있다. 💡 그래프의 용어 - 노드(Node) : 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertex)이라고도 한다. - 간선(Edge) : 노드 간의 관계를 표시한 선. - 인접 노드(Adjacent Node) :..

💡 Disjoint Sets(서로소 집합)? 서로소 집합이란, 공통 원소가 없는 두집합을 의미한다. 왼쪽 그림에서 집합 A와 B는 서로소 관계이고, 오른쪽 그림에서 집합 A와 B는 서로소 관계가 아니다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 union-find 자료구조라고도 불린다. 사용되는 연산의 이름 자체가 union과 find이기도 하고, 두 집합이 서로소 관계인지 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말과 같기 때문이다. 💡 Disjoint Sets 동작 과정 Disjoint Sets 를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. 트리로 부분집합을 ..

💡 최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길찾기'문제라고도 불린다. 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지이다. 이 중 플로이드 워셜 알고리즘을 이번 포스팅에서 다뤄보려고 한다. 💡 플로이드 워셜 알고리즘 다익스트라 알고리즘은 '한 지점'에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘이였다. 플로이드 워셜 알고리즘은 '모든 노드'에서 다른 모든 노드까지의 최단경로를 모두 계산하는 알고리즘이다. 플로이드 워셜 알고리즘은 노드의 개수가 N이라고 할때 N번만큼의 단계를 반복하며 '점화식'에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다. 구현 난이도가 다익스트라..

💡 최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길찾기'문제라고도 불린다. 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지이다. 이 중 다익스트라 최단 경로 알고리즘을 이번 포스팅에서 다뤄보려고 한다. 💡 다익스트라 최단 경로 알고리즘 하나의 출발 노드로 부터 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 단, '음의 간선'이 없을 때만 정상적으로 동작한다. 다익스트라가 연구한 알고리즘 중 가장 대표적인 알고리즘이기 때문에 간단하게 다익스트라 알고리즘이라고도 불린다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 가장 비용이 가장 적은 노드를 선택하는 과정을 반복하기 때문이다...

💡 다이나믹 프로그래밍 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법이다. 큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 푸는 '분할 정복' 알고리즘이 있다. 이때 동일한 작은 문제들이 반복적으로 계산되는 경우가 생길 수 있다. 그 문제를 매번 재계산 하지 않고 값을 저장했다가 재사용하는 기법이 바로 다이나믹 프로그래밍이다. 메모리 공간을 약간 더 사용하여 시간을 획기적으로 줄일 수 있는 방법이다. 여담이지만 다이나믹 프로그래밍의 Dynamic은 동적 할당(Dynamic Allocation)의 Dynamic과 아무런 관계가 없다. 동적할당에서 Dynamic은 '프로그램이 실행되는 도중'에라는 의미이지만 다이나믹 프로그래밍에서 Dynamic은 고안자인 벨만(Richar..

💡 이진 탐색 알고리즘 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 단, 데이터가 정렬되어 있어야지만 사용할 수 있다. 순차탐색의 시간 복잡도는 O(N)이지만 이진탐색의 시간복잡도는 O(logN)으로 빠르게 탐색이 가능하다. 만약 데이터의 탐색 범위가 2,000만이 넘어가면 이진탐색으로 문제에 접근해보는 것이 좋다. 💡 이진 탐색 동작과정 1. 시작점과 끝점 사이의 중간점을 지정한다. 중간점이 실수라면 소수점 이하는 버린다. 2. 중간점과 찾으려는 데이터를 비교한다. 3. 찾으려는 데이터가 중간점보다 크다면 시작점을 중간점 이후로 변경한다. 4. 찾으려는 데이터가 중간점보다 작다면 끝점을 중간점 이후로 변경한다. 5. 찾으려는 데이터가 중간점과 일치할때까지 1~4과정을 반복한다. 찾으려는 ..