문제 https://algospot.com/judge/problem/read/POTION algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 algospot.com 풀이 유클리드의 최대공약수 알고리즘을 활용하는 문제이다. 해당 문제에서 다른 건 몰라도 한 가지 확실한 것은 (이미 넣은 재료양)/(레시피 재료 양)의 비가 최대인 것보다 크거나 같은 크기의 약을 만들어야 한다는 것이다. 이러한 비를 already_put / recipe (최대비)라고 나타내 보자. 이보다 크거나 같은 비는 k/b(넣을 약의 비)라고 나타내면 아래와..

문제 https://algospot.com/judge/problem/read/STRJOIN algospot.com :: STRJOIN 문자열 합치기 문제 정보 문제 프로그래밍 언어 C 의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C 에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자 algospot.com 풀이 종만북 난이도: 중 난이도는 중인 그리디 문제이지만 C++ STL의 우선순위 큐(priority_queue)와 같은 컨테이너 라이브러리를 안다면 쉽게 해결할 수 있다. 일단 예를 들어 4개의 문자열(str1, str2, str3, str4)을 순서대로 합친다고 생각해보자. 첫번째로 합쳐진 문자열의 길이는 len1(str1+str2), 두번째는 l..

문제 https://algospot.com/judge/problem/read/POLY algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 풀이 종만북 난이도: 중 폴리오미노 중에서도 세로로 단조인 것의 개수를 구해야 하는 문제. 일단 폴리오미노는 한 변이라도 붙어이어야 하기 때문에 모든 정사각형은 이어저 있어야 한다. 또한 세로로 단조이기 위해서는 같은 세로줄이라면 모두 이어져야 한다. 따라서 위의 세로줄부터 num개의 사각형을 이어 붙이고 남은 사각형(remain_squ)으로 다음 세로줄을 몇 개의 사..

문제 https://algospot.com/judge/problem/read/ASYMTILING algospot.com :: ASYMTILING 비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 algospot.com 풀이 이전 문제인 타일링 문제를 풀고 오자. 타일링 문제는 아래의 점화식으로 간단히 해결이 가능하다. cache_tiling[i] = cache_tiling[i-1] + cache_tiling[i-2] 이번 문제는 이러한 타일링의 수에서 대칭으로 놓인 경우의 수를 빼주면 된다. 대칭이 가능한 경우는 크게 두 가지로 나누어진다. 1. n이..

문제 algospot.com/judge/problem/read/TRIPATHCNT algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com 풀이 종만북 난이도: 중 난이도는 중인 DP문제이지만 이전 단계를 풀었다면 쉬운 문제이다. 일단 이전 단계 문제인 삼각형 위의 최대 경로를 풀고오자. 최대 경로의 값을 구하는 문제는 아래와 같은 재귀함수로 해결이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 int TriMaxSum(int r,int c){ int& ret = cache..

문제 https://algospot.com/judge/problem/read/QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일 algospot.com 풀이 종만북 난이도: 중 1000이하의 자연수로 이루어진 수열을 S종류의 1000이하의 정수 값을 사용하여 양자화할 때, 오차 제곱의 합의 최솟값을 구하는 문제이다. 1~1000까지의 모든 수에서 10가지만 선택하는 조합의 경우의 수만 해도 너무나 크다. 따라서 미리 사용할 S(quan_num)개의 수를 선택해서 모든 값과 ..

문제 https://algospot.com/judge/problem/read/JLIS] algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 풀이 일단 이전 단계 문제인 LIS(최장 증가 부분 수열) 문제를 확인하고 옵시다. LIS보다 까다로워진 문제입니다. 단순히 생각했을 때 두 수열의 LIS의 길이를 더하면 된다고 생각할 수 있지만 1 4 9 4 -> lis length: 3 3 4 4 7 -> lis length: 3 위의 예제에서는 JLIS는 1 3 4 7 9인 5이지만 각각의 ..

문제 algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 풀이 대표적인 DP문제 중 하나인 최대 증가 부분 수열(LIS, Longest Increasing Sequence)을 구하는 문제이다. 단순히 아래의 예제에서 모든 경우의 수를 찾는다고 생각해보자. 1 5 4 3 4 6 7 1번째 수, 1에서부터 재귀 함수로 LIS를 찾는다고 가정하면 1보다 큰 모든 수를 하나하나..

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

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