문제 링크:https://www.acmicpc.net/problem/1504문제 상황오늘 해결한 문제는 방향성이 없는 그래프에서 특정한 두 정점을 반드시 거치는 최단 경로를 찾는 문제였습니다. 주어진 그래프는 NNN개의 정점과 EEE개의 간선으로 구성되며, 출발점(1번 정점)에서 도착점(NNN번 정점)까지 이동하는 경로 중 V1V1V1과 V2V2V2라는 특정 정점을 반드시 통과해야 했습니다. 이때 최단 경로의 길이를 구하는 것이 목표였습니다.제약 조건:간선이 없는 경우 또는 특정 경로가 없는 경우 결과는 −1-1−1을 출력.정점은 최대 800개, 간선은 최대 200,000개로 매우 큰 입력을 처리해야 함.문제 원인문제를 해결하면서 겪은 주요 문제점은 다음과 같습니다:간선이 없는 경우에 대한 예외 처리 부..

문제 링크https://www.acmicpc.net/problem/1253 문제 상황"좋은 수"를 찾는 문제는 주어진 N개의 수 중에서 어떤 수가 다른 두 수의 합으로 나타낼 수 있는지를 판별하는 것입니다. 초기 구현에서는 두 포인터(Two Pointers) 알고리즘을 활용했지만, 몇 가지 문제로 인해 예상한 대로 동작하지 않았습니다문제 원인현재 값을 포함한 계산 문제: 검증 대상 숫자 val 자체를 두 포인터 탐색에서 포함하여 계산한 경우가 있었습니다. 같은 숫자라도 인덱스가 다른 경우만 유효하므로, 이를 제외할 처리가 필요했습니다.벡터 초기화 문제: 고정 크기 배열을 사용하여 불필요한 메모리를 할당했으며, 입력 크기에 맞게 동적으로 초기화하지 않았습니다.Search 함수의 비효율적 구조: 두 포인터 ..

문제 링크 : https://www.acmicpc.net/problem/11657 풀이 과정알고리즘 선택: 벨만-포드 알고리즘벨만-포드 알고리즘은 다음 특징을 가진다:음수 가중치를 포함한 그래프에서도 최단 경로를 계산할 수 있다.음수 사이클이 존재하는 경우 이를 탐지할 수 있다.핵심 아이디어:N−1N-1N−1번 간선 완화를 수행하여 최단 거리를 계산한다.NNN-번째 간선 완화를 추가로 실행하여, 값이 갱신되면 음수 사이클이 존재한다고 판단한다.문제 상황음수 사이클이 정상적으로 동작하지 않아 " 출력 초과 " 메세지가 나옴 문제 원인음수 누적에 따른 정수 오버플로우 발생가중치의 범위가 −10,000≤C≤10,000-10,000 \leq C \leq 10,000−10,000≤C≤10,000으로 충분히 크며,..

문제 링크 :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..