코테용 문제풀이/알고스팟
알고스팟 wildcard (wildcard) 문제 파이썬으로 풀기
문자를 받아, 매치가 되는 문자를 출력하는 문제이다. 문제를 보고, 문자를 ?와 *로 잘라서 처리해야하나 고민해서, 자르고 위치를 어떻게 해야할지 찾아보다가 https://wikidocs.net/4308 위키독스 온라인 책을 제작 공유하는 플랫폼 서비스 wikidocs.net 여기에서 정규 표현식이라는 것을 발견했다. 읽어보니 문자열 매칭을 빠르고 짧게 처리할 수 있는 방법이 나와있어서, 그것을 이용해 코드를 짜보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 # wildcard import re case = int(input()) for i in range(case): instr = input() # 와일드카드 문자열 입력 newin = ins..
알고스팟 승률올리기 (RATIO) 문제 파이썬으로 풀기
승률을 1% 올리게 되는 가장 적은 연승 횟수를 구하는 문제이다. 이진탐색을 생각해 낸다면 매우 쉬운 문제가 될 것이고, 아니라면 고생할 것이다. 물론 난 후자였고, 그래서 이것저것 고민해보다가 문제 분류에 이진탐색이라고 있는것을 보고 이진탐색을 적용하여 문제를 해결했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 # ratio maxwin = 2000000000 # 최대 승리 case = int(input()) for i in range(case): n, m = map(int, input().split()) result = 0 # 결과 nowrate = (m * 100) // n # 현재 승률 if nowrate >= ((m + maxwin) * 100)..
알고스팟 원주율 외우기 (PI) 문제 파이썬으로 풀기
숫자를 입력받아, 난이도를 계산하는 문제이다. 전형적인 동적계획법 문제처럼 보이지만(큰 문제를 작게 자르고 값을 계산하여 저장하고 저장한 값을 이용해 최종 값을 구하면 된다), 이 문제의 특이한 점은 숫자들을 3, 4, 5자리로만 끊어야 하고, 입력이 매우 크다는 것이다. 두번째 점은 특히 파이썬으로 풀때 치명적으로 다가오는데, 일반적인 동적계획법 문제 풀듯이 전체 값을 저장할 리스트/배열을 만들고 리스트/배열의 특정 위치의 값을 가져와서 그 값의 최소/최댓값을 구하고 그것을 return 하는 방식으로는 주어진 시간 (1000ms) 안에 풀 수 없다는 것이다. 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 ..
알고스팟 드래곤 커브 (dragon) 문제 파이썬으로 풀기
문제가 길어서 링크로 대체한다. https://algospot.com/judge/problem/read/DRAGON algospot.com :: DRAGON 드래곤 커브 문제 정보 문제 드래곤 커브(Dragon curve)는 간단한 수학 규칙으로 그릴 수 있는 그림으로, 위 그림같은 형태를 지닙니다. 드래곤 커브는 선분 하나에서 시작해서 간단한 규칙으로 이 선분을 변형해서 만들어지며, 변형이 한 번 이루어져 세대가 변할 때마다 더욱 복잡한 모양으로 진화합니다. 이 도형같이 일부를 확대했을 때 전체와 비슷한 형태로 구성된 도형들을 프랙탈(fractal) 이라고 하지요. 드래곤 커브를 그리는 방법을 드래곤 커브 algospot.com 한 세대의 문자열을 요구하는 만큼 출력하면 되는 문제이다. 이 문제는 문자..
알고스팟 쿼드 트리 뒤집기 (quadtree) 문제 파이썬으로 풀기
이미지를 압축하는 방식 중 하나인 쿼드 트리를 입력으로 받아 원 그림의 상하를 뒤집은 모습을 쿼드 트리로 출력하면 된다. 문제를 풀며 분할 정복이란 것에 한발짝 발을 딛는 듯한 느낌을 받았다. 이 문제는 입력을 여러 조각으로 나누어 풀어야 하는데, 'x'+왼쪽 위+오른쪽 위+왼쪽 아래+오른쪽 아래로 나누고, 그거에 맞춰 상하로 바꾸어주어야 한다. 인터넷에서 그림을 이용하여 쉽고 빠르게 이해할 수 있는 글을 찾았는데, https://gurumee92.tistory.com/153 알고스팟 문제 풀이 QUADTREE 책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "QUADTREE"에 대한 풀이입니다. 목차 문제 해결 전략 코드 전문 QUADTREE 문제 URL은 다음과 같습니다. QUADTRE..
알고스팟 PPAP (PPAP) 문제 파이썬으로 풀기
https://algospot.com/judge/problem/read/PPAP algospot.com :: PPAP PPAP 문제 정보 문제 I have a pen I have an apple Apple pen! I have a pen I have a pineapple Pineapple pen! Apple pen, Pineapple pen, pen-pineapple-apple-pen Piko just can't stop singing along to PPAP! PPAP is an extremely addictive song which became an internet algospot.com 사진으로 하기엔 너무 길어서 링크로 대체한다. 문제 자체는 "pen-pineapple-apple-pen/"이라는 ..
알고스팟 Domino (DOMINO) 문제 파이썬으로 풀기
도미노에 있는 마크의 수를 세는 문제이다. 처음 문제를 보면 갯수를 어떻게 세야 할지 걱정이 앞설 수 있지만, 아주 간편한 방법이 있다. 예제에 있는 입력과 출력을 표로 한번 나타내보자. 입력 출력 2 12 3 30 15 2040 입력이 2가 들어왔을때, 출력은 12이다. 그리고 문제 설명에서 도미노가 2칸일때 6개의 경우가 나온다는 것을 보여주었다. 여기서 출력이 입력과 경우의 수의 곱인가? 하고 추측해볼 수 있다. 입력이 3일때 출력은 30이다. 앞서 했던 추측이 맞다면, 30은 3과 10의 곱이므로 도미노칸이 3일경우 10개의 경우가 나올 것이다. 그리고 입력이 1이 들어왔을때를 가정해보자. 도미노 1칸에는 마크가 0개, 1개, 2개일 경우가 있으므로, 경우의 수는 3개이다. 그럼 여기까지 진행한 ..
알고스팟 달팽이 (snail) 문제 파이썬으로 풀기
달팽이가 우물을 탈출할 확률을 구하는 문제이다. 동적계획법으로 분류가 되어있긴 하지만, 그걸 이용하지 않고 훨씬 쉬운 방법으로 풀어낼 수 있다. 문제를 보면, 달팽이는 비가 오는 날 2m를 기어오르고, 맑은 날은 1m를 기어오른다. (미끄러진다거나 밑으로 떨어지지 않는다!) 이 조건을 핵심으로 하여 문제를 푸는 것이다. 예를 들어, 예제 입력에 나와있는 3m를 2일안에 오를 확률을 구한다 하자. 달팽이가 미끄러지지 않기 때문에, 날이 맑던 비가오던, 달팽이는 매일 1m를 오른다. 그러므로, 3m를 2일안에 맑은 날에 1m를 오르고 비오는 날엔 2m를 오르는 달팽이가 오를 확률 = 1m를 2일안에 맑은 날에 0m를 오르고 비오는 날엔 1m를 오르는 달팽이가 오를 확률 이다. 마찬가지로 예제 입력에 있는 ..
알고스팟 폴리노미노 (poly) 문제 파이썬으로 풀기
세로 단조 폴리노미노의 수를 구하는 문제이다. 이 문제를 풀려면 점화식을 구해서 구현하는 게 가장 좋아 보였는데, 이 포스팅에서 점화식을 아주 보기에 좋게 구해 놓았으므로, 이를 참고하여 코딩을 했다. 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 #poly def poly(n,d): if d == n: return 1 if board[n][d] != -1: return board[n][d] x = n-d ret = 0 for o in range(1,x+1): ret += (o+d-1)*poly(x,o) ret %= 10000000 board[n][d] = ret return ret board = [[-1 for j in ran..
알고스팟 coin change(coins) 문제 파이썬으로 풀기
금액을 받고, 주어진 동전으로 환전 할 수 있는 경우를 구하는 문제이다. 전형적인 동적계획법 문제이다. 처음엔 접근방식을 전체 금액에서 동전을 빼는 식으로 구하려 했다. 즉 금액이 110원이고 동전이 10, 50, 100, 500이 있으면 110=100*1+10*1=50*2+10*1=50*1+10*6=10*11 로 4가지 경우가 나오는데, 110에서 뺄 수 있는 가장 큰 금액인 동전이 100원이므로 110-100=10을 하고, 남은 10에서 뺄 수 있는 가장 금액인 동전이 10이므로 10-10=0 이 되면 횟수에 1을 더하고, 110에서 100을 제외하고 뺄 수 있는 가장 큰 금액인 동전이 50이므로 110-50=60을 하고 여기서 또 가장 큰 금액인 50을 빼서 60-50=10 이 되고, 10-10=0..