Algorithm/BaekJoon (10) 썸네일형 리스트형 [백준 5557] 1학년 python 문제 풀이 이 문제는 DP로 풀어야한다. 어떤 구조로 정보가 저장될 수 있을지 살펴보면 왜 DP로 풀어야하는지 시각적으로 알 수 있다. 0부터 20사이의 숫자만 나와야하므로 DP는 크기가 21인 배열(0포함)을 사용할 수 있다. 21개의 배열에 루프를 돌며 다음 값을 + - 해서 다음 배열에 저장해주면 된다. 이때 상근이는 20을 넘는 수는 모른다는 조건이 있으므로 배열을 넘어가는 수는 저장하지 않는다. 이를 코드로 구현하면 아래와 같다. 통과된 풀이 import sys n = int(input()) arr = list(map(int, sys.stdin.readline().split())) dp = [[0] * 21 for _ in range(n)] # 첫 번째 수는 무조건 저장해야하니까 dp[0][ar.. [백준 12904] A와 B python 문제 문자열 S, T가 주어질 때 2가지 규칙에 의해 S를 T로 변경할 수 있는지 출력하는 문제이다. 풀이 기본 아이디어 S의 길이 마지막 문자열이 A라면 A를 제거한다. 문자열을 뒤집고 뒤에 B를 추가한다. -> 마지막 문자열이 B라면 B를 제거하고, 문자열을 뒤집는다. 파이썬 구현 문자열을 뒤집고, 마지막 문자열을 제거하는 동작을 해야하므로 리스트 이용 통과된 풀이 s = list(input()) # 문자열 S t = list(input()) # 문자열 t success = False while len(s) != len(t): if t[-1] == 'A': # 규칙 1 t.pop() elif t[-1] == 'B': # 규칙 2 t.pop() t = t[::-1] if s == t: # 성공 여부 체.. [백준 9020] 골드바흐의 추측 python 문제 문제 요약 : 모든 짝수를 두 소수의 합으로 나눌 수 있다는 골드바흐의 추측에 맞게 주어진 짝수 n에 대하여 골드바흐 파티션을 출력하는 문제이다. 풀이 기본 아이디어 : n을 반으로 나눈 다음 n에서 반으로 나눈 수와 가까운 소수를 뺐을 때 나머지가가 소수이면 골드바흐 파티션이 된 것 ! 소수인지 판별 에레토스테스테네스의 체 사용 ( 백준 1929 번 ) 루프 사용 반복 변수 : tmp , n//2 부터 시작 반복 변수 갱신 : 0이 되기 전 까지 -1 종료 조건 : n- tmp 했을 때 소수가 나온다. 반(n // 2) 만 체크하는 이유 가장 차이가 적은 파티션을 찾아야 하니까. 0부터 (n // 2)까지 반만 체크해도 n-tmp가 소수인지 체크하기 때문에 결국 0부터 n까지 전체가 다 체크되니까.. [백준 4948] 베르트랑 공준 python 문제 풀이 처음에 입력받은 수에 대해서 숫자를 세는 방식으로 문제를 풀었는데 시간 초과가 되었다. 가장 큰 수(123456)까지 소수가 아닌지 기억한 후 입력받은 구간에 대해서 소수의 개수를 세는 방식으로 바꿔서 통과되었다. 통과된 풀이 sosu = [0] * (123456 * 2 + 1) def isPrime(num): if num == 1: return False for i in range(2, int(num ** 0.5) + 1): if num % i == 0: return False return True for i in range(2,len(sosu)): if isPrime(i): sosu[i] = 1 while True: n = int(input()) if not n: break print(su.. [백준 1929] 소수 구하기 (+에라토스테네스의 체) python 문제 풀이 시간초과가 나와서 구글링해보니 에라토스테네스의 체를 이용해야 통과되는 문제이다. 에라토스테네스의 체 : 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 숫자의 제곱근 까지만 약수의 여부를 검증하는 방식이다. 1. 먼저 2를 제외한 2의 배수를 제거 2. 3을 제외한 3의 배수 제거 3. 5를 제외한 5의 배수 제거... 이런식으로 모든 구간에 대해 반복하면 소수만 남는다. 이것은 자신의 제곱근 까지만 약수의 여부를 검증하는 식으로 구현할 수 있다. (구글링을 통해 알게됨) 통과 된 풀이 def isPrime(num): if num == 1: return False else: for i in range(2, int(num ** 0.5) + 1): if nu.. [백준 11653] 소인수 분해 python 문제 풀이 통과된 풀이 가장 작은 수부터 시작 나누어 떨어지지 않을 때 까지 그 수로 나누어주면 그 수의 배수는 앞으로 체크안될테니까 소수로만 나누어짐 N = int(input()) m = 2 # 1은 소수가 아니니까 2부터 시작 while N != 1: if N % m == 0: print(m) N = N // m else: m += 1 시간 초과 풀이 n보다 작은 수 중 가장 작은 소수를 찾아서 계속 나누어주는 방법 error를 두어 소수가 아닌 경우 체크 n = int(input()) # 소인수 분해할 변수 num = 1 # 소수를 저장할 변수 # n보다 작은 수 중 가장 작은 소수부터 찾아 나가기 while n >= num: # num보다 n이 커지면 루프 종료 num += 1 # 1은 소수가 아.. [백준 1011] Fly me to the Alpha Centauri 파이썬 python 문제 나의 풀이 소스코드 t = int(input()) for _ in range(t): x, y = map(int, input().split()) distance = y - x # y와 x사이의 거리 tmp = 0 # 이동 거리 cnt = 0 # 공간 장치 이동 횟수 moving = 0 # 반복 횟수 while tmp < distance: cnt += 1 if cnt % 2 != 0: moving += 1 tmp += moving print(cnt) 해설 백준 단계별 풀어보기 하는 중 안풀려서 며칠 고민했던 문제다. 수학 유형은 직접 나열해보면서 규칙성을 파악해야한다. 특히, 문제에서 종료조건을 제대로 설정안해서 처음에 비효율적이고, 시간 초과가 나오는 코드를 만들었다. 1. 공간 장치 이동 횟수는 (.. [백준 2869] 달팽이는 올라가고 싶다 python 문제 풀이 쉬운 문제일 줄 알았는데 시간 초과가 나기 쉬운 문제였다. 그래서 정답률이 낮은듯.. 밤이 되기 전에 막대를 모두 올라가면 날짜 카운팅을 멈춰야한다. 나의 풀이 밤이 되기 전에 도착할 수 있는 것을 고려하면 다음과 같은 식을 세울 수 있다. 막대 길이에서 달팽이가 밤이 되기 전에 가는 만큼 뺀 길이(v-a)를 밤이 지나서 이동하는 거리(a-b)만큼 나누고, 그거보다 가장 큰 정수를 구하면 달팽이가 밤이 지나서 이동하는 길이가 된다. 거기에 다시 밤이 되기 전에 가는 길이인 1을 더하면 최종 결과값을 도출할 수 있다. import math a, b, v = map(int, input().split()) day = (v-a)/(a-b) + 1 print(math.ceil(day)) 80ms 나왔다.. 이전 1 2 다음
