본문 바로가기

Programming [Python]

 (411)
#344 백준 파이썬 [2018] 수들의 합 5 - 투포인터 https://www.acmicpc.net/problem/2018 SOLUTION 투포인터 알고리즘을 통해 풀이하였다. (https://claude-u.tistory.com/393 참조) 차이점은 포인터 자체가 리스트 상 위치가 아니라 들어가는 숫자 자체이기에 리스트를 구성할 필요가 없다는 것 정도이다. PYTHON CODE N = int(input()) start = 0 #첫 숫자 end = 1 #끝 숫자 answer = 0 #정답 sum_numbers = 1 #답이 되는 숫자 while start < N//2 + 1: if sum_numbers < N: #작을 경우 뒤에 숫자 하나를 더붙여줌 end += 1 sum_numbers += end elif sum_numbers == N: #맞을 경우 숫자 ..
#343 백준 파이썬 [1644] 소수의 연속합 - 투포인터 https://www.acmicpc.net/problem/1644 SOLUTION 에라토스테네스의 체로 400만 이하의 소수를 구해준 뒤 투포인터 알고리즘을 통해 소수로 합이 되는 숫자를 구해주었다. 1) 소수를 구하는 에라토스테네스의 체 방법 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 1-1) 파이썬으로 에라토스테네스 구현 https://claude-u.tistory.com/202 2) 투포인터 알고리즘이란, 파이썬 구현 방법 https://claude-u.tistory.com/393 PYTHON CODE #4000000이하의 모든 소수를 추출 ..
#342 백준 파이썬 [1806] 부분합 - 투포인터 https://www.acmicpc.net/problem/1806 SOLUTION 위 문제는 투포인터 알고리즘으로 풀이하면 쉽게 풀린다. 알고리즘은 어렵지 않다. 말그대로 start 포인터와 end 포인터를 활용해 start~end 까지의 합을 구해주는 방식이다. end는 항상 start를 초과하고 두 포인터 모두 증가하는 방향으로 나아간다. 1) 주어진 리스트의 sum_A리스트를 따로 하나 생성한다. (첫항부터 자신 까지의 합이 담긴 리스트) 2) start = 0, end = 1로 놓는다. 3) sum_A[end] - Sum_A[start]를 기반으로 다음 if문을 실행한다. 4-0) (start, end)가 (n-1, n)이 되면 종료한다. 4-1) sum_A[end] - sum_A[start] 가..
#341 백준 파이썬 [2003] 수들의 합 2 https://www.acmicpc.net/problem/2003 SOLUTION 1) 단순히 1부터 N까지 Sum한 것에서 1부터 K까지 Sum한 걸 빼주면 되는 경우의 수가 있고 2) 투 포인터 알고리즘을 활용해 푸는 방법이 있다. (하단 링크 참조) 전자의 경우엔 수가 작을 경우엔 풀리지만 어느 정도 수가 커지면 시간 복잡도가 N^2가 되기에 비효율적인 단점이 있다. 아래의 경우엔 1) 단순하게 풀이하였다. 투포인터로 푸는 방법은 https://claude-u.tistory.com/393를 참고하면된다. PYTHON CODE #pypy로 풀이하였음 N, M = map(int, input().split()) A = list(map(int, input().split())) sum_A = [0] * (N..
#340 백준 파이썬 [1740] 거듭제곱 https://www.acmicpc.net/problem/1740 SOLUTION 제곱수의 합으로 이루어질 수 있는 수 중 작은 수부터 나열하는 문제다. 자세히보면 제곱은 정수의 조합으로 이루어져있다. 3^0 (이하 제곱만 나열) - 1개 1, 10 - 2개 2, 20, 21, 210 - 4개 3, 30, 31, 32, 310, 320, 321, 3210 - 8개 이를 쭉 지속해나가다 보면 증가량이 2의 배수 형태를 띔을 알 수 있다. 3^n + 3^n-1 .... 3^1, 3^0의 수는 n이 있느냐 없느냐에 따라 101010101011... 와 같이 표현할 수 있다. ex) 11번째 수 = 1011 = 3^3 + 3^1 + 3^0 ex) 26번째 수 = 11010 = 3^4 + 3^3 + 3^1 ex)..
#339 백준 파이썬 [11005] 진법 변환 2 https://www.acmicpc.net/problem/11005 PYTHON CODE system = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" #10진법이면 9 까지, 36진법이면 Z까지 표현된다 N, B = map(int, input().split()) answer = '' while N != 0: answer += str(system[N % B]) #위치로 진법 변환 N //= B print(answer[::-1])
#338 백준 파이썬 [4504] 배수 찾기 https://www.acmicpc.net/problem/4504 PYTHON CODE n = int(input()) number = int(input()) while number: if number % n == 0: print("%s is a multiple of %s." % (number, n)) else: print("%s is NOT a multiple of %s." % (number, n)) number = int(input())
#337 백준 파이썬 [1075] 나누기 https://www.acmicpc.net/problem/1075 PYTHON CODE N = int(input()) F = int(input()) front = N // 100 answer = front * 100 while answer % F != 0: answer += 1 print(str(answer)[-2:])

티스토리툴바