문제 링크 :https://www.acmicpc.net/problem/11054문제 개요주어진 수열에서 특정 숫자를 기준으로 증가하다가 감소하는 바이토닉 수열의 부분 수열 중 가장 긴 수열의 길이를 구하는 문제입니다.접근 방법이 문제는 **DP(동적 계획법)**을 활용하여 해결합니다. 1. 문제 분할바이토닉 수열은 두 가지 부분으로 나뉩니다:증가하는 부분 수열(LIS): 왼쪽에서 오른쪽으로 증가.감소하는 부분 수열(LDS): 오른쪽에서 왼쪽으로 감소.2. 점화식LIS[i]: 왼쪽에서 오른쪽으로 진행하며 A[i]를 포함한 가장 긴 증가 수열의 길이.LDS[i]: 오른쪽에서 왼쪽으로 진행하며 A[i]를 포함한 가장 긴 감소 수열의 길이.3. 바이토닉 수열 길이 계산dp[i]=LIS[i]+LDS[i]−1 (−..

문제 링크 : https://www.acmicpc.net/problem/9461📝 문제 요약문제: 삼각형이 나선 모양으로 배치된 파도반 수열에서, 주어진 N번째 숫자를 구하는 문제.입력:테스트 케이스의 개수 T (1 ≤ T ≤ 100)각 테스트 케이스에서 N (1 ≤ N ≤ 100)출력: 각 테스트 케이스마다 P(N) 출력.📌 접근법1. 파도반 수열의 정의점화식: P(N) = P(N-3) + P(N-2) (단, N > 3)초기값: P(1) = 1, P(2) = 1, P(3) = 1첫 몇 개의 값은 다음과 같습니다:P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2, P(6) = 3, P(7) = 4, ... 2. 사전 계산 (Dynamic Programming)점화..

문제 링크https://www.acmicpc.net/problem/11055 📝 문제 요약문제: 주어진 수열에서 순서를 유지하면서 숫자가 점점 커지는 부분 수열 중, 합이 가장 큰 부분 수열의 합을 구하는 문제.입력:수열 크기 N (1 ≤ N ≤ 1,000)수열 A (1 ≤ Ai ≤ 1,000)출력: 가장 큰 증가하는 부분 수열의 합.📌 접근법1. DP 배열 정의dp[i]: i번째 숫자를 마지막으로 하는 가장 큰 증가 부분 수열의 합을 저장합니다.2. 점화식조건:arr[j] 점화식:dp[i] = max(dp[i], dp[j] + arr[i])3. 초기화각 숫자는 혼자만으로 합이 되는 증가 부분 수열을 만들 수 있으므로, dp[i] = arr[i]로 초기화합니다.4. 결과 계산DP 배열을 모두 계산한 ..

문제 링크https://www.acmicpc.net/problem/11722📝 문제 요약문제: 주어진 수열에서 순서를 유지하면서 숫자가 점점 작아지는 부분 수열 중 가장 긴 수열의 길이를 구하는 문제.입력:수열 크기 N (1 ≤ N ≤ 1,000)수열 A (1 ≤ Ai ≤ 1,000)출력: 가장 긴 감소하는 부분 수열의 길이.📌 접근법1. DP 배열 정의 dp[i]: i번째 숫자를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장합니다. 2. 점화식조건: arr[j] > arr[i] (j 점화식: dp[i] = max(dp[i], dp[j] + 1)3. 초기화각 숫자는 혼자만으로 길이 1의 감소 수열을 만들 수 있으므로, dp[i] = 1로 초기화합니다.4. 결과 계산DP 배열을 모두 계산한..

문제 링크:https://www.acmicpc.net/problem/9655 📝 문제 요약두 명의 플레이어가 번갈아가며 돌을 가져가는 게임입니다.돌은 한 번에 1개 또는 3개씩 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 승리합니다.상근이가 먼저 시작하며, 두 플레이어는 항상 최적의 전략으로 게임을 진행합니다.입력으로 주어진 돌의 개수 N(1 ≤ N ≤ 1000)에 따라 승자를 구합니다.📌 접근법1, 게임의 성질 파악:현재 돌의 개수 i에서 돌을 가져가면 남은 돌의 개수는 i - 1 또는 i - 3입니다.상대가 남은 돌의 개수로 패배하는 경우라면 현재 플레이어가 승리합니다.2, DP (동적 계획법) 사용:dp[i]: 돌이 i개 남았을 때 이기는 사람을 나타냄.true: 상근이(SK)가 이김.fal..

문제 링크 : https://www.acmicpc.net/problem/2116 문제 요약이 문제는 여러 개의 주사위를 쌓아 옆면 숫자의 합이 최대가 되도록 하는 문제입니다. 주사위를 쌓을 때 다음 규칙을 지켜야 합니다:각 주사위의 아래면 숫자는 바로 아래 주사위의 윗면 숫자와 같아야 합니다.주사위는 회전할 수 있지만, 위아래 위치는 고정됩니다.옆면의 숫자 중 가장 큰 값을 선택하여 합을 계산합니다.문제는 옆면 숫자의 합의 최대값을 구하는 것입니다.문제 해결 접근법1. 주사위의 위/아래 면 설정주사위의 각 면은 A,B,C,D,E,FA, B, C, D, E, FA,B,C,D,E,F로 표현됩니다.아래 면과 윗면의 관계는 다음과 같습니다:A(0)↔F(5)B(1)↔D(3)C(2)↔E(4)아래 면의 값을 기준으로..

문제 링크:https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약이 문제는 주어진 송전탑과 전선 정보에서, 전선 하나를 끊어 두 전력망으로 나누었을 때 송전탑 개수의 차이가 최소가 되도록 하는 것입니다.문제의 주요 조건:입력으로 주어진 송전탑 네트워크는 항상 트리 구조입니다.전선 하나를 끊으면 두 전력망으로 분리됩니다.송전탑의 개수를 비교해 그 차이를 최소화해야 합니다.문제 해결 접근법1. 그래프를 인접 리스트로 표현전선으로 연결된 송전탑 관계를 그래프의 형태로 나타냅니다.인접 리스트를 사..

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약이 문제는 주어진 숫자 조각들로 만들 수 있는 모든 숫자 조합 중 소수가 몇 개인지 찾는 것입니다. 문제를 해결하기 위해:숫자 조각들로 만들 수 있는 모든 가능한 조합을 생성.각 조합이 소수인지 판별.중복된 숫자를 제거하여 유일한 소수의 개수를 계산.제약 조건:입력 문자열의 길이는 최대 7이므로 완전 탐색이 가능.숫자 조합의 순서와 길이를 고려해야 함.문제 해결 접근법1. 모든 조합 생성 (완전 탐색)숫자 조각으로 만들 수..