알고스팟 (7) 썸네일형 리스트형 [동적계획법테크닉] 3. 광학 문자 인식 컨셉 1. A라고 인식한 단어가 B일 확률 == B인데 A라고 인식할 확률. - 이유: 다음 표를 보자. (X → Y : X인데 Y로 인식할 확률) X(실제)＼Y(인식) A (인식) B C A (실제) 0.5 0.2 0.3 B 0.1 0.7 0.2 C 0.3 0.0 0.7 예) 실제 A인데 B로 인식할 확률 = 0.2 / B로 인식했는데 실제론 A일 확률 = 0.2 실제론 X인데 Y로 인식할 확률(X를 보고 →Y찾기)이나, Y로 인식했는데 실제론 X일 확률이나(Y를 보고 X를 찾기) 같다. 2. OCR(index, real) //인식한 index번째 단어가 사실은 단어 real일 확률 OCR(index, real) = ∑ OCR(index-1, 단어 i) * (단어 i 다음에 단어 real이 올 확률) .. [동적계획법] 12. 폴리오미노 폴리오미노 https://algospot.com/judge/problem/read/POLY algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다. 예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 algospot.com 컨셉 폴리오미노를 만드는 문제를 두 단계로 나눴다. 1. 사각형 배분하기 2. 사각형 위치잡기 윗줄에.. [동적계획법] 10.달팽이 우물을 기어오르는 달팽이(예제)를 응용한 '장마가 찾아왔다' https://algospot.com/judge/problem/read/SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. 여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하 algospot.com 책과 홈페이지에 나온 문제가 약간 다르다!! 책.. [동적계획법] 9. 삼각형 위의 최대 경로 수 https://algospot.com/judge/problem/read/TRIPATHCNT algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9, algospot.com 컨셉 초안 내 코드 (정답, 24ms) ...더보기 /** * @name 8.11. 삼각형 .. [동적계획법] 8. 타일링 방법의 수 https://algospot.com/judge/problem/read/TILING2 algospot.com :: TILING2 타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. 경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요. 입력 입력의 첫 줄에는 테스트 케이스의 수(C N; cout [동적계획법] 7. Quantization https://algospot.com/judge/problem/read/QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이고, 키가 161, 164, 170, 178 인 학생 넷을 '160대 둘, 170대 둘' 이라고 축약해 표현하는 것 또한 양자화라고 할 algospot.com 컨셉 1. 숫자 오름차순 정렬 2. 숫자 몇개씩 묶음 3. 묶은 뭉텅이 내부에서 양자화 초안 내코드.. [동적계획법] 3. 삼각형 위의 최대 경로 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 컨셉 점화식을 만들었다. path(y,x) //(y,x)에서 시작하여 맨 아래줄까지.. 이전 1 다음
