나홀로 프로그래밍 공부하기

문제 출처 : algospot.com :: RESTORE algospot.com :: RESTORE 실험 데이터 복구하기 문제 정보 문제 토요일에 출근해서 연구실에서 놀고 있던 대학원생 진호는 실수로 실험에 사용하던 데이터를 삭제하고 말았습니다. 복사본도 없는 터라 이대로라면 교수 algospot.com 1. 문제 분석 (1) 답의 구조 파악하기 1) 예제에서 답의 구조 확인하기 3번째 예제 입력에서 부분 문자열 조각 [ abrac, cadabra, dabr ]을 이용하여 만들 수 있는 문자열 중 가장 짧은 문자열은 cadabrac이다. 두 조각 abrac과 cadabra에서 abra가 일치하는 것을 알 수 있다. 부분 문자열 조각 dabr는 cadabra의 일부인 것을 알 수 있다. 2) 정리하기 어떤..

문제 출처 : algospot.com :: ZIMBABWE algospot.com :: ZIMBABWE 웨브바짐 문제 정보 문제 계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러! 계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르 algospot.com 1. 코드(작동 안됩니다.) MOD = int(1e9) + 7 # 완전 탐색 알고리즘 # e의 자릿수로 만들 수 있는 숫자를 모두 출력 # price : 지금까지 만든 가격 # taken : 각 자릿수의 사용 여부(= Boolean 리스트) def generate(price, taken): # 기저 사례 : 모든 자릿수를 사용 if len(price) == n: if ..

문제 출처 : algospot.com :: TSP2 algospot.com :: TSP2 Traveling Salesman Problem 2 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 algospot.com 1. 함수의 정의 바꾸기 6.7 단원(6.7 예제 : 최적화 문제 - 여행하는 외판원 문제(Python) (tistory.com))에서 완전 탐색 알고리즘을 통해 이 문제를 해결한 전력이 있다. 전에는 n개의 도시들에 대해 n!개의 경로를 모두 생성하는 방법을 사용했는데, n이 15만 되더라도 계산이 불가능할 지경이다. 또한, sh..

문제 출처 : algospot.com :: DRAGON algospot.com :: DRAGON 드래곤 커브 문제 정보 문제 드래곤 커브(Dragon curve)는 간단한 수학 규칙으로 그릴 수 있는 그림으로, 위 그림같은 형태를 지닙니다. 드래곤 커브는 선분 하나에서 시작해서 간단한 규칙으로 이 algospot.com 1. p번째 글자를 찾는 함수 작성하기 (1) 함수 설계하기 우선 맨 앞에서 전체 드래곤 커브 문자열을 생성하는 알고리즘을 만들고, 이것을 기반으로 p번째 글자를 찾는 알고리즘을 작성해본다. 드래곤 커브 문자열을 만드는 방법을 재귀적인 구현으로 만든다. 처음 주어진 정보는 0세대 문자열인 FX(=seed)와 세대 수 n(=generations)이다. 이를 전달받는 함수 curve( )를 ..

문제 출처 : algospot.com :: KLIS algospot.com :: KLIS K-th Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있 algospot.com 1. 문제 분석 이전의 예제와 문제(8.4절 참고)들을 통해서 최대 증가 부분 수열 중 가장 긴 것을 찾아낸 경험이 있다. 이를 바탕으로 위 문제를 해결하기 위해서는 다음의 과정을 거쳐야 한다. 1. 바탕이 되는 최적화 문제를 푼다. 2. 최적화 문제의 최적해를 세는 문제를 푼다. 3. 답의 수를 기반으로 답안을 재구성한다...

문제 출처 : algospot.com :: MORSE algospot.com :: MORSE 모스 부호 사전 문제 정보 문제 모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 algospot.com 1. 모든 신호 만들기(완전 탐색 알고리즘) (1) 문제 분석 이 문제처럼 문제의 모든 답을 사전순으로 나열했을 때, 이 중 k번째에 오는 답을 구하라는 문제가 종종 있다. 답의 개수가 적은 경우에는 모든 답을 만들어 정렬하고 k번째 답을 반환할 수도 있지만 현실은 그렇지 못 한 경우가 대부분이다. 기존의 동적 계획법 문제를 해결할 때, 완전 탐색으로 시작했던 것 처럼 이런 형태의 ..

문제 출처 : algospot.com :: OCR algospot.com :: OCR 광학 문자 인식 문제 정보 문제 알림: 채점 서버 속도 문제로 시간 제한을 60초로 늘리고, 테스트 케이스 수를 20으로 줄입니다. 광학 문자 인식(Optical Character Recognition)은 사람이 쓰거나 기계로 인 algospot.com 1. 문제 분석 이 문제에서 어려운 부분은 입력에 주어진 요구 조건을 수학적으로 풀어 쓰고 정형화 하는 부분이다. 또한, 원문이 생성되는 과정이 '8.16 문제 : 두니발 박사의 탈옥'에서 소개된 마르코프 연쇄 모델을 따른다. 마르코프 연쇄 유한개의 상태가 존재한다. 매 시간마다 상태가 변경된다. 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에 의해서만 ..

문제 출처 : algospot.com :: PACKING algospot.com :: PACKING 여행 짐 싸기 문제 정보 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 algospot.com 1. 문제 분석 (1) 완전 탐색 알고리즘 물건의 모든 조합을 하나하나 검사하고 이들 중 최적의 조합을 찾아내는 완전 탐색 알고리즘부터 시작 각 물건에 대해 가져가거나 말거나 두 가지의 선택이 존재한다. 따라서 전체 n개의 물건에 대해 2^n개의 조합이 있고 이를 통해 다음과 같은 부분 문제를 얻을 수 있다. pack(items) = 지금까지 모든 물건들의 목록이 items에 주어질 때, 남은 용량을..