걸음마코딩기

공통된 숫자를 이용하여 가장 큰 수를 만들어주는 문제이다. string solution(string X, string Y) { string answer = ""; vector num(10,0); vector result; for(int i=0; i

🚦 이번 포스팅에서는 〰️ ▶️ 동적 계획법(Dynamic Programming)이란? ▶️ 동적 계획법(Dynamic Programming) 문제 풀어보기 📌 동적 계획법(Dynamic Programming)이란? : 하나의 문제는 단 한번만 풀도록 매번 저장하는 알고리즘 동일한 문제를 요구하는 경우 기존에 이미 저장해 두었던 것을 가져온다. 불필요한 반복 계산을 줄이고 효율적으로 최적해를 찾는다. 계산한 값들은 하나의 보관용 테이블(배열)에 순서대로 저장한다. 분할 정복법과 같이 여러개의 하위 문제들로 나누어 먼저 처리해야 할 때 사용한다. 대표적인 문제 : 피보나치 수열 DP 구현의 두가지 방법 재귀 함수 이용 (Top - Down) : 큰 문제를 쪼개나간다. 재귀 함수를 이용한 피보나치 수열 구현..

🚦 이번 포스팅에서는 〰️ ▶️ Greedy(탐욕) 알고리즘이란? ▶️ Greedy(탐욕) 알고리즘 문제 풀어보기 📌 Greedy(탐욕) 알고리즘이란? : 각 단계에서 가장 최선의 선택을 하는 기법이다. 현재의 선택이 나중에 미칠 영향을 고려하지 않는다. 그렇기 때문에, 그 정당성 분석이 중요하다. ▶️ 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요! 동적(dynamic) 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위한 개념이다. 대표적인 문제로 거스름돈 문제, 활동 선택 문제 등이 있다. 📌 Greedy(탐욕) 알고리즘 문제 풀어보기 1️⃣ 백준 14916 거스름돈 동전의 개수가 최소가 되도록 거슬러줘야 하기 때문에 되도록 큰 단위의 동전을 많이..

🚦 이번 포스팅에서는 〰️ ▶️ DFS(깊이 우선 탐색)이란? ▶️ DFS 구현방법 ▶️ BFS(너비 우선 탐색)이란? ▶️ BFS 구현방법 ▶️ DFS vs BFS 📌 DFS(깊이 우선 탐색) 이란? : Depth First Search의 줄인말로, 그래프를 탐색하는 방법 중 하나이다. 루트 노드 (혹은 다른 임의의 노드)에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법이다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택하며, BFS(너비 우선 탐색)보다 좀 더 간단하다. 단순 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느리다. 전위순회(Pre-Order Traversal)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. DFS는 재..

🚦 이번 포스팅에서는 〰️ ▶️ 그래프(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 형태..

priority queue pair로 구현했다. pair로 구성한 우선순위 큐는 첫번째 원소를 기준으로 정렬하기 때문에, pair의 첫번째 값에는 절댓값을 넣어주고 두번째 값에 원래 값을 넣어줬다. 또한, 내림차순이 기본이기 때문에 오름차순으로 바꿔주었다. #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; priority_queue pq; cin >> N; while(N--) { int x; cin >> x; if(x==0) { if (pq.empty()) cout

🚦 이번 포스팅에서는 〰️ ▶️ 트리(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라고 할 수 있다. 힙은 항상 완전 이진트리의 모습을 지닌다. ✅ 우선순위 큐? 단어 그대로 우선순위가 존재하는 큐이다. 데이터들..

후위 표기식? 제일 뒤에 입력된 것끼리 연산하는 방식으로, 대표적인 스택 문제이다. [ 입력 예시 ] 입력 = ABC*+DE/- 첫번째 연산자 ➡️ 연산자 * ➡️ 스택 상황 A B C 1 2 3 ➡️ 연산 B * C = 2 * 3 = 6 ❗️연산 순서 주의 ❗️ 덧셈,곱셈에서는 문제가 되지 않지만 뺄셈,나눗셈에서는 문제발생한다. 첫번째 pop한 원소를 두번째 연산자로 정하고, 두번째 pop한 원소를 첫번째 연산자로 정해준다. ➡️ 연산 후 스택 상황 A B*C = F 1 6 두번째 연산자 ➡️ 연산자 + ➡️ 스택 상황 : 위 연산 후 스택 상황 ➡️ 연산 A + F = 1 + 6 = 7 ➡️ 연산 후 스택 상황 A + F = G 7 ... 이런식으로 연산을 진행한다. 마지막까지 연산을 진행하면 스택의..