목록Algorithm (236)
HTD
www.acmicpc.net/problem/2581 import sys input = sys.stdin.readline def isPrimeNumber(n): for i in range(2, int(n**(1/2))+1): if n % i == 0: return False return True M = int(input()) N = int(input()) isPrimeNumberList = [True]*(N+1) primeMin = 10001 primeSum = 0 for i in range(2, N+1): if isPrimeNumberList[i]: if not isPrimeNumber(i): isPrimeNumberList[i] = False continue isPrimeNumberList[i] = T..
[Python] 백준 13460번: 구슬 탈출 2
www.acmicpc.net/problem/13460 import sys import copy input = sys.stdin.readline TOP, RIGHT, BOTTOM, LEFT = 0, 1, 2, 3 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def bfs(): global curMap, curRedPos, curBluePos todo = [[map, redPos, bluePos, 1]] # 2개의 구슬의 위치를 기록하여 중복을 허용하지 않도록 함 ballRecords = [[redPos, bluePos]] while todo: curOriginalMap, curOriginalRedPos, curOriginalBluePos, curCount = todo.pop( 0) ..
www.acmicpc.net/problem/1181 import sys input = sys.stdin.readline N = int(input()) words = set() for _ in range(N): words.add(input().rstrip()) words = list(words) words.sort() words.sort(key=lambda x: len(x)) for word in words: print(word) 우선 조건이 크게 두 개가 있다. 1. 조건에 따른 정렬 2. 중복된 문자는 1번만 출력함 일단 중복된 문자는 신경을 쓰지 않으므로, 순서는 없지만 중복을 허용하지 않는 집합(set)을 이용한다. 입력을 set()으로 초기화된 집합에 받아 중복을 걸러낸 이후에 이것을 리스트화 하..
www.acmicpc.net/problem/1874 N = int(input()) nums = [] for _ in range(N): nums.append(int(input())) stack = [] toPush = 1 toPrint = [] for num in nums: while toPush
www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net import sys input = sys.stdin.readline def setJumpCounts(maxIndex): global jumpCounts lastIndex = 1 i = 2 while lastIndex < maxIndex: rep = (i+1)//2 jumpCounts.append(jumpCounts[i-1]+rep) lastIndex = jumpCou..
www.acmicpc.net/problem/2206 import sys input = sys.stdin.readline dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(): global stepMap todo = [(0, 0, 0)] while todo: curPos = todo.pop(0) if curPos[1] == N-1 and curPos[2] == M-1: return stepMap[curPos[0]][curPos[1]][curPos[2]] for i in range(4): curX, curY = curPos[1] + dx[i], curPos[2] + dy[i] if 0
www.acmicpc.net/problem/1654 import sys input = sys.stdin.readline def getLanCountAfterCut(lans, cutBy): lanCountAfterCut = 0 for lan in lans: lanCountAfterCut += lan//cutBy return lanCountAfterCut K, N = map(int, input().split()) lans = [int(input()) for _ in range(K)] left, right = 1, max(lans) while left
import sys input = sys.stdin.readline N = int(input()) nums = list(map(int, input().split())) dp = [0]*N for i in range(N): maxDp = 0 for j in range(i): if nums[j] < nums[i]: maxDp = max(maxDp, dp[j]) dp[i] = maxDp+1 print(max(dp)) 우선 일반적인 풀이이다. i에 대한 for문의 각각 수행하는 것은 다음과 같다. 0~i-1 인덱스에서, nums가 nums[i]보다 작으면서 dp가 최대인 값(maxDp)를 찾고, 현재 dp에 maxDp+1을 넣어주는 것이다. 즉, 예시와 같은 경우 dp의 값은, [1, 2, 1, 3, 2, 4]..
[Python] 백준 10844반: 쉬운 계단 수
www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, N+1): dp[i][0] = dp[i-1][1] for j in range(1, 9): dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] dp[i][9] = dp[i-1][8] print(sum(dp[N]) % 1000000000) bfs 같은 것을 통해 직접 구현하는 것은 터무니없이 느리다. 따라서 DP를 이용한다. ..