💜개발과 일상 (≧∇≦)ﾉ

📌 문제 Longest Common Subsequence, 최장 공통 부분 수열을 구하는 문제다. 이 문제는 직접적으로 문제의 규칙을 알려주지 않지만 암묵적인 규칙이 존재한다.일단 부분 수열을 만들 때 무조건 수열 내 알파벳 순서를 지켜야한다는 점이다. 필자는 이 문제가 DP로 풀린다는 것을 알고 있었지만 어떻게 풀어야하지?? 막막했다. 하지만 DP라는 문제를 생각해내면 금방 풀 수 있는 문제다. 먼저 문자열 별로 배열을 두 개 작성할 수 있도록 한다. 💻 정답 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //첫째 줄과 ..

#include using namespace std; int main() { long long N; cin >>N; int Cnt = 1; long sum = 1; long temp = 1; while (true) { if (sum >= N) { cout

📌 문제 M x N 보드를 8x8 크기 체스판으로 만들기 ( M,N > N; int M; cin >> M; char** arr = new char*[N]; for (int i = 0; i > arr[i]; } //모든 변수 선언 및 입력 int min = 9999999999999; for (int k = 0; k < N - 7; k++) { for (int l = 0; l < M - 7; l++) { int CntB = 0; int CntW = 0; for (int i = k; i < 8 + k; i++) { for (int j = l; j < 8 + l; j++) { if ((i + j) % 2 == 0) { if (arr[i][j]..

📌 문제 카드의 개수 N, M 둘째줄 부터는 카드에 쓰여 있는 수, ( 10만을 넘지 않음 ) 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우의 수를 구하라. 만약 카드를 3장 이상이거나, 사용자가 원하는 카드 장수를 입력받을 경우는, 재귀함수로 구현을 해야하지만 3장이라 충분히 삼중 반복문을 통해서 3가지를 고른 후 모든 경우의 수를 계산할 수 있다. 브루트 포스로 충분히 풀 수 있는 문제 반복문을 쓸 때 끝 값이나 초반 값이 index가 넘어가지 않도록만 주의하면 된다. 💻 정답 코드 #include using namespace std; int main() { int N; cin >> N; if (N 100) return 0; int M; cin >> M; if (M < 10..

📌 문제 내용을 직관적이게 정리하자면, 문자열 S가 주어지고, 테스트 케이스 q 를 입력 받으면 문자열 S 내 l번째 ~ r번째 문자 내에 문자 a가 몇 개 있는지 케이스 별로 출력하는 문제이다. 조건은 문자열은 20만자 이하, 테스트 케이스 수는 20만개이다. 이게 문제라고? 너무 쉽잖아 그냥 반복문으로 계산하면 되지 않을까? 라고 생각할 순 있지만, 테스트 케이스의 개수와 문자열의 개수를 보자. 테스트케이스마다 문자열을 탐색하면 시간복잡도가 기하급수적으로 증가하여 비효율적이다. 이 문제는, 결론을 먼저 말하자면 누적합 문제이다. 누적합은 빈도수나 구간 별 숫자의 합을 계산할 때 DP를 효율적으로 사용할 수 있다. 예를 들어, n부터 m까지 순서에 있는 숫자를 다 더하는 알고리즘이 있을 경우 이 전에 ..

📌 문제 N일이 주어지만 하루 별 해결할 수 있는 일이 주어진다. 해당 일이 언제 주어지는지와 그 일을 해결하기 까지 필요한 시간이 주어진다. 주어진 일 리스트에서 일을 골라 했을 때 가장 수입이 높을 때의 수입을 출력하는 문제다. 문제를 처음 봤을 땐 백트래킹 문제인가? 싶었는데 최종 결과를 이전에 판단할 수 없기 때문에 brute force 문제라고 판단했다. 1년전, 동기들이랑 코딩테스트 스터디를 했을 때 풀었는 듯 하다... 과거에 내가 모든 경우의 수를 탐색할 수 있도록 재귀 함수를 기반으로 구현을 했다. 1년전 코드기 때문에 부끄럽다... 사실, 재귀함수는 위험한 방법이고 불필요하게 프로세스를 생성하므로 백준 문제를 풀 때 자주 시간초과가 났기 때문에 내 코드가 그렇게 좋은 방법은 아닌 듯 하..

https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 📌 문제 자잘한 문제 내용을 제거하고 알고리즘에 대해서만 이야기 하자면, 자릿수가 짝수개 있는 정수를 입력 받으면 해당 정수의 자릿수를 둘로 나눴을 때 왼쪽에 있는 자릿수와 오른쪽에 있는 자릿수를 더했을 때 그 값이 같을 경우는 "LUCKY" 를 출력한다. 아닐 경우는 "READY"를 출력한다. 문제 조건을 보니 입력을 int형으로 받기 때문에 이를 배열 형태로 바꿔야하는 경우가 생겼다. 파이썬의 경우는 int형을 문자열 배열로 바꿔주는 기능이 있..

https://www.acmicpc.net/problem/2798 📌 문제 블랙잭 규칙인 카드의 합이 21을 넘지 않는 한도 내에 카드의 합을 최대한 크게 만드는 게임이다. N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력한다. 해당 문제는 완전탐색으로 모든 경우의 수를 다 찾으면 된다. 문제의 특이점은 꼭 3장을 골라야한다는 점이다. 그래서 중첩 루프문을 3개 겹쳐서 3개를 고른 모든 경우의 수를 탐색하면 된다. 참고로 재귀함수를 사용한 완전탐색일 경우 시간초과로 인해 문제를 풀지 못한다. 알고리즘 문제 풀이는 대부분 시간 싸움이기 때문에 재귀함수는 그래서 되도록이면 사용하지 않는 것이 좋다. 재귀함수는 말 그대로 함수를 꼬리가 꼬리를 물..