걸음마코딩기

🚦 이번 포스팅에서는 〰️ ▶️ 분할 정복(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

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

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