코테용 문제풀이/알고스팟

알고스팟 외발 뛰기(jumpgame) 문제 파이썬으로 풀기

숫자 격자를 입력받아서, 맨 처음 칸부터 맨 마지막 칸까지 갈 수 있나를 알아보는 문제이다. 전형적인 동적계획법 문제이다. 만약 동적계획법을 아주 잘 알고 있다면, 이 문제는 매우 쉽게 느껴졌을 것이다. 하지만 나는 동적계획법 문제를 볼때마다 머리가 아파지는 초보 코더이기 때문에, 여러번의 삽질을 겪었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #jumpgame def jump(numlist, x, y): # 숫자 격자와 현재 x, y 위치를 입력받음 if x >= n: return False # x축 칸을 넘어간 경우 if y >= n: return False # y축 칸을 넘어간 경우 if x == n-1 and y ..

알고스팟 단어 길이 재기 (wordlength) 문제 파이썬으로 풀기

단어 배열을 받고, 단어의 평균 길이를 출력하는 문제이다. 조건이 좀 까다로워서 여러번 실패를 했지만, 그래도 어찌어찌 구현을 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #wordlength import sys def wordlength(line): word = line.pop(0) # 첫 입력을 뽑아놓는다 while len(line) > 0: locword = line.pop(0) if word[-1] == '-' and locword[0] != '-': # 문제의 조건 word = word[:-1] + locword # 전 입력의 '-' 부분은 제외함 else: word = word + ' '..

알고스팟 Longest Increasing Sequence (LIS)문제 파이썬으로 풀기

문제 자체는 이해하기 매우 쉽다. 수열을 받아 가장 긴 부분 수열의 길이를 구하면 되는 문제이다. 하지만 푸는 것은 매우 힘들었는데, 순증가 하는 부분 배열을 어떻게 구해야할지 방법이 마땅히 떠오르지 않았기 때문이었다. 혼자서 삽질을 하다가, 인터넷에서 새로운 방법을 찾아 보았다. 메모이제이션을 이용해 뒤에서부터 증가수열의 길이를 구해나가는 방식이다. 이를 파이썬으로 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #lis import sys def lis(pos): if dp[pos] != -1: # -1이 아니라면 lis길이를 구한 것이므로 그 길이를 리턴 return dp[pos] ret = 1 # lis 길이 for l i..

알고스팟 울타리 잘라내기 (fence) 문제 파이썬으로 풀기

입력값을 받아 가장 큰 넓이의 직사각형의 크기를 출력하면 된다. 보기엔 쉬워 보였지만, 몇번의 실패를 하고 어떤 알고리즘을 써야 할지 찾아보았다. 분할 정복으로 푼 사람이 꽤 많이 보였으나, 나는 그 방법보단 스위핑이 나아 보여서 스위핑으로 푸는 방법을 참고했다. 판자 높이의 index를 이용해 계산하는 방식이다. 거의 배끼다 시피 해서 코드를 완성했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #fence import sys case = int(sys.stdin.readline()) for i in range(case): fencenum = int(sys.stdin.readline()) # 판자 수 fences = list(map(..

알고스팟 weekly calendar 문제 파이썬으로 풀기

날짜를 입력받아 한 주를 출력하는 문제이다. 간단해 보이지만 조금 어려운 문제인데, 일월화수목금토 순으로 날짜를 출력해야하고, 그 와중에 월이 넘어가면 날짜를 더해주던 빼주던 해야하기 때문이다. 다른 언어였다면 고생했을거 같지만, 파이썬은 indexing이 매우 잘 된 언어라, 월이 넘어가도 리스트에서 처리하는게 쉬워 금방 풀게 되었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #weeklycalendar import sys months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] # 월마다의 날 수 weekdays = ['Sunday', 'Monday', 'Tuesday', 'Wedne..

알고스팟 록 페스티벌(festival) 문제 파이썬으로 풀기

