데굴데굴

10845번: 큐 (acmicpc.net) 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 분명 맞게 푼 것 같았는데 답과는 다르게 출력돼서 뭐지..? 했는데 queue를 for문 내에 정의한 걸 디버깅하다가 깨달았다^^ 그리고 pop을 수행할 때에도 리턴한 값을 출력하기 위해서 print()를 씌워줘야 한다. 비슷한 스택 문제를 풀어봤어서 비교적 수월하게 풀 수 있었다. 이 문제도 역시 n의 입력이 1부터 10000까지 주어지기 때문에 빠른 처리를 위해서 sys 모듈을 사용해야 한다. n도 명..

9012번: 괄호 (acmicpc.net) 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택의 원리를 활용하여 푸는 문제이다. 괄호가 일련으로 입력되면 그 괄호들의 쌍이 서로 맞는지 판단하여 YES, NO를 출력해야 한다. 나의 시도 처음에는 stack이라는 이름의 리스트를 만들어서 거기에 append, pop하는 방식으로 시도했다. 왼쪽 괄호가 나오면 stack에 append 해주고, 오른쪽 괄호가 나오면 stack에 있는 왼쪽 괄호를 팝하여 stack을 비운다. 반복적으로..

10828번: 스택 (acmicpc.net) 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 오늘 자료구조 강의에서 스택 공부한 김에 백준에서 스택 문제를 풀어보았다. 다른 경우는 명령어만 입력되는데 push는 명령어와 값이 같이 입력되는 형태라 input에서 어떻게 나눠줘야 할 지 고민이 많았다. input().split()으로 하면 다른 명렁어 처리에서 오류가 발생하고, 리스트는 시간초과가 발생한다. 결국 구글링해보니 대부분이 시간초과 때문에 sys.stdin.readline()을 활용하고..

10870번: 피보나치 수 5 (acmicpc.net) 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 재귀함수를 이용하여 피보나치 수를 만들어야 한다. 피보나치 수열 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 ... n을 입력받은 후 n번째 피보나치 수를 출력해야 한다. ex) n = 5, 출력값은 3 n = int(input()) def fibonacci(n): if n

10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 0보다 크거나 같은 정수 N이 주어졌을 때 N! 출력하기 * 재귀함수를 사용할 것. 참고링크: 백준 10872 [파이썬] 팩토리얼 (=계승) (tistory.com) n = int(input()) # n 입력받기 def factorial(i): res = 1 if i > 0: res = i * factorial(i - 1) return res print(factorial(n)) 팩토리얼의 성질 n! = n*(n-1)! 이용하기 0! = 1이므로 res의 초기값을 1로 지정해둔 후 0을 입력받았을 때에는 아무런 연산도 거치지 않고 res만 출력되도록 함. - 재귀함수는..

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 소수: 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수 골드바흐의 추측: 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 이러한 수를 골드바흐 수라고 함. 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 함. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재함. 2보다 큰 짝수 n이 주어졌을 때 n의 골드바흐 파티션을 출력하는 프로그램 작성 만약 파티션이 여러 가지인 경우에는 두 소..

4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 베르트랑 공준 - 임의의 자연수 n에 대하여 n보다 크고 2n보다 작거나 같은 소수는 적어도 하나 존재한다. ex) 10보다 크고 20보다 작거나 같은 소수는 4개 {11,13, 15, 19} 14보다 크고 28보다 작거나 같은 소수는 3개 {17, 19, 23} 자연수 n이 주어졌을 때 n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 프로그램 작성 [구조] 소수를 찾는 함수를 정의 주어진 범위에..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 설명에 '에라토스테네스의 체'로 풀어보라고 되어 있어서 찾아보았다. 에라토스테네스의 체의 계산 방식은 다음과 같다. 1을 제거함 지워지지 않은 수 중에 제일 작은 2를 소수로 선택 나머지 2의 배수를 모두 지움 지워지지 않은 수 중에 제일 작은 3을 소수로 선택 나머지 3의 배수를 싹 지움 5, 7, 11도 이렇게 반복해서 배수들을 싹 지운다. 이 메커니즘을 활용하여 코드를 짜면 이렇게 된다고 한다. 구글링함. def isPrime(num): if num == 1: return False el..