while (1): study();

링크: https://algospot.com/judge/problem/read/LUNCHBOX algospot.com :: LUNCHBOX Microwaving Lunch Boxes 문제 정보 문제 After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp. He contacted the famous packed lunch company "Doosot" to prepare N lun algospot.com import sys rl = lambda: sys.stdin.readline() def min_time(): t..

링크: https://algospot.com/judge/problem/read/MATCHORDER algospot.com :: MATCHORDER 출전 순서 정하기 문제 정보 문제 전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 algospot.com 동적 계획법은 시간적으로 효율적이지만, 공간적으로는 그렇지 않을 수 있습니다. 모든 경로를 재귀호출하여 탐색하고 그 결과를 캐싱하기 때문이죠. 만약 공간적으로 효율적인 알고리즘을 작성해야 하는 경우엔 탐욕법을 생각해볼 수 있습니다. 탐욕법은 탐욕법으로 최적해를 찾을 수 있는 문제 또는 동적계획법으로 작성하기엔 메모리 공간을 너무 많이 차지하여 근사해를 ..

링크: https://www.algospot.com/judge/problem/read/PACKING algospot.com :: PACKING 여행 짐 싸기 문제 정보 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 www.algospot.com 최적화 문제에서 경로의 가짓수를 센다거나, 최대값을 구하는 일은 쉽습니다. 그러나 실제 경로를 출력해야한다면 어떨까요? 완전탐색 알고리즘에 동적계획법을 적용할 때 단지 캐시만 추가하여 전체 흐름에는 크게 변화가 없었던 것처럼, 결과를 출력할 때도 코드를 크게 바꾸지 않습니다. 단지 캐싱 과정에서 저장의 용이성을 위해 어느정도 포기했던 정보를 다시 재구..

링크: https://algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 동적 계획법으로 풀 수 있는 대표적인 문제입니다. 동적 계획법으로 최적화 문제를 풀때, 다음과 같은 절차를 밟는다고 생각하면 편합니다. 완전 탐색으로 설계 (최적 부분 구조) 최적화 문제로 부분문제 변환 메모이제이션 적용 아래 코드들은 다음과 같은 절차에 의해 LIS(Longest Increasin..

링크: https://www.algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 www.algospot.com 동적 계획법이란 완전탐색 알고리즘에서 중복되는 부분문제를 메모이제이션으로 해결하는 것을 의미합니다. 동적 계획법 알고리즘을 계획할 때는 몇 가지 중요한 조건이 있는데, 하나는 참조 투명성이며 다른 하나는 최적 부분 구조(optimal substructure)입니다. 최적 부분 구조란 부분문제의 최적..

링크: https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com 완전탐색은 문제의 한 조각을 풀고 나머지 문제의 처리를 재귀함수에 맡길 수 있다. 나아가 분할정복 알고리즘은 부분문제의 결과를 조합하여 원하는 답을 도출한다. 동적 계획법은 분할정복에서 한발 더 나아간다. 분할정복으로 접근가능한 어떤 문제들은 중복되는 부분문제(overwrapping subproblems)가 생긴다. 이 경우 따로 처리해주지 않으면 같은..

알고리즘 공부를 하다보면 온라인저지에 올라온 많은 문제를 풀게 됩니다. 그러나 일반적으로 sys.stdin.readline() 명령어를 사용하여 입력을 받는 실제 코딩테스트와는 달리 문자열을 다른 방식으로 전처리하거나 매번 수기로 입력해주어야 하여 실제 테스트와 연습 간의 괴리가 발생합니다. 이럴 때 다음과 같이 클래스를 활용하면 연습과 실제 간의 괴리를 최대한 해결할 수 있습니다. class Input: def __init__(self, txt): self.txt = txt self.idx = 0 def __len__(self, line): return len(line) def __getitem__(self): ret = self.txt.split('\n')[self.idx] self.idx += 1 ..

https://www.algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 www.algospot.com 해당 문제의 풀이에는 분할 정복을 사용합니다. 분할 정복이란 문제를 더 작은 부분문제들로 나누고, 부분문제들의 결과를 적절히 조합하여 전체 정답을 도출하는 과정입니다. 흔히 알려진 바로는 분할(divide) - 병합(merge)의 단계를 거쳐 푼다고 합니다. 쿼드트리 자체가 재귀적으로 정의되어 있기 때문에 재귀 호출을 사용하여 압축 혹은 ..

링크:https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 완전탐색은 가능한 모든 사건을 탐색하는 알고리즘입니다. 모든 것을 탐색한다는 워딩부터 왠지 계산이 힘들 것 같습니다. 그러나 많은 경우에 그렇지만, 항상 그런 것은 아닙니다. 입력 자료가 많지 않을 경우 오히려 더 빠를 수도 있으며, 처음에 문제에 접근하기 위한 좋은 직관을 제공하기도 합니다. 특히 ..

출처: https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 암호의 순서는 언제나 오름차순 정렬로 고정되어 있으므로, 순서에 대해 고려하지 않아도 됩니다. 따라서 조합(Combination)을 이용하여 간단하게 문제를 풀 수 있습니다. 파이썬 내장 라이브러리 중 하나인 itertools의 combinations 함수를 사용하면 됩니다. 소스코드는 다음과 같습니다. from itertools import combinations l, c = list(map(..