지식을 남기고 쌓는 곳

📚 DP(동적계획법)란? 큰 문제를 작은 문제로 나누어 푸는 것인데 이때 하나의 문제는 한 번만 풀어야 합니다. 동적 계획법에 대해 설명하기 딱 좋은 예시가 있는데 그것은 피보나치수열입니다. 📚 피보나치 수열이란? 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. ❓ 그러면 피보나치수열의 몇 번째 항을 바로 알 수 있는 코드를 짜려면 어떻게 해야 할까요? 피보나치의 규칙을 살펴보면 된다. 첫 번째와 두 번째는 무조건 1이고 다음 항부터는 Fibo(n) = Fibo(n - 1) + Fibo(n - 2) 이 반복된다. 우리는 이것을 재귀 함수로 쉽게 구현할..

📚 BFS (Breadth-First Search) 란? 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 넓이 우선 검색을 적용한다. DFS는 인접한 한 노드를 끝까지 탐색했다면 BFS는 인접한 모든 정점을 방문합니다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모드 노드들을 저장하고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다. 처음에 넣은 노드이므로 큐를 이용해서 BFS를 구현할 수 있다. 📋 BFS 전체 과정 BFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 루트 노드를 큐에 넣는다 2. 현재 큐의 노드를 빼서 visited에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않..

📚 DFS란(Depth First Search)? DFS는 자료의 검색 트리나 그래프를 탐색하는 방법 중 하나이다. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS는 이름에 나와있는 그대로 끝까지 탐색하는 거에 초점을 맞춥니다. 그래서 그래프의 최대 깊이만큼의 공간을 요구하며, 이는 공간을 적게 쓰는 것입니다. 그러나 최단 경로를 탐색하기는 쉽지 않다. 모든 경로를 탐색하는 것이 아니기 때문입니다. 📋 DFS 전체 과정 DFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 3. 만약 끝에 도달했다면 리턴한..

📚 그래프 정의 그래프는 연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 비선형 자료구조이며, 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조이다. 그래프는 TCP 라우팅 알고리즘과 페이스북 관계망 등에서 자주 쓰이는 자료구조이다. 🧬 그래프 구조 노드(Node) : 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertex)라고도 한다. 간선(Edge) : 노드 간의 관계를 표시한 선 인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점) 📝 그래프 표현 방법 그래프를 코드로 표현하는 방법은 LinkedList와 Array가 있는데 ☝ LinkedList는 각 정점간의 관계를 노드로 연결하여 표현한다. head를 3으로 가리..

📚 힙 정의 힙은 데이터에서 최댓값과 최솟값을 찾기 위해 고안된 완전 이진 트리이다. 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다. 그러면 가장 큰 값이 모든 자식보다 크기 때문에 가장 위로 간다. 바로 루트 노드로 말이다. 이렇게 아래로 갈수록 작고 위로 갈수록 커지는 힙은 Max Heap이라 하고 이와 반대인 경우는 Min Heap이라 한다. 그런데 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 하는 규칙이 있다. 🤔 그러면 힙에 새로운 노드를 삽입하거나 이미 존재하는 노드를 삭제할 때 규칙을 어기지 않게 하려면 어떻게 해야 할까? 지금부터 노드 삽입과 노드 삭제 과정을 훑어보자 ..

📚 트리의 정의 트리는 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 트리는 대표적인 사용 예시는 컴퓨터의 폴더 구조이다. 파일이 어느 경로에 있는지 그 경로에는 어떤 폴더들이 포함되는지 나타내야 하기 때문이다. 트리의 구조는 다음과 같다 🧬 트리의 구조 Node : 트리에서 데이터를 저장하는 기본 요소 Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 상위 레벨에 연결된 노드 Child Node : 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node(Terminal Node) : Child Node가 하나도 없는 노드 S..

자료구조 중에서 자주 쓰이는 Array와 LInkedList를 서로 비교하겠다. 언어는 Python 기준으로 하겠다. (선언할 때 배열 크기를 정해야 하는 c++, 자바의 정적 배열과는 달리 Python의 배열은 동적 배열이다.) 다음 간단한 배열의 예를 들어보자 배열은 index와 데이터로 이루어져있다. index는 0으로부터 시작되어 데이터의 순서를 매기며 데이터는 int형부터 시작되어 그 어떤 데이터 타입도 들어갈 수 있다. 여기서 배열의 어떤 하나의 데이터에 접근하는데 걸리는 시간은 얼마나 소요될까? 정확히 말하자면 시간복잡도 O는 얼마일까? 답은 O(1)이다. 내가 접근하고 싶은 데이터가 배열의 맨 앞에 있는 뒤에 있든 중간에 있는 ary[0], ary[2], ary[4] 이런 식으로 단 한 번..

문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어..

1. 시간복잡도 더보기 시간 복잡도는 입력값에 따라 문제를 해결하는데 걸리는 시간과의 상관관계를 말합니다. 똑같은 알고리즘에 입력값이 몇 배로 늘어남에 따라 문제를 해결하는 데 걸리는 시간은 몇 배만큼 늘어나는지 보는 것이다. 우리는 똑같은 입력값이라도 당연히 더 빠른 시간 안에 입력을 처리하는 알고리즘을 선호한다. 즉 걸리는 시간이 줄어들수록 시간 복잡도는 작아지며, 시간 복잡도가 작은 알고리즘이 좋은 알고리즘이다. 시간 복잡도에 대해서 설명하기 위해 똑같은 목적을 가진 두 개의 알고리즘을 살펴보겠다. 두 개의 알고리즘의 목표는 배열 안에 숫자 중 가장 큰 최댓값을 찾는 로직이다. array = [1,3,6,5,4,2] def findMaxValue(array): max_num = array[0] fo..

GD프로젝트 알고리즘 수업 4주 차가 시작되었다. 그럼 4주 차에 배운 내용과 풀었던 알고리즘 문제에 대해 설명하겠다. 목차 1. 새롭게 배운 내용(트리, 힙, 그래프, DFS, BFS, Dynamic Programming) 2. CGV 극장 좌석 자리 구하기 문제 1. 새롭게 배운 내용 1 - 0 선형, 비선형 더보기 선형 자료구조의 대표적인 예시인 스택과 큐이다. 선형구조는 처음과 끝이 확연히 정해져 있다. 그래서 자료를 저장하고 꺼내고 탐색하는 것에 초점이 맞추어져 있다. 즉 내가 사용해야할 자료구조가 조회, 삽입, 삭제가 얼마나 빈번하냐에 따라 선택해야 한다. 비선형 자료구조의 대표적인 예시인 트리와 그래프이다. 비선형 구조는 처음과 끝이 정해져 있지 않으며 때로는 순환적이기도 하다. 비선형 자료..