문제 www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 해당 문제는 다이나믹 프로그래밍 문제이다. 본인의 경우 여기에 BFS기법을 추가해서 문제를 해결했다. 일단 입력으로 받는 동전의 값이 10,000 이하의 수 일 때만 coin_value에 그 값을 저장한다. 가치의 합은 최대 10,000이기 때문에 그 이상의 값은 문제를 해결하는데 전혀 도움이 되지 않기 때문이다. 이후 coin_value를 정렬하고 BFS를 구현한다. ..

문제 https://algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 풀이 다이나믹 프로그래밍 문제이지만, 단순히 메모이제이션을 적용할 수 없어서 어려웠다. 풀이는 알고리즘 문제 해결 전략(일명 종만북)을 참조하였다. 와일드 카드(wild_card)와 파일명(file_name)을 한 글자씩 비교하여 진행할 경우 글자가 같은 경우와 와일드 카드의 ? 문자는 다음 칸으로 넘어가는 것으로 간단히 구현이 가능하다. 하지만 와일..

문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍 문제이므로 일단 직관적인 top-down 방식으로 풀어보았다. 메모이제이션을 위한 배열 max_stair[300][2] 선언하는데 2차원으로 선언하는 이유는 해당 위치가 직전 계단과 연속되는지를 저장하기 위해서이다. max_stair[ ][ 0 ] 에는 두 계단을 뛰어 연속되는 계단이 없는 경우를, max_stair[ ][ 1 ] 에는 한 계단만 올라가 이전의 계단과 연속되는 경우를 저장한다...

문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 전형적인 다이나믹 프로그래밍 문제이다. 이런 문제의 특징인 부르트 포스로 모두 계산하기에는 경우의 수가 너무 많다. 이러한 경우의 수들 중 중복계산을 수도 없이 호출하기 때문에 우리는 계산된 값들을 저장하여 최적화를 할 수 있다. 해당 문제에서 모든 집들을 단순히 3가지 색으로 칠하는 경우의 수는 3^1000 이므로 시간 초과가 발생한다. 하지만 메모이제이션으로, 해당 순서의 집..

다이나믹 프로그래밍 문제 모음 *해당 난이도 분류는 작성자의 주관적인 생각입니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. DP 연습 문제 [알고스팟] 외발 뛰기(JUMPGAME) [백준] RGB거리(1149) [백준] 계단 오르기(2579) + bottom-up 구현해보기 [백준] 내리막 길(1520) + Dfs가 결합된 문제 [백준] 동전 2(2294) + bfs 사용없이 풀기 [백준] 1학년(5557) [백준] 격자상의 경로(10164) + 실수 주의 [백준] 기타리스트(1495) [백준] 수열(2491) [알고스팟] 삼각형 위의 최대 경로 수 세기(TRIPATHCNT) [알고스팟] 비대칭 타일링(ASYMTILING) [백준..

문제 https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com 풀이 간단한 다이나믹 프로그래밍 문제 해당 위치에서 끝에 도달이 가능한지의 여부를 is_pos_board에 저장해두어 중복된 호출을 방지하여 최적화한다. 해당 위치의 도달 여부가 기록되어있다면 바로 그 값을 반환하고 아니라면 왼쪽과 오른쪽으로 이동하는 경우를 재귀호출하여 반환된 값을 기록한다. 코드

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 문제마다 이를 구현하는 방식을 제각각이고 고난이도 문제가 많은 편이다. 문제 목록 [LeetCode] Two Sum + 스위핑 기본 문제 [LeetCode] 3Sum+ Two Sum 변형 문제 [백준] 선 긋기(2170) + 스위핑 기본 문제 - Gold 5 [백준] - 철로(13334)★ - Gold 2 [백준] 개구리 점프(17679) + 분리 집합 - Gold 3 [백준] - 버스 노선(10165)★ + 그리디 - Platium 5 슬라이딩 윈도우 [L..

문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 풀이 해당 문제는 -1,000,000,000 이상 1,000,000,000 이하의 범위를 가지는 선들이 주어진다. 따라서 이를 단순히 20억 개의 배열에 저장해서 표현하기에는 메모리 제한으로 불가능하며 비효율적이다. 이 문제는 스위핑 알고리즘 대표적인 문제로 아래와 같은 방법으로 해결 가능하다. 해당 문제에서 일단 배열 points에 입력을 받고 선의 시작 부분을 기준..

문제 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 행렬 A의 제곱 수인 B는 최대 100,000,000,000의 값을 가지기 때문에 단순히 A를 반복해 곱하는 것은 시간 초과를 발생시킨다. 이와 같이 입력값이 너무 큰 경우 분할 정복을 떠올리자. 제곱 수를 pow_num이라고 하면 pow_num %2 ==1 인 경우, 즉 홀수라면 A^(pow_num-1) * A를 짝수라면 A^(pow_num/2) * A^(pow_num/2) 로 계산한다면 제곱 연산을 O(logB..

문제 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 풀이 간단한 분할 정복 문제. 대체로 분할 정복 문제들은 입력이 굉장히 큰 경우가 많아 브루트 포스로 접근하면 시간 초과가 발생한다. 해당 문제도 최대 3^7의 큰 입력을 받는다. 행렬은 항상 같은 크기인 9개의 종이로 자르기며 재귀호출을 하기 아래와 같은 기저 사례가 필요하다. 기저 사례: 잘라진 크기가 1인 경우 해당 origin_paper[row][col] 값을 바로 반환한다. 위의 기저 ..