공부/알고리즘 문제풀이 (96) 썸네일형 리스트형 [알고스팟] 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--이 신호들은 사전순서대로 정렬되어 있습니다. -의 아스키 코드.. [SW Expert Academy] N-Queen 2806. N-Queen SW Expert Academy의 문제는 무단 복제가 금지되어 있으므로 링크로 대체합니다. N-Queen 문제는 대표적인 백트래킹 문제입니다!마찬가지로 재귀 함수를 이용해서 풀 수 있습니다! 퀸의 특성상 한 행에 딱 하나의 퀸만 존재 할 수 있습니다!때문에 총 N개의 퀸만이 존재할 수 있는 것이죠! 문제를 푸는 방법은 재귀 함수를 통해서 각 행마다 퀸을 놓을 수 있는 개수를 세서 반환하고 모두 더해주면 됩니다!기저 사례는 맨 마지막에 퀸을 위치 시키려고 하는 경우이겠죠!그리고, 놓인 퀸의 영향으로 놓지 못하는 곳을 항상 체크해 두는 것을 잊지 말아야 합니다. 하지만, 체크할 때에 유의해야할 것이 있습니다!만약, bool을 이용해서 놓을 수 없다는 체크를 했을 때 생기는 문제죠!그.. [SW Expert Academy] 장훈이의 선반 1486. 장훈이의 높은 선반 SW Expert Academy의 문제는 무단 복제가 안되므로 링크로 대체합니다! 장훈이의 높은 선반! 덧셈의 모든 경우의 수를 다 만들어서 원하는 목표인 B부터 차례대로 해당 덧셈이 될 수 있는지 확인하면 됩니다! 덧셈을 확인하는 방법은 어떻게 하면 될까요?높이 1만이 20명 있을 수 있기 때문에, 우선 배열의 200001의 크기를 가지는 배열을 만듭니다.그리고 현재는 아무런 더하기도 할 수 없기 때문에 더하기의 max 값은 0 입니다! 이제 3을 입력받겠습니다! max(0) 에 3을 더해서 3이 더해서 나올 수 있는 것이라는 것을 체크해 줍니다.이제 4를 입력 받습니다. max(3)에 4를 더해서 max는 7이 됩니다. 그리고 4도 입력 받았으므로 4에 체크를 해줍니다... [SWExpertAcademy] Code Battle (18.8.12 수정) 글이 다 날아갔다... 너무슬프다.. 다시 써야겠따.. SW Expert Academy의 문제는 무단 복제가 금지되어 있으므로 링크로 대체합니다. 4579. 세상의 모든 팰린드롬 2 이 문제는 이전에 왔던 펠린드롬과 비슷하다!하지만 훨씬 쉽다! 왜냐하면 *은 모든 글자를 대체할 수 있기 때문이다!따라서 뒤에서 부터 팰린드롬이 되는지(문자가 같은지)확인하다가 별표를 만나면 어떠한 단어든 팰린드롬이 가능하다는 소리다!(단, 문자를 확인하면서 팰린드롬이 안된다면 그 문자는 무조건 팰린드롬이 안되는 것이다!) 예를들면, a*wflkjwrglakjgla 라는 단어를 생각해보자!뒤에 a가 팰린드롬이니 제외하고 *wflkjwrglakjgl를 보면,*에는 wflkjwrglakjgl가 거꾸로 들어가기만 하면 팰린드롬이 .. [알고스팟] 광학 문자 인식 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)OCR60000ms65536kb1203292 (24%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제알림: 채점 서버 속도 문제로 시간 제한을 60초로 늘리고, 테스트 케이스 수를 20으로 줄입니다.광학 문자 인식(Optical Character Recognition)은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정을 말합니다. OCR 알고리즘들은 대개 수많은 필기 샘플을 통계적으로 분석하고 패턴을 찾아내어 각 단어들을 인식하곤 합니다. 하지만 단순히 각 단어들을 개별적으로 인식하기보다, 단어의 분포나 문법 등을 고려하면 더 나은 결과를 얻을 수 있는 경우가 많습니다... [알고스팟] 여행 짐 싸기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PACKING2000ms65536kb41941145 (27%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.물건노트북 컴퓨터카메라XBOX365커피그라인더아령백과사전부피4264210절박도7106754캐리어의 용량이 정해져 있기 때문에 가져갈.. [알고스팟] 두니발 박사의 탈옥 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)NUMB3RS2000ms65536kb40171670 (41%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았습니다. d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수)를 찾아왔습니다. 찰리 교수는 두니발 박사가 감옥에 남겨둔 노트를 분석해 다음과 같은 가설을 세웠습니다.두니발 박사는 검문을 피해 산길로만 이동한다.두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.두니발 박사는 수색을 피하기 위해 그 후 매일 인접한 마을로 움직여 은신한다.. 이전 1 ··· 7 8 9 10 11 12 다음
