걸음마코딩기

트리와 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 등 모든 경우의 수를 탐색하는 과정에서 조건문 등을 ..

문제를 풀다보면 종종 순열, 조합, 중복순열, 중복조합을 이용하는 경우가 있다. 이번 포스팅에서는 각각의 정의와 c++로 구현하는 방법에 대해 정리해보았다. 1. 순열 : 순서를 따지고, 중복을 허용하지 않는다. 중복을 허용하지 않기 때문에, 중복을 검사하는 visitied 처리가 필요하다. depth로 r만큼의 길이를 출력해준다. 그렇지 않다면 중복을 검사한 후, 재귀로 함수를 부른다. depth가 r이 될때, 순열이 완성된 것이므로, 순열을 출력해주고 backtracking해준다. backtracking을 수행한 뒤, check[i] = false로 다음 루프에서 해당 숫자를 사용할 수 있게 한다. 그렇지 않으면, 한번 사용된 숫자는 계속 사용중으로 표시가 되어, 그 숫자가 다른 가능한 순열 위치에서..

git에 push하다가 이런 에러를 직면했다. git을 다루다보면 한번쯤 봤을 에러인데, 해결책을 맨날 까먹고 구글링하길래 적어본다. ❓원인 ✔️ push 하려는 github에 내 Local에 없는 파일이 존재하기 때문에 생기는 에러이다. ❗️해결방법 1. pull git을 먼저 pull해와서 현재 내 Local과 상태를 맞춰주어야 한다. git pull {원격저장소(보통 origin)} {branch(main, master ...)} 2. push 그 다음 동일하게 push를 해주면 잘 올라간다. git push {원격저장소(보통 origin)} {branch(main, master ...)} 그런데 이래도 해결이 잘 안될때가 있다. 이럴땐 강제로 그냥 올리는 방법도 있다. 정석적인 방법은 git pu..

내가 우선적으로 보려고 만들어놓은 Linux 명령어 요약본 (풀어서 쓴 정리본은 추후 업데이트 예정) ls 명령어 모음 *명령어 중복가능 ex) ls -il : i-node및 l에서의 정보 나옴 디렉토리 명령어 모음 - 디렉토리 생성/삭제/변경 : mkdir/rmdir/cd - 현재 디렉토리확인 : pwd, dirs 파일 명령어 모음 파일복사 cp cp -R, -r : 전체 디렉토리의 내용을 재귀적으로 복사 cp -p : 원본파일의 파일속성 보존 cp -s : 파일복사대신 symbolic link생성 현재 dir에 복사하는 법 : . 파일이름변경/이동 & 제거 mv & rm rm -i : 삭제하기 전 물어봄(**i : interactive, 사용자와 상호작용함) rm -r : 재귀적으로 하부 dir까지 ..

그리디 문제이다. 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