동적 계획법 (28) 썸네일형 리스트형 [알고스팟] 실험 데이터 복구하기 RESTORE [알고스팟] 웨브바짐 ZIMBABWE클릭시 이동합니다! 웨브바짐문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)ZIMBABWE2000ms65536kb842354 (42%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러!계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르기 때문에 물건의 가격을 실시간으로 바꿔야 합니다. 웨브바짐에서 가장 큰 무가베 마트에서는 그래서 위와 같이 빈 칸만 쓰여 있는 광고판을 붙여놓고 계란 가격이 오름에 따라 (정확히는 웨브바짐 달러의 가치가 추락함에 따라) 실시간으로 숫자가 크게 적힌 플라스틱 판을 빈 칸에 갈아 끼웁니다. .. [알고리즘] 동적 계획법(dynamic programming) - 5 오랜만에 쓰는 알고리즘 글입니다!요즘 뭔가 하고싶은 일이 많다보니 알고리즘을 조금 줄이게 됐네요!종만북 1권도 도대체 언제 끝낼지 모르겠습니다 후덜덜;; 각설하고 이제 동적 계획법에 대해서 설명하겠습니다! 오늘은 정수 이외의 입력에 대해서 어떻게 메모이제이션을 할 것인가? 에 대해 알아보겠습니다! 지금까지는 메모이제이션에 사용되는 값이 정수였습니다!하지만, 가끔씩 메모이제이션에 사용해야 하는 값이 문자열이거나 배열인 경우가 있습니다. 이런 경우에는 어떻게 메모이제이션을 해야할까요!? 첫번째로는 STL의 힘을 빌리는 방법이 있습니다.C++ STL에는 map과 vector라는 아주 훌륭한 stl이 있기 때문에 다음과 같이 메모이제이션을 사용할 수 있습니다. map memoi STL의 컨테이너는 자체적인 대소.. [알고스팟] k번째 최대 증가 부분 수열 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)KLIS2000ms65536kb2297484 (21%)출제자출처분류JongMan연습문제보기문제어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9의 부분 수열이 아니다.어떤 부분 수열이 _단조 증가_할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 하며, 이 중 가장 긴 것을 최대 증가 부분 수열 (LIS, longest increasing subsequence) 라고 한다. 예를.. [알고스팟] 모스 부호 사전 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)MORSE2000ms65536kb2281641 (28%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 들어 알파벳 J는 모스 부호 o---로 표현되고, M은 --로 표현됩니다.n개의 장점과 m개의 단점으로 구성된 모든 신호들을 담고 있는 사전이 있다고 합시다. 예를 들어 n = m = 2라면 다음과 같은 신호들이 포함되어 있는 것이죠.--oo -o-o -oo- o--o o-o- oo--이 신호들은 사전순서대로 정렬되어 있습니다. -의 아스키 코드.. [알고리즘] 동적 계획법(dynamic programming) - 4 오늘은 알고리즘 동적 계획법 4번째를 설명하도록 하겠습니다!진짜 동적 계획법 엄~~~청 길어서 거의 10까지 할 것 같아요. 이번 동적 계획법에서는 k번째 답을 계산할때 쓰는 방법입니다! 예를 들면, 한 배열에서 LIS들은 한 가지 방법만 있는 것이 아닙니다.가능한 LIS들을 사전순으로 나열한다고 할 때, k번째 LIS를 구하려면 어떻게 해야할까요? 우선, 사전순으로 개수를 세는 알고리즘을 만드는 경우를 생각해 봅시다. 1번째 답으로 올 수 있는 경우가 3개 있다고 합시다. 그럼, 경우 1에서 만들어 질 수 있는 수가 n1개 있을것이고,경우 2에서 만들어질 수 있는 경우의 수가 n2개 있을 것 입니다. 하지만, 만약 경우 1에서 만들어질 수 있는 수가 k개 보다 작으면 어떨까요?그럼, 경우 1의 경로를 .. [알고스팟] 광학 문자 인식 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)OCR60000ms65536kb1203292 (24%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제알림: 채점 서버 속도 문제로 시간 제한을 60초로 늘리고, 테스트 케이스 수를 20으로 줄입니다.광학 문자 인식(Optical Character Recognition)은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정을 말합니다. OCR 알고리즘들은 대개 수많은 필기 샘플을 통계적으로 분석하고 패턴을 찾아내어 각 단어들을 인식하곤 합니다. 하지만 단순히 각 단어들을 개별적으로 인식하기보다, 단어의 분포나 문법 등을 고려하면 더 나은 결과를 얻을 수 있는 경우가 많습니다... [알고스팟] 여행 짐 싸기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PACKING2000ms65536kb41941145 (27%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.물건노트북 컴퓨터카메라XBOX365커피그라인더아령백과사전부피4264210절박도7106754캐리어의 용량이 정해져 있기 때문에 가져갈.. 이전 1 2 3 4 다음
