Don't die there

문제 링크 https://algospot.com/judge/problem/read/POLY algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 세로로 단조인 폴리오미노는 각 행의 사각형들이 모두 연속해서 붙어있어야 합니다. 같은 행에서 사각형들 사이에 공간이 있으면 안된다는 것을 의미합니다. 이 형태의 폴리오미노를 구하기 위해서는 첫 번째 행부터 내려가면서 각 행에서 사각형을 놓을 수 있는 모든 방법을 세어주면 됩니다. n이 3일 때 첫 번째 행에 올 수있는 사각형은 1, 2, 3개로 총 3가지 경우가 ..

문제 링크 https://algospot.com/judge/problem/read/SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 � algospot.com 1. 현재날짜+1에서 한칸 더 올라가는 경우 * 0.25 2. 현재날짜+2에서 두칸 더 올라가는 경우 * 0.75 두가지 경우를 더해주면 값을 구할 수 있습니다. 구현 코드

문제 링크 https://algospot.com/judge/problem/read/TRIPATHCNT algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 � algospot.com 이전의 삼각형 위의 최대 경로 문제에서 연장되는 문제입니다. 이전 문제로 각 위치에서의 최대 경로를 아래 오른쪽과 같이 구할 수 있습니다. 이렇게 구하고난 경로 값을 이용해서 1. 현재 위치에서 한칸 아래 위치 2. 현재 위치에서 오른쪽 한칸 아래 위치 두 값중 더 큰쪽이 항상 최대 경로가 됩니다. 이 때 두 값이 동일하..

문제 링크 https://algospot.com/judge/problem/read/TILING2 algospot.com :: TILING2 타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있 algospot.com 백준 11726 문제와 동일한 타일링 문제입니다. 구현 코드

문제 링크 https://algospot.com/judge/problem/read/QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일� algospot.com 양자값과의 오차의 제곱을 구할 때 숫자마다 하나씩 양자값을 구하고 오차를 계산하는 것이 아닌 정렬된 숫자들을 적절하게 그룹으로 묶어서 각 그룹을 한 숫자로 표현해서 값을 찾아냅니다. s개의 자연수를 사용해 양자화를 해야 하는데 숫자가 낮은 값에 낮은 s를 사용하고 높은 수에 비교적 더 높은 s를 사용해야 오차를 줄일 ..

문제 링크 https://algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 두 배열을 하나의 배열처럼 놓고 모든 부분 수열을 확인해야하기 때문에 첫 번째 배열과 두 번째 배열의 현재 위치 인덱스를 사용해 첫 번째 배열부터 순서대로 탐색해나갑니다. 첫 번째 배열에서 다음 값이 현재 값보다 크면 첫 번째 배열의 다음 인덱스와 두 번째 배열의 현재 인덱스로 재귀함수를 탐색해나갑니다. 두 번째 배열도 마찬가지로 다음 값이 현..

문제 링크 https://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 동일한 문제가 백준에도 있지만 종만북에서는 이 문제를 동적계획법과 이분법으로 해결하는 두가지 방법을 설명합니다. 먼저 이분법 방식부터 살펴보면 먼저 입력으로 주어진 길이와 동일한 빈 배열 c를 만들어줍니다. 그리고 a의 첫번째 값부터 시작하여 c에 아무 값이 없거나 가장 최근에 들어온 값이 a의..

문제 링크 https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 �� algospot.com 삼각형 가장 위쪽의 위치에서 최대경로는 1. 현재위치에서 한칸 아래 위치 2. 현재위치에서 오른쪽 한칸 아래 위치 두 가지 위치의 최대 경로 중 큰값에 현재 위치의 값을 더해주면 됩니다. 구현 코드