python

문제백준 - 약수, 배수와 소수 2https://www.acmicpc.net/step/18[4948]베르트랑 공준문제링크: https://www.acmicpc.net/problem/4948 베르트랑 공준: 임의의 자연수 n에 대하여, n보다 크고 2n보다 작거나 같은 소수는 적어도 하나 존재한다. 문제를 그대로 읽어야 된다.n보다는 (크고) 2n보다 (작거나 같아야 한다.)n보다는 ((크고 2n보다 작거나) 같아야 한다.)2번으로 생각하고 풀었는데 1번이었다.즉 자연수 n이 주어졌을때 n 를 만족하는 소수의 갯수를 구하면 된다. 풀이전체풀이는 아래와 같다.# 에라토스테네스의 체를 이용한 풀이.from sys import stdininput = stdin.readline_max = 123456*2 # 체..

문제수 정렬하기 2: https://www.acmicpc.net/problem/2751수 정렬하기 3: https://www.acmicpc.net/problem/10989풀이[2751]수 정렬하기 2우선 첫번째 풀이다.N = int(input())nums = []for _ in range(N): nums.append(int(input()))nums.sort()print(*nums, sep="\n")갑자기 '시간초과'가 떠버려서 뭔가 했더니, input()때문이었다. 나같은 경우 웬만하면 int(input()) 또는 map(int, input().split())으로 해결하는 편인데, 이게 입력받을 데이터가 많은 경우엔 과부하가 걸린단다. input()은 입력값을 받을 때 프롬프트 메시지를 출력하고 사..

문제https://www.acmicpc.net/problem/24267알고리즘 수업 시리즈 중 가장 어려웠던 문제다. 수학책을 다시 구해봐야겠다.서준아 그만 일하자풀이N = int(input())print(N*(N-1)*(N-2) // 6, 3, sep="\n")이 문제는 두가지 방식으로 풀 수 있다. 압도적으로 쉬운건 조합을 이용한 풀이다. 시그마 공식을 이용한 풀이숫자의 개수: n-2개 (1부터 n-2까지니까)첫 번째 숫자: 1^2 = 1마지막 숫자: (n-2)^2 1부터 n까지의 제곱의 합 공식 = n(n+1)(2n+1) / 6 ∑(k(k + 1) / 2)를 풀어서 정리하는 과정:먼저, k(k + 1) / 2를 전개, (k^2 + k) / 2이걸 시그마 식에 넣으면 ∑((k^2 + k) / 2)시그..

문제를 풀다보면 자주 출제되는 개념이 있다.약수, 배수, 소수 + 최대공약수, 최소공배수, 소인수분해...'안다'고 해서 끝나는게 아니라 이해 → 풀이 → 최적화 까지 가야하므로 헷갈릴때가 많다.이참에 정리해두려고 한다.문제https://www.acmicpc.net/step/10 최대공약수 (GCD, Greatest Common Divisor)약수: 어떤 수를 나누었을때 나누어 떨어지는 수.최대공약수는 두 수의 공통된 약수 중 가장 큰 수를 말한다. math.gcd()Python에는 math모듈이 있는데, 이 모듈의 gcd()함수를 사용하면 최대공약수를 쉽게 구할 수 있다.import mathdef gcd(a, b): return math.gcd(a, b)print(gcd(24, 36)) # 12..

파이썬의 편리한 기능들을 소개해볼까한다.물론 개인 메모겸 적는것이므로 그닥 유용하진 않을수도 있다.  문제 풀다가 발견def is_correct(s): stack = [] for char in s: if char == "(": stack.append(char) else: if not stack: return False stack.pop() return not stackreturn not stack: 조건문의 결과를 boolean으로 반환해준다. stack이 비어있다면(not stack) True, 비어있지 않다면 False를 반환한다. 오... 역시 파이톤! 아래부터는 자주 쓰이..

문제https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있..