공연장을 빌리는 평균 비용을 최소한으로 하는 문제이다. 이 문제를 풀 때 세번의 큰 과정을 거쳐서 정답을 얻게 되었는데, 처음과정은 이렇게 대여하는 날짜를 다르게 하여 평균 비용을 구하는 것이다. 이 방법이 제일 구현하기 간단하고 쉽게 생각할 수 있어서 해보았지만, 시간초과가 나왔다. 그래서 해본 것이 이렇게 시작하는 날짜를 정하고 대여하는 날짜를 늘려나가는 방식이다. 이건 전의 방법보다 빠르겠지만, 코드를 짰을때 여전히 시간초과가 났다. 그 원인이 뭘까 하고 생각해보니, 대여비용을 구할때 썻던 sum 함수가 의외로 시간을 많이 잡아먹는다는 글을 보았다. 그래서 sum의 사용을 최소한으로 하려 코드를 다시 짰고, 드디어 정답을 얻게 되었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

알고스팟 weird numbers (weird) 문제 파이썬으로 풀기

숫자를 입력받고, 그 숫자가 weird 인지 아닌지 판별하는 문제이다. 어떤 수가 weird이라면, 그 수 자신을 제외한 약수의 합이 자신보다 커야하고, 수 자신을 제외한 약수 집합의 모든 부분합이 그 숫자가 되면 안된다. 이 문제는 전에도 시도해 보았지만, 시간을 넘기거나 오답이 계속 나와서 다른 코드를 좀 참조해서 풀었다. 우선 첫번째 조건인 약수집합의 합을 빠르게 구하기 위해서 이 코드를 이용했다. i^2를 이용해 시간을 줄이면서도, 제곱수를 한번만 추가하게 하는 코드가 좋아보여서 썼다. 두번째 조건을 위해선 아래의 코드를 이용했다. 약수집합과 구하는 수를 점점 줄여나가는 방법이다. 문제를 간소화 하는 방식이 좋아 보여서 썼다. 그렇게 가져온 코드를 파이썬식으로 변형했다. 1 2 3 4 5 6 7 ..

알고스팟 Mismatched Brackets 문제 파이썬으로 풀기

대괄호 중괄호 소괄호로 이루어진 입력을 받아서 열리고 닫힘의 유무와 겹침의 유무를 보는 문제이다. 문제에 보면 조건이 세 개 있는데, 괄호끼리 페어를 이룰 것, 먼저 열리고 닫힐 것, 서로 겹치지 않을 것이다. 이중 세번째 조건이 가장 어려웠는데, 이 코드를 보고 구현을 하게 되었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #brackets2 open = ['[', '{', '('] close = [']', '}', ')'] case = int(input()) for i in range(case): bra = list(input()) # 입력 cross = [] checkval = True # true=안겹침,..

알고스팟 yulo 문제 파이썬으로 풀기

점수 여러개를 받아, 가장 큰 기대점수를 출력하는 문제이다. 주의할 점은 1등 기대점수를 소수점 첫 번째 자리까지 출력해야한다는것 정도? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #yulo import sys case = int(sys.stdin.readline()) for i in range(case): stunum = int(sys.stdin.readline()) # 학생 수 입력 stutest = list(map(int, sys.stdin.readline().split())) # 점수 입력 testsor = sorted(stutest) # 정렬(가장 작은 수와 가장 큰 수끼리 더해야 하기 때문에) testlist = [] # 리스트에 기대점수를 넣는다 for j i..

알고스팟 note 문제 파이썬으로 풀기

문제 자체는 간단하게 보인다. 입력은 8개의 서로 다른 정수 한 줄 뿐이고, 배열에 따라 descending, ascending, mixed 중 하나를 골라 출력하면 된다. (Example 1 같은건 신경안써도 됨) 간단해 보이는 문제지만, 고전했다. 그 이유로는 여럿이 있는데, 우선 첫번째는 저 Example 1, 2, 3 이런것도 출력해야 하나 하고 출력에 넣었다가 안 넣어도 된다는 것을 깨달았다. 두번째 이유는 내 성급함이다. 입력을 항상 받던대로 sys.stdin.readline()으로 받고, 리스트에 넣은 다음 배열해서 출력하는 것이 계속 실패해서 다른 사람의 코드를 좀 보려고 찾아봤는데, 이렇게 c++로 쓴 코드가 나왔다. 보니까 gets함수를 사용해서 입력을 받는데, 이게 버퍼와 관련이 있다..