걸음마코딩기

🚦 이번 포스팅에서는 〰️ ▶️ 최단 경로 알고리즘? ▶️ 주요 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜) ▶️ 다익스트라 알고리즘 ▶️ 벨만-포드 알고리즘 ▶️ 플로이드-워셜 알고리즘 이번에는 최단 경로 알고리즘을 싹다 정리해보기로 했다!! 마침, 너무 정리가 잘 된 블로그를 찾게되어서 블로그 글을 요약해보며 공부하기로 했다. 블로그 = https://roytravel.tistory.com/340 감사합니다. 📌 최단 경로 알고리즘? : 최단 경로 문제는 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 〰️ 최단 경로 계산 방식 One-To-One : 한 지점에서 다른 특정 지점까지의 최단경로 One-To-All : 한 지점에서 다른 모든 지점까지의 최단경로 All-To..

대표적인 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..

전형적인 bfs 문제로, 목표지점을 기준으로 각 좌표들의 최단거리를 구해주면 된다. queue를 이용해 각 좌표들의 visited 처리와 함께 거리를 구해주었다. #include #include using namespace std; int n, m, r, c; int graph[1001][1001] = {0,}; int visited[1001][1001] = {0,}; //각 좌표의 상,하,좌,우를 탐색해준다. int dir_n[4] = {-1,1,0,0}; int dir_m[4] = {0,0,-1,1}; //목표좌표를 기준으로 시작된다. void bfs(int x, int y) { queueq; q.push(make_pair(x,y)); visited[x][y] = 1; while(!q.empty())..

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

전형적인 dp문제이다. 각 돌에 도달하기 위한 값들을 잘 정리하면 풀 수 있다. #include #include #include using namespace std; #define MAX 999999; /* three jumps plus 1 (no skip) plus 2 (1 skip) plus 3 (2 skips) -> just one time & k energy */ int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,k; cin >> n; pair energy[21]; for(int i=1; i> x >> y; energy[i] = make_pair(x,y); } cin >> k; /* dp[i][0]은..

🚦 이번 포스팅에서는 〰️ ▶️ 백트래킹(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..

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