본문 바로가기

알고리즘

 (10)
[2017 카카오 예선] 보행자 천국 2017 카카오코드 예선 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 | 프로그래머스 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 컨셉 고등학교 때 했던 수학문제. 간 단 쓰. way[i][j] //(i,j)까지 갈 수 있는 방법의 수 way[i][j] = way[i-1][j] + way[i][j-1] //위에서 오는 방법의 수 + 왼쪽에서 오는 방법의 수 단, 직진코스(city_map 값이 2인 경우)이 있는 경우는 조금 다르다. - 직진인..
[동적계획법테크닉] 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이 올 확률) ..
[동적계획법 테크닉] 2. 여행 짐 싸기 컨셉 int packing(int index, int capacity) //capacity만큼 용량이 남은 경우, item[index]부터 짐을 쌌을 때 가능한 최대 절박도를 리턴한다. //packing(index,capacity) = item[index]를 짐에 넣은 경우, 안 넣은 경우 중 절박도가 큰 것 packing(index, capacity) = MAX(packing(index+1, capacity) , packing(index+1, capacity - items[index].volume); 초안 내가 쓴 코드(정답, 12ms) ...더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32..
[동적계획법] 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)에서 시작하여 맨 아래줄까지..

티스토리툴바