걸음마코딩기

백준을 풀다가 위상정렬 문제가 나와서 간단하게 정리를 해봤다. 📌 위상정렬(Topology Sort)이란? '순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 그 순서를 결정해주기 위한 알고리즘. ✅ 작업의 순서가 정해져 있을 때, 작업을 정확하게 정렬해주는 알고리즘이다. ✅ 경로에 따라 여러개의 답이 존재할 수 있다. ✅ 사이클이 없는 방향그래프인 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 🔆 결과값으로 1️⃣ 현재 그래프가 위상정렬이 가능한지, 2️⃣ 정렬이 가능하다면 그 결과는 무엇인지를 알 수 있다. ✔️ 위상정렬 구현 방법 위상정렬을 구현하는 방법으로는 두가지가 있는데, 1. Stack으로 구현 2. Queue로 구현 대부분 큐로 구현하는 것 같아, 여기서는 큐로..

대표적인 dp문제이다. 하지만, 나는.. 바보같이 처음에 map써봤다가 당차게 틀려먹었다.. (대체 왜이러니..) map쓰면 문자열을 계속 순회해야해서 시간복잡도에서 걸린다. 그리고 이건 대표적인 dp라서 그냥 내가 바보였던것으로.. 넘어갑시다. 아무튼, dp를 이용해서 각 부분 문자열에 대한 LCS 값을 구해나가면 된다! 여기서 dp의 경우의 수는 두가지인데, i번째 문자열 == j번째 문자열 이건 왼쪽 위 대각선 값에 +1 해주면된다. 왼쪽 위 대각선 값이 이전 문자열인 (i-1,j-1)의 LCS 값이기 때문! i번째 문자열 != j번째 문자열 이건 왼쪽과 위 중 max값을 가져가면 된다. #include #include using namespace std; int main(void) { ios::s..

와.. 이름만 보고 풀기로 마음먹었는데 예상외로 비트연산을 이용해야하는 문제라 애 좀 먹었다.. (다 까먹어서.. 멍충) 그냥 배열로 순회하면서 구현했을때는 시간초과가 나서, 기억 저편에 있던 비트연산을 다시 공부하며 풀었다. (참고) - https://velog.io/@surpiz/C15787%EB%B2%88-%EA%B8%B0%EC%B0%A8%EA%B0%80-%EC%96%B4%EB%91%A0%EC%9D%84-%ED%97%A4%EC%B9%98%EA%B3%A0 챗지피티한테 이것저것 물어보면서 이해했는데 이 똥멍청이가 자꾸 자기가 한말을 번복해서 이해하는데 엄청 오래 걸렸다.. (사실 내가 똥멍청이) 아무튼.. 코드를 작성하며 이해가 잘 안간 비트 연산들을 필기해놓은 것들을 같이 첨부한다. 부디 나처럼 헤매..

트리와 3가지 순회를 구현해보는 문제이다. 사실 처음엔 vector를 이용해서 구현해보려고 했는데, (멍청) 생각해보니 노드를 찾으려면 모든 vector를 순회해야 하므로 복잡도가 엄청 들게 생겼다.. 그래서, unordered_map을 이용하기로 했다. hash특성상 키에 접근하는 시간이 O(1) 상수시간이므로 빠르게 접근이 가능하다. 다만, 정렬은 필요없으므로 unordered를 사용했다. #include #include #include using namespace std; unordered_map tree; //root-left-right void preOrder(const string& node) { //node가 .이면 자식이 없으므로 return if(node == ".") return; c..

🚦 이번 포스팅에서는 〰️ ▶️ 분할 정복(Divide&Conquer) 알고리즘이란? ▶️ 분할 정복(Divide&Conquer) 알고리즘 문제 풀어보기 📌분할 정복(Divide&Conquer) 알고리즘이란? : 나누고 정복한다는 의미로, 크고 복잡한 문제를 작은 단위로 나눠 해결한 후 다시 합치는 알고리즘이다. (Top-down 형태) 현재의 선택이 나중에 미칠 영향을 고려하지 않는다. 그렇기 때문에, 그 정당성 분석이 중요하다. ▶️ 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요! 동적(dynamic) 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위한 개념이다. 대표적인 문제로 거스름돈 문제, 활동 선택 문제 등이 있다. 〰️ 분할 정복법의 과정..

🚦 이번 포스팅에서는 〰️ ▶️ 백트래킹(Backtracking)이란? ▶️ 백트래킹(Backtracking)문제 풀어보면서 익히기 📌 백트래킹(Backtracking)이란? : 해를 찾는 도중 해가 아니라서 막힌다면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. --> 반복문의 횟수까지 줄일 수 있음 일명 가지치기(pruning)로, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 그러나, 문제가 N!의 경우의 수를 가질때 최악의 경우로 O(지수함수) 필요할 수 있다. 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 답이 될만한지 판단하고, 그렇지 않으면 가지치지한다. 주로, DFS 등 모든 경우의 수를 탐색하는 과정에서 조건문 등을 ..

그리디 문제이다. 2+1으로 3개중 가장 작은 값을 무료로 해주기 때문에 가능한 큰 숫자들끼리 묶어서 가장 작더라도 전체에서는 큰 숫자를 무료로 받도록 코드를 짰다. 내림차순으로 정렬 3개씩 묶어서 마지막 값은 sum에 포함 안해준다. (인덱스가 0부터 시작하므로 i%3이 2가 아니면 다 더해줌) #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; vector c; cin >> N; for(int i=0; i> t; c.push_back(t); } sort(c.begin(), c.end(), greater ()); long..

🚦 이번 포스팅에서는 〰️ ▶️ 동적 계획법(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는 재..