꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1017 소수 관련된 문제이므로 에라토스테네스의 체와 이분 매칭을 통해 풀 수 있는 문제였습니다.저도 처음에 백트래킹으로 접근했다가 TLE가 발생했던 문제입니다 ㅠ 알고리즘은 다음과 같습니다.1. nums[0]과 합쳤을 때 소수를 이루는 nums[i]를 매칭합니다.2. 남은 수들로 이분 그래프를 만드는데 왼쪽 집합은 홀수인 수들, 오른쪽 집합은 짝수인 수들로 구성하며 간선은 두 수의 합이 소수일 때 연결시킵니다.3. 이분 그래프에서 최대 매칭을 찾아서 모든 노드가 매칭에 포함되는지 확인합니다.3.1 매칭의 크기가 남은 노드의 절반이라면 모든 수를 짝지을 수 있다는 의미입니다.  개발환경:Visual Studio 2017 지적, 조..

문제 링크입니다: https://www.acmicpc.net/problem/27989 맥스 펜윅 트리를 활용하는 문제였습니다. 알고리즘은 다음과 같습니다.1. cache는 수열 A를 오름차순으로 정렬한 배열입니다.2. 수열 A를 순회하며 이분탐색을 통해 현재 A[i]가 cache에 위치한 인덱스를 찾습니다.2.1 +1을 하는 이유는 A는 0-인덱스인 반면 펜윅 트리는 1-인덱스이기 때문입니다.3. A[i]보다 작은 모든 값들에 대해 현재까지 계산된 최대 부분합을 구합니다.4. 3번에서 구한 값과 A[i]를 합치면 현재 인덱스까지의 최대 부분합을 구할 수 있습니다. 해당 값을 펜윅 트리의 idx 위치에 업데이트합니다.5. 2 ~ 4번 과정을 반복한 뒤 N번째 인덱스에 대해 쿼리를 수행하면 답을 구할 수 있..

문제 링크입니다: https://www.acmicpc.net/problem/1344 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 구간, A팀 득점 수, B팀 득점 수임을 유추할 수 있습니다.따라서 세 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/17837 문제에서 주어진 대로 풀면 되는 문제였습니다.저는 같은 칸에 여러 개의 말이 위치할 수 있고 쌓인 순서를 토대로 로직이 달라질 수 있기 때문에 stack 자료구조를 사용하여 말이 쌓인 순서를 표현했습니다,. * moveDir[4]를 {1, 0}이 아닌 {0, 1}로 해놓고 맞왜틀 이러고 있었네요... 아까운 내 시간 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1535 전형적인 Knapsack DP 문제였습니다.세준이의 체력이 0이어도 기쁨을 못 느낀다는 것이 핵심이었습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1513 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 현재 위치(y, x), 방문한 오락실 개수, 그리고 직전에 방문한 오락실 번호임을 유추할 수 있습니다.따라서 네 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/12865 전형적인 Knapsack DP 문제였습니다.주의할 점은 동전 2 문제와 달리 각 물건은 하나씩 존재한다는 점입니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/12852 연산을 하는 횟수의 최솟값은 DP를 통해 간단하게 구할 수 있는 문제였습니다.문제는 " N을 1로 만드는 방법에 포함되어 있는 수"를 출력하는 것이었는데 이는 DP에 사용했던 cache 배열을 역추적하며 구할 수 있었습니다.테스트해 본 결과 top-down 방식으로 구현할 경우 N이 100만 일 때 stackoverflow가 발생하는 것 같은데 AC를 받는 것으로 보아 데이터 추가가 필요해 보입니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/4811 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 한 조각인 알약 개수와 반 조각인 알약 개수임을 유추할 수 있습니다.따라서 두 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.   개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1103 문제 조건대로 풀면 되는 백트래킹 + DP 문제였습니다.중간에 있는 구멍은 무시한다는 조건이 있기 때문에 동전을 한 칸 한 칸 움직이지 않고 한 번에 이동해도 무방했습니다.   개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~