알고리즘

(C++) 백준 1182번 - 부분수열의 합

문제 링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 백트래킹을 활용하여 풀이하였다. 부분수열에 숫자 하나를 포함하거나 포함하지 않거나 하는 경우를 모두 시도하여 조건에 맞는 경우를 카운트하는 식으로 풀이하였다. #include using namespace std; int n, s, tmp, size, cnt; int num[20]; int used[20]; void subseqadd(int i..

(C++) 백준 9663번 - N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹을 활용하여 풀이하였다. Queen은 같은 행이나 열, 같은 대각선 상에 존재하면 서로를 잡을 수 있다는 점을 알아야 한다. 그렇기에 한 행에 놓으면 같은 행의 다른 칸에 놓을 수 없음을 이용하여 한 행에 Queen을 하나씩만 두고, 열과 대각선 상만 피해서 Queen을 놓게 구현하면 된다. #include using namespace std; int n; int isUsedcol[15..

(C++) 백준 15649번 - N과 M (1)

문제 링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 백트래킹을 사용한 풀이이다. 이미 특정 숫자가 배열에 들어가 있는지 arr을 순회하면서 확인하고, 들어있지 않은 숫자들만 배열에 삽입한다. 사이즈가 m이 되는 순간 지금까지 배열에 저장해 놓은 숫자들을 출력한다. #include using namespace std; int n, m; int arr[8]; void nNm(int num, int idx){ for(int x = ..

(C++) 백준 13549번 - 숨바꼭질 3

문제 링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 백준 1697번(숨바꼭질)과 상당히 유사한 문제이다. 비슷하게 풀이하되 시간이 들지 않는 2배 순간이동을 최우선으로 체크하고, 다음으로 - 연산, + 연산 순으로 BFS를 쓰면 된다. #include #include #include #define X first #define Y second using namespace std; int n,k; ..

(C++) 백준 7569번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 토마토(백준 7576번)의 3차원 버전이다. 2차원과 동일하게 진행하되 체크를 6개의 방향으로 진행하도록 BFS를 구현하면 된다. #include #include #include using namespace std; int dx[6] = {1,0,0,-1,0,0}; int dy[6] = {0,1,0,0,-1,0}; int dz[6] = {0,0,1,0,0..

(C++) 백준 10026번 - 적록색약

문제 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 백준 1926번 그림 문제와 거의 동일한 문제이다. BFS를 이용하여 풀이를 하였다. 색약이 아닌 사람들은 1926번에서 풀이한 그대로 하면 되고, 색약인 사람들의 경우에만 R과 G를 동일한 색인 것처럼 풀이하면 된다. //boj 10026 성공 #include #include #include #define X first #define Y second using name..

(C++) 백준 1074번 - Z

풀이 재귀를 이용하여 풀이하였다. 2의 거듭제곱으로 커져가기 때문에 한 변의 길이가 2, 4, 8, 16, ... 순으로 증가한다. 그렇기 때문에 한 변이 2일 때를 재귀를 종료하는 base condition으로 두고, 사각형들을 4개로 분할하여(한 변의 길이를 2배씩 줄여) 나가면서 풀었다. #include using namespace std; int calZ(int n, int r, int c){ if(n == 1){ // 2 * 2 일 때 if(r == 0 and c == 0) return 0; else if(r == 0 and c == 1) return 1; else if(r == 1 and c == 0) return 2; else return 3; } int half = (1= half and ..

(C++) 백준 11729번 - 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 재귀 문제의 대명사격인 하노이 탑 문제이다. s에서 l로 n개를 이동하려면 다음과 같은 과정을 거치면 된다. 1. 제일 아래에 있는 가장 큰 판을 제외한 n-1개의 판을 s에서 6-s-l로 이동시킨다. 2. 제일 큰 판을 s에서 l로 이동시킨다. 3. 1에서 6-s-l로 이동한 n-1개의 판을 l로 이동시킨다. 이 과정을 재귀로 반복하여 문제를 풀이하였다. #inc..

(C++) 백준 1629번 - 곱셈

문제 링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 재귀를 활용하여 풀이하였다. "n의 k승을 알면, n의 2k승과 n의 2k+1승을 알 수 있다."는 사실과 "(a x b) % k = (a % k) x (b % k)"라는 사실을 활용하여 풀이를 진행하였다. #include using namespace std; using ll = long long; int power(ll a, ll b, ll c){ if(b == 0) return 1; // 모든 수의 0승은 1 if(b == 1) retur..

(C++) 백준 1697번 - 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 응용한 문제로 실버 1 문제치곤 어렵지 않게 해결할 수 있다. 다만 조건에 수빈이와 동생이 같은 위치에 있을 순 없다는 말이 없으므로 같은 위치에 존재하면 그냥 0을 출력하고 종료할 수 있도록 해야 한다. #include #include #include #define X first #define Y second using namespace s..