스도쿠 (골 4) : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠는 내가 정말 좋아했던 게임이다. 에버랜드 알바하던 시절에 쉬는 시간 틈만 나면 폰으로 스도쿠 했을 만큼 좋아했다. 스도쿠를 하면서 가장 힘들었던 유형은, 노가다로 숫자를 하나씩 집어 넣어 중복되는게 없는지 일일이 다 확인해야 하는 경우가 많은 문제였다. 이 문제는 그 노가다 과정을, 고스란히 코드로 옮기는 문제이다. 접근 방법은 다음과 같다. 1. 빈 칸에 숫자 1을 ..

쉬운 문제를 어렵게 풀지 말자. 문제를 접했을 시, 노가다가 가능한지 항상 우선적으로 생각하자. 완전 탐색(exhaustive search, 철저한 검색이라는 뜻.)은 말 그대로 경우의 수를 모조리 찾아보는 탐색법이다. 브루트 포스(한국말로 노가다)라고도 한다. 1. 순열/조합 유형 2. 재귀 함수를 사용하는 유형. (feat 완전 탐색 레시피 : https://sanghoonly.tistory.com/25) 3. 재귀 함수를 사용하지 않는 유형. + 최적화 문제 또한 완전 탐색으로 접근할 수 있다. 사실, 완전 탐색은 최적화 문제를 풀기위한 가장 기초적이고 직관적인 방법인데, 그냥 전부 답을 생성한 다음 그중에서 제일 좋은 것을 골라내면 되기 때문이다. (ex. 외판원 문제) 1. 순열/조합 유형 - ..

다음 순열 : https://www.acmicpc.net/problem/10972 이전 순열 : https://www.acmicpc.net/problem/10973 모든 순열 : https://www.acmicpc.net/problem/10974 다음 순열과 이전 순열에선 우선 input으로 어떤 수열이 주어진다.그러면 결과로 그 수열 이후/이전에 오는 순열(permutation)을 프린트한다. 모든 순열에선 n이 주어지며, 1 ~ n 까지 모든 permutation을 구하면 된다. 1. 반복문으로 해결하기 - 다음 순열 next_permutation이 치트키이지만... 안쓰고 반복문으로 도전해보았다. #include #include #include using namespace std; int N, k;..

N과 M (2) : https://www.acmicpc.net/problem/15650 N과 M (4) : https://www.acmicpc.net/problem/15652 N과 M (6) : https://www.acmicpc.net/problem/15655 N과 M (8) : https://www.acmicpc.net/problem/15657 N과 M (10) : https://www.acmicpc.net/problem/15664 N과 M (12) : https://www.acmicpc.net/problem/15666 2번은 n개의 자연수 중 m개를 고르는 조합(nCm) 문제이고, 4번은 중복 조합을 구하는 문제이다. 6번은 2번과 똑같이 nCm을 구하는 문제인데, n개의 자연수가 크기에 상관없이 ..

N과 M (1) : https://www.acmicpc.net/problem/15649 N과 M (3) : https://www.acmicpc.net/problem/15651 N과 M (5) : https://www.acmicpc.net/problem/15654 N과 M (7) : https://www.acmicpc.net/problem/15656 N과 M (9) : https://www.acmicpc.net/problem/15663 N과 M (11) : https://www.acmicpc.net/problem/15665 1번은 n개의 자연수 중 m개를 고르는 순열(nPm)을 구하는 문제이고, 3번은 중복 순열을 구하는 문제이다. 5번은 1번과 똑같이 nPm을 구하는 문제인데, n개의 자연수가 크기에 상..

https://www.acmicpc.net/problem/9095 1. 문제 이해 => 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 1, 2, 3을 사용해서, 1, 2, 3의 합으로 n을 나타내는 방법의 수를 구하는 것. 2. 재정의 & 추상화 => 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. == 1, 2, 3을 사용하여 n을 나타내는 모든 경우의 수를 구하여라. == 완전 탐색 문제 == 재귀, 분할 정복등을 사용 3. 설계 재귀적 접근 : 함수 내부에서 for 문으로 1, 2, 3을 돌면서 n - 1, n - 2, n - 3한 값을 다시 함수에 인자로 넣음. 기저 사례는 n이 0..