📍유사 문제 2023.01.13 - [⚙️알고리즘 & 자료구조/BOJ] - 백준 9655 JavaScript 백준 9655 JavaScript 📍문제 링크 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 📍알고리즘 분류 - 수학 - 다이나믹 프로그래밍 - 게임 ggarden.tistory.com 📍문제 링크 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래..

📍문제 링크 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 📍알고리즘 분류 - 수학 - 다이나믹 프로그래밍 - 게임이론 📍문제 풀이 두 사람 A, B가 게임을 하는데 N개의 돌 중에 1, 3개를 택해서 가져갈 수 있다. 마지막에 가져가는 사람이 이긴다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람은 누구일까? 🤔완벽하게 게임을 했을 때? - 이길 수 있는 상황에서 게임을 이기는 것. 확실한 finish로 시행 횟수를 최소화 하는 것! - 예) N = 7, A, B가 플레이어 A B A 1 3 3(무조건 3을 냄, 1을 내지 않음) 일단 A가 이긴다는 것은 진..

📍문제 링크 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 1️⃣피보나치 수열임을 파악하기 - 1 2 3 4 5.. N 의 N명이 양 옆으로만 움직일 수 있을 때 가짓수는 피보나치 수열 fib(N)과 일치 - 즉, fib(N) = fib(N - 2) + fib(N - 1) 그 이유는, N번째 사람이 N 자리일 수 있고, N-1 자리일 수 있는데, i) N 자리이면 N-1명의 가짓수인 fib(N-1)에 해..

📍문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 그래프 이론 - 그래프 탐색 - 트리 - 깊이 우선 탐색 - 트리에서의 다이나믹 프로그래밍 📍문제 풀이 트리와 이차원 배열이 주어진다. 이차원 배열은 [정점 번호, 숫자] 형태의 원소를 갖고 있다. 이차원 배열을 순회하며, 정점 번호에 해당하는 정점의 모든 자식 노드에 숫자를 더해주면 된다. - DFS를 사용하는 이유 사실 어차피 모든 그래..

📍문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 수의 길이가 주어질 때, 계단 수의 총 가짓수를 구하라 - 계단 수 : 12345, 10101 처럼 각 자릿수가 1씩 증감하는 수 - 이차원 배열 memo가 있고 - row : N - column : 맨 마지막 숫자 일때, N=2 까지 아래와 같은 2차원 배열을 만들 수 있다 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 N = 2 일때, - 마지막 숫자가 1인 경우는 memo..

📍문제 링크 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 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 가장 긴 증가하는 부분수열 : LIS (Longest Increasing Subsequence) 알고리즘으로 알려져 있다 - DP를 사용하여 해결한다 - 비슷한 문제가 많은 시리즈 문제 - LIS의 길이만 다루면 됨 - memo 배열을 data[n] 까..

📍문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - DP를 문제에 적용한다는 것은 메모이제이션이 활용된다는 것을 의미한다. - 이 문제에 메모이제이션을 적용하려면, n=1, 2 ... 커질 때, n=1 일 때의 값이 n=2 일 때 활용되도록 하면 된다. 5 3 최댓값 5 5 1 3 5 최댓값 10 (5+5) 5 1 10 3 5 4 최댓값 20 (5+5+10) 그런데, 이..

📍문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 문자열 📍문제 풀이 - 다이나믹 프로그래밍(DP) 관련해서 유명한 문제 - X, Y 두 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구해보자 예시) LCS(X,Y) = B C B A _ _ _ _ A B C B D A B _ _ _ _ B D C A B A - 단순 무식하게 브루트 포스 ..