노는 게 제일 좋아

전형적인 백트래킹 문제다. 백트래킹에 익숙하지 않은 터라 다른 사람풀이를 봐도 이해가 시간이 걸렸다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹은 제일 인간다운 생각이 아닌가 싶다. 그리고 무의식적으로 그것이 효율적이라 생각하면서 쓰고 있다. 우선 나는 그렇다. 우선 이 문제를 보자마자 같은 줄에 못놓겠구나 생각이 들었다. 아무튼 거기까지만 하고 들어가보자 한줄에 하나 넣어보고 다음 줄에 되는 것 넣어보고 그 다음줄에 되는 것 넣어보고 하면 될 ..

나 이거 맞았길래 봤더니 파이썬으로 풀었음 ㅎ 파이썬 permutation으로 3초만에 풀었음..ㅎ C++로 해보자꾸나.. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹이라는 원리를 적용해서 푼다. 코드에 주석을 보면서 이해해보자 #include #include using namespace std; int n,m; /////////////////////////////////////// int arr[10]; // 선택에 ..

나는 재귀가 아직도 헷갈린다. 이 문제를 분석하며 한 번 더 배워가자 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 이 문제는 또 재귀다. 결과를 보고 과정을 생각해내는 것이다. 해보자. 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의..

하노이 탑의 근본을 알려주는 문제다 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이 탑하면 재귀문제가 떠오른다. 하지만 감은 전혀 안 온다. 아니 감이 안 온다기보다는 코딩을 못하는 것이다. 머리로는 이해가 가는데.. 코딩을 어떻게 해야하지?? 나도 그렇다. 아직 재귀가 익숙치 못하다. 하나씩 알아보자 여기 링크 들어가서 알아보자 https://www.mathsisfun.com/games/towerofhanoi.html Pl..

재귀나 숫자 범위에 대해 기본적인 문제 좋은 것 같다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 음.. 처음 봤을 때 당황 많이했다. int, 4바이트 long long 8바이트 재귀함수까지... 재귀함수는 항상 그게 중요하다. 점화식을 찾는 것... 1번, n번 n+1번까지의 식만 찾으면 굿 맞는 풀이( 틀린 풀이도 집어넣어놨다.) #include using namespace std; using ll = long long; ll remain(ll a, ll b, ll c){ //n = 1일 때 if(..

간단한 산수문제다. 메모리제한 256이 아니라 512네? 우선 두고보자 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 시간 5분이나 더 썼다. 1,000,000 * 1,000,000 는... 우선 21억을 넘어간다. ㅎㅎ int형으로는 불가능 long long으로 쓰자. 64비트다. int는 32 비트다. 2^32배 더 큰 수를 표현할 수 있다. 21억 * 21억 하면 되겠다. # 맞는..

뭐 이것도 BFS의 기본문제라고 볼 수 있겠다 다만 이건 입력을 특이하게 받는 케이스? 라고 보면 된다. https://www.acmicpc.net/problem/1012 #맞는 풀이 하지만 정제되지 않음 손에 익지 않아서 20분정도 걸림 주석포함 솔직히 다른 사람은 어떻게 그렇게 정제된 풀이가 바로 생각나는거지??... 아직 갈 길이 멀다. #include #include #include #define X first #define Y second using namespace std; int tc; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //t..

BFS의 응용문제다. 어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다. www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제도 BFS를 이용한다는 감이 온다. 고려해야 할 조건이 몇가지 있다. 1. 지훈이의 탈출 조건 2. 불이 있는 곳에 지훈이 있을 수 없다. 우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다. 즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다. -> 다시 말해서 가..

이것도 BFS의 기본이라고 볼 수 있다. www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전 문제의 최단경로의 경로문제라고 해도 무방하다. 하지만 약간 꼬아놨으니 BFS의 시작점이 여러군데다. 근데 뭐 별다를 거 없다. 시작점을 큐에 다 넣고 시작하는 것과 같이 얘도 똑같이 해주면 된다. #맞는 풀이 다만 최적화는 되어있지 않은 풀이 #include #include #define X first #define Y second using nam..

이 문제도 이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데 뭐 메모리랑 관련이 있다고만 해두겠다. **사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다. # 맞는 풀이 #include #include using n..