전체 글
[C++] BOJ 9251 / DP (LCS 최장 공통 부분 수열)
코드 #include #include #include using namespace std; int same[1002][1002]; int main() { ios::sync_with_stdio(0); cin.tie(0); string a, b; cin >> a >> b; int lenA = a.size(); int lenB = b.size(); for(int curA=1;curA
[C++] BOJ 2579 / DP (계단 오르기, 점화식 2차원 배열 접근)
코드 #include #include using namespace std; int stairs[301]; int arr[301][2]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i> stairs[i]; } arr[0][1] = stairs[0]; arr[1][2] = arr[0][1] + stairs[1]; arr[1][1] = stairs[1]; for(int i=2;i 2칸 째에 i번 계단을 밟았을 때의 최대 점수 점화식 arr[i][1] = max(arr[i-2][1], arr[i-2][2]) + stairs[i] arr[i][2] = arr[i-1][1] + stairs[i]
[C++] BOJ 9095 / DP (1, 2, 3 더하기)
문제 분석 https://www.acmicpc.net/problem/9095 해당 문제도 DP로 해결해야 한다. DP의 경우에는 정말 어려운 문제가 아닌 이상, 문제 분석과 해결 방법은 생략하겠다. 코드 #include using namespace std; int arr[12] = {0,1,2,4,0,0,0,0,0,0,0,0}; int main() { int t, n; cin >> t; while(t--) { cin >> n; if(n
[C++] BOJ 1463 / DP (1로 만들기, 점화식 첫 도전)
문제 분석 https://www.acmicpc.net/problem/1463 BFS로도 구현이 가능하지만, DP로 훨씬 깔끔하게 구현이 가능하다. 어떠한 문제에 DP를 적용해야 하는지 깨닫기 위해서는 많은 문제를 풀면서 습득해야 한다. 해결 방법 DP 문제는 공통적인 해결 방법을 갖는다. 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 이다. 코드 #include #include using namespace std; int arr[1000001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=2;i
[C++] BOJ 15683 / 시뮬레이션 (감시, 첫 시뮬레이션 노가다 경험)
문제 분석 https://www.acmicpc.net/problem/15683 5가지 종류의 CCTV가 배치되어 있고, 각 CCTV는 감시하는 방향이 다르지만, 회전 시킬 수 있다. CCTV의 배치도가 주어졌을 때의 사각 지대의 최소 크기를 출력하는 문제이다. CCTV가 감시할 수 있는 방향이 정해져있으며, 회전 시 킬 수 있는 경우의 수는 1번 CCTV부터 차례로 4 2 4 4 1 이다. 회전 시킬 수 있는 모든 경우의 수를 따지고, 그 중 사각 지대가 가장 적을 때를 출력하면 된다. 해결 방법 시뮬레이션 문제라서, 따로 해결 방법이라고 할 것이 없다. 문제에 주어진 조건을 충실히 지키며 구현하면 된다. 코드 #include #include #include #include using namespace ..
[C++] BOJ 1941 / 백트래킹 (소문난 칠공주, next_permutation 사용)
문제 분석 https://www.acmicpc.net/problem/1941 25명의 여학생들 중에 문제 조건에 맞는 인접한 그룹의 경우의 수를 출력하는 문제이다. 주어진 조건은 1. 여학생 수가 7명이어야 한다 2. 7명은 가로나 세로로 인접해 있어야 한다. 3. 7명 전부 이다솜파 일 필요는 없다. 4. 최소 이다솜파가 4명 이상은 반드시 포함되어야 한다. 해결 방법 1. 총 25명 학생 중에서 7명을 뽑아야 한다. (1번 조건 충족 시키기) - next_permutation 사용 2. 7명 중에 이다솜파가 4명 이상 있는지 확인한다. (4번 조건 충족 시키기) 3. 7명이 서로 인접해 있는지 확인한다. (2번 조건 충족 시키기) - BFS 사용 코드 #include #include #include ..
[C++] BOJ 9663 / 백트래킹 (N-Queen, 2차원 배열 속 대각선 계산)
문제 분석 https://www.acmicpc.net/problem/9663 크기가 N X N 인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 출력하는 문제이다. 체스 말에서의 퀸은 대각선을 포함한 상하좌우로 여러 칸 이동 가능하다. 해결 방법 퀸을 행 별로 하나 씩 배치하면서, 만나지 않는 경우를 전부 찾아야 하므로 백트래킹을 사용해야한다. 행 별로 하나 씩 두기 때문에, 같은 행에 있는지는 체크 하지 않아도 되지만, 같은 열에 있는지와 우측 대각선 좌측 대각선에 있는지 체크하기 위해 배열을 3개 사용해야한다. 같은 대각선에 있음을 확인하는 방법은, x+y가 같으면 좌측하단에서 우측상단을 잇는 대각선에 위치해있다. 반대로 좌측상단에서 우측하단을 잇는 대각선은 x-y가 같은지 확인하면 ..
[C++] BOJ 15649 / 백트래킹 (M과 N(1), 백트래킹 첫 도전)
문제 분석 https://www.acmicpc.net/problem/15649 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 문제이다. 해결 방법 비어있는 리스트에 가능한 숫자를 넣어가며, 리스트의 사이즈가 M이 됐을 때를 base case로 설정하여 구현한다. 중복 없이 고른다는 조건이 있기 때문에, 이미 리스트에 포함되어 있는 숫자인지 체크하기 위한 배열을 선언해야한다. 코드 #include using namespace std; int n,m; int arr[10]; bool choice[10]; void pick(int k) { if(k==m) { for(int i=0;i
[C++] BOJ 2447 / 재귀 (별 찍기10 / Divide and Conquer)
문제 분석 https://www.acmicpc.net/problem/2447 별 찍기 문제이지만, 규칙이 정해져 있으므로 재귀로 구현해야 한다. 해결 방법 N에 따라서 균등하게 9등분이 가능하다. 9등분을 하며 재귀호출을 하고, 5번 째 조각일 경우에 호출을 건너뛰면 된다. base case는 n이 1일 때, 즉 더이상 나눌 수 없을 때 이다. 코드 #include #include using namespace std; char board[2188][2188]; // 3^7 == 2187 void func(int x, int y, int n) { if(n == 1) { board[x][y] = '*'; } else { int div = n/3; for(int i=0;i n; for(int i=0;i
[C++] BOJ 16920 / BFS (확장게임, BFS 이동 제한)
문제 분석 https://www.acmicpc.net/problem/16920 플레이어 수는 최대 9명이며, 플레이어 끼리 성을 하나 씩 가진 채로, 성을 상하좌우로 확장시키는 게임이다. 중요한 조건은 이동할 수 있는 칸수를 정해준다는 것이다. 기본적인 BFS는 1칸으로 제한되어 있다고 생각하면 이해하기 쉽다. 2칸 이상 씩 이동할 수 있게 조건이 주어진 경우를 구현하는데에 시간을 많이 썼다. 해결하고 생각해보면 간단한 것이었는데 난이도를 보고 어려울 것이라 지레짐작 했던 것이 악영향을 끼쳤다. 기본적인 것을 응용하는 것 또한 중요하다는 점을 깨달았다. 해결 방법 성이 이동할 수 있는 칸이 제한되어 있기 때문에, 이 조건을 맞추기 위해서는 BFS 이동 횟수를 제한해야 한다. 종료 조건이 모든 플레이어의 ..