걸음마코딩기

🚦 이번 포스팅에서는 〰️ ▶️ 그래프(Graph)란? ▶️ 그래프(Graph) 의 종류 ▶️ 그래프(Graph) 의 두가지 연산함수-Graph Traversal ▶️ 그래프(Graph) 구현 방법 ▶️ 인접 행렬 vs 인접 리스트 ▶️ 트리(Tree) vs 그래프(Graph) 📎 그래프(Graph)이란? : 노드(node), 또는 버텍스(vertex)와 에지(edge)로 구성되었으며, 어떤 자료들간의 관계(relation)을 설명하는 매우 일반적인 자료구조이다. 그래프를 탐색하는 2가지 알고리즘인 DFS(Depth First Search)와 BFS(Breadth First Search)가 유명하다. 대부분의 그래프 관련 알고리즘은 이 두 알고리즘을 바탕으로 확장된 것이다. 그래프가 중요한 이유? 가장 ..

🚦 이번 포스팅에서는 〰️ ▶️ 맵(Map) 이란? + multimap ▶️ 셋(Set) 이란? ▶️ 맵(Map) vs 셋(Set) 📌 맵(Map) 이란? : 연관 컨테이너로, pair 를 원소로 저장하는 컨테이너이다. key를 기준으로 데이터를 정렬한다. 연관 컨테이너는 원소를 빨리 찾기 위해서 사용한다. (연속 컨테이너인 array, vector, list보다 속도가 빠르다) insert 멤버 함수에 의해 삽입되면, 원소가 자동으로 정렬된다. (default=오름차순) key를 기준으로 정렬된다. ➡️ 내림차순 : map m로 선언 or 데이터에 -붙여 삽입처리 저장공간의 필요에 따라 allocator객체 사용 (동적할당) 🔆 맵(Map)의 구현 및 함수 -C++ STL 구현 : map pair 형태..

🚦 이번 포스팅에서는 〰️ ▶️ 트리(Tree) 란? ▶️ 트리(Tree) 의 종류 - 일반트리, 이진트리, 이진탐색트리, 트라이 ▶️ 트리(Tree) 구현 방법 ▶️ 트리(Tree) vs 그래프(Graph) 📌 트리(Tree) 란? : 그래프의 종류(연결된 graph이며 Cycle이 없다)로, 노드로 이루어진 자료구조이다. STL tree가 존재하나, 활용 상황이 다 달라 사용되기 어렵기 때문에 직접 구현해서 사용한다. 🔆 Tree 종류 (큰 틀) Rooted Tree, Unrooted Tree : root의 존재 여부 Ordered Tree, Unordered Tree : 자손의 순위가 있는지의 여부 Directed Tree, Undirected Tree : 에지 방향이 있는지의 여부 Binary T..

🚦 이번 포스팅에서는 〰️ ▶️ 힙(Heap) 이란? + 우선순위 큐? ▶️ 힙(Heap) 의 종류 ▶️ 힙(Heap) 구현 방법 - 힙의 삭제, 힙의 삽입, 힙의 정렬 📎 힙(Heap)이란? : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬상태(느슨한 정렬 상태)를 유지하는데, 이는 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도를 의미한다. 더 직관적인 말로 설명하자면 부모노드가 자식 노드보다 항상 큰 maximum binary tree라고 할 수 있다. 힙은 항상 완전 이진트리의 모습을 지닌다. ✅ 우선순위 큐? 단어 그대로 우선순위가 존재하는 큐이다. 데이터들..

#include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //1~N 순서대로 카드, 제일 위부터 pop => Queue queue card; int N; cin >> N; for(int i=1; i 1) { //card 한장 남을때까지 반복 card.pop(); int temp = card.front(); card.pop(); card.push(temp); } cout

문제풀이 처음에는 연결리스트 사용해서 circular queue를 사용해야겠다고 생각했다. 하지만 복잡하기 때문에 그냥 단순하게 필요한 순번의 번호가 나올때까지 뽑아서 다시 Queue 뒤에 저장하는 방식으로 야매 circular queue를 구현했다. Queue에 N만큼의 정수를 저장해준다. K-1번째까지의 원소를 pop해서 Queue 뒤에 push해준다. K번째의 원소를 pop해준다. Queue에 원소가 1개 남을때까지 반복해준다. (출력 형식때문에) 마지막원소를 출력해주고 마무리한다. 코드 #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int..

풀이과정 괄호 문제는 스택의 대표적 문제이다. 짝맞추는 문제이므로 '('가 들어왔을때만 스택에 넣어준다. ')'가 들어왔을 때 스택이 비어있다면 잘못된 괄호이므로 "NO"를 출력해주고 아니라면 짝이 맞았으므로 스택을 pop해준다. 문자열 길이만큼 진행한 뒤 스택이 비어있지 않다면 짝이 안맞았음을 의미하므로 "NO"를 출력한다. 스택이 비어있다면 짝이 다 맞았다는 것을 의미하므로 "YES"를 출력한다. #include #include using namespace std; void VPS(string inp) { stack s; for (int i = 0; i < inp.length(); i++) { if (inp[i] == '(') s.push('('); else { if (!s.empty()) s.pop..

🚦 이번 포스팅에서는 〰️ ▶️ 큐(Queue)란? ▶️ 큐(Queue) functions - C++ ▶️ 큐(Queue) 구현 방법 ▶️ 원형 큐(Circular Queue)에 대해서 ▶️ 우선순위 큐(Priority Queue)에 대해서 ▶️ 덱(Deque)에 대해서 ▶️ 큐(Queue) 사용 사례 ▶️ 스택(Stack) vs 리스트(List) vs 큐(Queue) 📎 큐(Queue) 란? 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 이는 나중에 집어넣은 데이터가 먼저 나오는 ..

🚦 이번 포스팅에서는 〰️ ▶️ 스택(Stack)이란? ▶️ 스택(Stack) functions - C++ ▶️ 스택(Stack) 구현 방법 ▶️ 스택(Stack) 사용 사례 ▶️ 스택(Stack) vs 리스트(List) vs 큐(Queue) 📎 스택(Stack)이란? 말 그대로 "쌓아놓은 더미"를 뜻한다. 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이며, 대표적인 예시로 프링글스 통을 생각하면 좋다. 가장 최근에(마지막으로) 들어온 데이터가 가장 먼저 나간다는 의미로, 가장 먼저 들어온 데이터가 먼저 나가는 Queue의 반대개념이다. 📎 스택(Stack) functions - C++ 스택은 LIFO(Last In First Out) 형태로, 가장 ..

시간복잡도-주어진 N대비 소모시간 => weak ordering : 약하게 순서매기기 Shortest path Minimum Spanning Tree Topological Sort and Critical Path(a.k.a 순서) Dynamic Programming : sub-problems로 나눠서 결과취합하여 최종적인 결과도출 -Ex) edit distance(ex.키워드찾아주기) -matrix chain multiplication [Array&Stack&Queue] Linked lists(연결리스트)> -push&pop: 처리가 항상 top에서만 일어남 -Parenthesis(괄호) Matching가능 여는괄호 -> stack push 닫는괄호 -> stack 괄호pop&matching -inser..