전체 글

[Python] 6588 - 골드바흐의 추측 (실버1) : 에라토스테네스의 체

1. 문제 설명 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 오일러..굉장히 존경스러운 수학자시긴 하지만 시험 기간에는 별로 반갑지 않은..ㅠㅠㅠ 2. 아이디어 소수를 구하는 가장 빠른 방법이다. (아마도..?) "소수를 구하는 문제 -> 에라토스테네스의 체"라고 머리에 쑤셔넣어놓아야 할 정도로 중요하다. 나도 간만에 봤더니 잊어 먹어서 다시 공부했지만 ㅎㅎ. 에라토스테네스의 체 이 방법을 사용하지 않으면..시간 초과..

[Python] 2504 - 괄호의 값 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 2. 아이디어 굉장히 유명한 문제 중 하나로 전형적인 stack 자료구조를 이용한 풀이방법을 썼다. 입력받은 값이 '[', '(', ')', '(', '(', ')', '[', ']', ')', ']'라고 하자. 우선 스택에 '['라는 정보를 담아놓고 그 다음에 들어오는 정보를 확인한다. '('는 '['와 매칭되는 쌍이 아니므로 마찬가지로 스택에 쌓는다. 다음 정보는 ')'이므로..

[Python] 2630 - 색종이 만들기 (실버2)

1. 문제 설명 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 2. 아이디어 아예 분할 탐색을 쓰라고 문제에 사진까지 첨부해가며 어필하고 있다. N = 2^k (1

[Python] 17427 - 약수의 합2 (실버2)

1. 문제 설명 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 2. 아이디어 N의 범위가 1,000,000이므로 이걸 무식하게 약수를 매번 구하는 이중 for문으로 해결하려 하면 시간 복잡도가 O(n√n)이므로 0.5초 내로 해결하는 것은 무리다. 이럴 때 필요한 것이 바로 "music is my life". 무식이 내 삶이란 소리다. 직접 한번 패턴을 분석해보자. 1부터 10까지 약..