Topic/Data Structure
-
알고리즘 수학, 순열과 조합, GCD / LCM, 멱집합, 정규표현식Topic/Data Structure 2022. 1. 19. 21:33
순열과 조합 ✔️ 순열 ☑️ 순서를 생각하며 결과를 만드는 경우의 수 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60 일반식: nPr = n! / (n - r)! 조합 ☑️ 순서를 고려하지 않고 결과를 만드는 경우의 수 순열로 경우의 수를 만든 경우에서 중복된 경우를 나누어주면 조합을 얻을 수 있다. 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10 일반식: nCr = n! / (r! * (n - r)!) GCD / LCM ✔️ GCD ☑️ 최대 공약수: 둘 이상의 공약수 중에서 최대인 수 문제: Mask States 방역용 마스크를 제작/판매하는 Mask Man 사는 이례적인..
-
-
자료구조 ( Tree, Graph, BST, BFS, DFS )Topic/Data Structure 2021. 12. 17. 22:19
Tree Traversal 전위 순회 가장 먼저 루트를 방문하고, 루트에서 시작해 왼쪽 노드부터 먼저 둘러본 뒤, 왼쪽 노드 탐색이 끝나면 오른쪽 노드를 탐색한다. 중위 순회 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작해 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색합니다. 후위 순회 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작해 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문합니다. BFS / DFS 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이다. BFS: Breadth-First Search, 너..
-
알고리즘, 자료구조, stack, queueTopic/Data Structure 2021. 12. 17. 09:08
자료구조 기초 자료구조: 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것. 대표적인 자료구조 네 가지 Stack, Queue, Tree, Graph 자료구조는 어떤 특정 상황에 놓인 문제를 해결하는데 특화되어있다. 많은 자료구조를 알아두면, 어떤 상황이 닥쳤을 때 적합한 자료구조를 바로 적용하여 해결할 수 있다. Stack (스택) 데이터(data)를 순서대로 쌓는 자료구조다. 금은동 메달을 각각 책상에 쌓는다고 생각해보자 첫번째로 금, 다음은 은,동 순서로 쌓고, 우리가 다시 그 메달을 집을 때 어떤 메달부터 잡아야 할까? 동메달부터 잡고, 은메달, 마지막으로 금메달을 잡을 수 있다. 이러한 방식처럼 가장 먼저 쌓은 메달은 가장 나중에 잡을 수 있는 경우가 스택이다. 스택의 특징은 입력과 출..