알고리즘 문제풀이 (66) 썸네일형 리스트형 [SW Expert Academy] 괄호 짝짓기 괄호 짝짓기 SW Exeprt Academy의 문제들은 무단복제가 금지되어있기 때문에 링크로 대체합니다. 어떻게 풀까? 대표적인 스택 활용 문제입니다. 열린 괄호의 경우에는 모두 스택에 저장합니다.그리고, 닫힌 괄호가 나타나면 스택의 맨 위의 괄호와 비교합니다. 만약, 스택의 맨 위의 열린 괄호와 현재 나타난 닫힌 괄호가 매칭이 되지 않는다면 제대로 맞지 않는 괄호겠죠! 또한, 마지막에 스택 사이즈도 확인해야 합니다.스택 사이즈가 0이 아니라면, 열린 괄호가 많이 남아있다는 것이겠죠! 이 상황도 괄호의 짝이 맞지 않는 경우입니다. 간단한 예시 문제 2개를 풀어보겠습니다. 열린 중괄호이기 때문에 스택에 넣습니다.마찬가지로 열린 대괄호이기 때문에 스택에 넣습니다.마찬가지로 열린 소괄호이기 때문에 스택에 넣습.. [알고스팟] 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) 라고 한다. 예를.. [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시간 제한메모리 제한제출 횟수정답 횟수 (비율)NUMB3RS2000ms65536kb40171670 (41%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았습니다. d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수)를 찾아왔습니다. 찰리 교수는 두니발 박사가 감옥에 남겨둔 노트를 분석해 다음과 같은 가설을 세웠습니다.두니발 박사는 검문을 피해 산길로만 이동한다.두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.두니발 박사는 수색을 피하기 위해 그 후 매일 인접한 마을로 움직여 은신한다.. [알고스팟] 폴리오미노 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)POLY1000ms65536kb16781071 (63%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형.. [알고스팟] 삼각형 위의 최대 경로 개수 세기 문제 링크삼각형 위의 최대 경로 수 세기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)TRIPATHCNT5000ms65536kb20141122 (55%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제9 5 7 1 3 2 3 5 5 6위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다.이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9, 7, 2, 6}과 {9, 7, 3, 5}의 합이 모두 최대인 24.. [알고스팟] 타일링 방법의 수 세기 문제링크 타일링문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)TILING21000ms65536kb28901781 (61%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.입력입력의 첫 줄에는 테스트 케이스의 수(C 이전 1 ··· 5 6 7 8 9 다음
