궤도

문제 풀이 숫자의 순서는 고정되어 있으니 백트래킹의 대상이 되는 것은 사칙연산 기호 뿐이다. 종료 조건을 만나면 함수를 종료하던 이전 문제들과 달리 노드의 끝에 다다르면 최댓값, 최솟값을 갱신하며 모든 경우의 수를 따져야 한다. 소스코드 #include using namespace std; int min_num = 1000000000; int max_num = -1000000000; int arr[11]; int op[4]; int N; int cal(int a, int b, int op) { //계산 int result = 0; switch (op) { case 0: result = a + b; break; case 1: result = a - b; break; case 2: result = a * b..

문제 풀이 입력을 어떻게 처리하여 어떤 순서로 스도쿠의 빈공간을 채워나갈지 고민을 많이했다. 처음에는 1행->9행으로 값을 채우고 그 다음에 1열->9열로 값을 채우고 마지막으론 구역별로..?라고 생각하다가 너무 복잡해질 것 같다는 생각이 들었다. 그러다 내가 실제로 스도쿠를 볼 때 어떻게 푸는지 생각했다. 보통 사람들은 먼저 빈공간을 찾아가서 그 공간의 행, 열, 구역을 한번에 확인한 뒤 값을 채워나간다. 그럼 코드도 이런식으로 짜면되지 않을까? 싶었다. 입력을 받으면서 빈공간을 봐둔 다음에 각각의 빈공간마다 1~9를 넣어보면서 그 공간의 행, 열, 구역의 숫자와 비교하면 될 것 같았다. 이 아이디어를 떠올리니 나머지는 크게 어렵지 않았다. 소스코드 #include using namespace std;..

문제 풀이 N-Queen 문제는 백트래킹의 대표적인 문제이다. 근데 난 얘가 너무 어렵다... 이런 체스판에 퀸을 놓고 이 퀸들이 서로 공격할 수 없게 놓는 문제이다. 퀸은 가로세로대각선으로 이동할 수 있으니 어떠한 퀸들도 같은 행열대각선에 위치하지 않도록 배치해야 한다. 소스코드 #include using namespace std; const int SIZE = 15; int n, ans; int check[SIZE]; bool promising(int num) { int idx = 0; while (idx < num) { //이미 놓여있는 모든 퀸에 대해 if (check[num] == check[idx] || abs(check[num] - check[idx]) == (num - idx)) //같은 ..

문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com myunji.tistory.com/199?category=1154147 [백준] 15651번 : N과 M (3) 문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?categor..

문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com 번호로는 위 문제의 다음이지만 사실 이 문제가 더 간단하다. 왜냐하면 현재 노드를 기억해 둘 필요도 없고...눈치가 빠른 사람은 알겠지만 입력에 따른 출력 갯수가 N^M이다. 소스코드 #include using namespace std; const int MAX = 8; int N, M; int a..

문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 myunji.tistory.com 이 문제를 약간 응용한 문제이다. 오름차순을 구현하려면 어떻게 해야할까? 현재 노드의 값을 기억해두면 될 것이다. 소스코드 #include using namespace std; const int MAX = 8; int N, M; int arr[MAX]; void backNM(int cnt, int flag) { //오름차순 위해 현재 노드 저장하는 flag 추..

문제 풀이 입력으로 들어오는 값의 범위가 커서 단순한 덧셈 연산으로는 해결할 수 없다. 구몬 수학을 풀던 초등학교 시절로 기억을 되돌려보면 이런식으로 1의 자리부터 더하는게 좋을 것이다. 그런데 위와 같이 두 수의 자릿수가 다르면 어떻게 될까..? 여러 방법이 있겠지만 가장 간단한 방법은 이렇게 0을 붙여주는 것이다. 소스코드 #include #include #include #include using namespace std; int main() { string str1, str2; vector A, B, C; bool isCarry = false; //받아올림 여부 cin >> str1 >> str2; if (str1.size() < str2.size()) //str1(A)의 길이가 더 길도록 swap..

왜 쓰게 됐는가? git과 github의 차이는 알지만 그래서 어떻게 레포지토리를 만들어서 연동하는지 궁금한 사람들을 위한 글이다. 왜냐면 과거의 내가 그랬기 때문...정말 처음부터 떠먹여주는 글이 필요했는데 당시 빈약한 구글링으론 찾을 수 없었다. 당신은 이 글을 찾을 수 있을까..? 모든 글은 실제 내가 쓰는 방법을 기준으로 한다. 나도 잘 쓰는 편은 아니라 내 방법이 제일 좋은건 아니란 것이다. 준비물 git cmd를 설치하고 초기 설정하는 과정은 boogong.tistory.com/58 윈도우 10에서 git 설치하기입니다. 평소 Git을 사용하지 않지만, 깃허브 페이지에 블로그를 개설하게 되어 Git를 사용하게 되었습니다. 개인적으로 깃 설치가 어렵네요. 선택 사항이 많은데 다 영어고 전문용어라..