Greedy Algorithm - 결정해야할 때 그 순간에 가장 좋다고 생각하는 것(기준이 필요)을 선택하면서 답을 찾아가는 알고리즘 - 그 때는 최적일지도 모르지만 최종적으로는 답이 최적이 아닐 수도 있다. - 기준을 하나 선택해서 계속 적용하는 것 - 왜 그 기준을 선택하는 것이 정답인지를 증명해야 한다. 그리디 알고리즘의 흔한 예시인 거스름돈 문제는 사실 동전이 배수 관계이기 때문에 성립 가능하다. 💚1080 행렬 결국에는 0, 1밖에 없으므로 궁극적으로 연산을 아예 안 하는 것과 1회 한 것으로 나눌 수 있다. 3 X 3보다 큰 행렬을 바꾸는 연산을 할 때 가장자리가 연산횟수가 1회로 가장 적다. 그걸 기준으로 바꾸는 연산을 할지 말지 결정해야 한다. 행렬을 순회하면서 가장자리의 정보를 가지고 판..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 초기화를 잘못해서 어이없게 헤맨 문제이다. 처음에 코드를 짤 때 신중하고, 엣지 케이스를 잘 만들어야 한다. #include #include using namespace std; int main() { int n; cin >> n; vector v(n); // 모든 수의 최소 길이는 1이므로 인덱스가 0인 값 외에도 1..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr Level 3이라고 적혀있지만 Level 3이 아닌 듯 하다. 문제에서 안내된대로 폭포수 같이 삼각형의 꼭대기에서부터 바닥까지 탐색하면서 최대값을 찾으면 된다. DP를 활용하면 되는데, 어떤 부모(왼쪽? 오른쪽?)의 값을 가져오는 것이 이득인지 따지면 된다. 어차피 그 다음의 child들은 grandparent와 전혀 무관하기 때문이다. 그래서 Level 0을 제외한 Level 1 ~ Level.last까지 왼쪽과 오른쪽 중 큰 값을 가..

💚 16928 뱀과 사다리 게임 - 100개의 칸으로 나누어져 있는 게임이 있다. 1에서 100으로 가야 한다. - 주사위를 굴려 나온 수만큼 이동할 수 있으며, 도착한 카이 사다리인 경우에는 사다리를 타고 더 큰 번호의 칸으로, 뱀인 경우에는 더 작은 번호의 칸으로 이동한다. - 주사위에 나온 수를 정할 수 있을 때, 최소 몇 번 굴려야 하는지 구하는 문제 - 게임에서 뱀과 사다리의 구분은 중요하지만 구현에서는 별로 중요하지 않다. - x ➡️ y로 간다는 점만 중요하다. - 새로운 배열 next[x]를 만들어서, x에 도착한 이후에 가야할 곳을 모두 기록 - 뱀이나 사다리인 경우에는 next[x] = y - 일반 칸인 경우에는 next[x] = x #include #include #include #d..

💚 14225 부분수열의 합 - S의 부분 수열의 개수는 2^N가지 - N > n; for(int i = 0;i > a[i]; } // 비트마스크로 모든 부분 수열 조합을 만든다. for(int i = 0;i > a[i]; } int ans = -1; for(int k = 0;k > m; for(int i = 0;i > board[i][j]; // R, B, O는 특수한 값이므로 별도 변수에 저장 // 최대한 간편한 계산을 위해 board에는 #,..

백트래킹 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 백트래킹에 따라 최적화가 달라진다. 💚 9663 N-Queen 대표적인 백트래킹 문제이다. N X N 크기의 체스판 위에 Queen을 N개 놓는 방법의 수를 구하는 문제 브루트포스 시에는 칸에 퀸이 있음 또는 없음 ➡️ 2^N^2 하나의 행/열에는 퀸이 하나만 가능하다는 점을 고려하면 체스판의 절반만 확인하면 되므로 N!까지 경우의 수를 줄일 수 있다. calc(row): row 행에 퀸을 어디에 놓을지 결정해야 함 Check 부분을 배열을 이용하면 놓을 수 있는지 검사를 O(1)만에 해결할 수 있다. #include using namespace std; bool a[14][14]; int n; bool che..