1003 https://www.acmicpc.net/problem/1003 당연히 시간초과나는 코드 아래 풀이 방식은 문제 조건은 잘 만족했으나, 당연히 시간 초과가 남 함수 호출이 $O(1.6^n)$의 시간 복잡도를 가지기 때문 다만 주시해볼만한 부분은, -1 번째 항을 사용했다는 점 결국 0이 호출되는 횟수는 fibo(x - 1), 1이 호출되는 횟수는 fibo(x) 다만 x가 0인 경우 0이 호출되는 횟수는 1 그렇기 때문에, fibo(-1)을 1로 정의 이렇게 하면 fibo(1) == fibo(0) + fibo(-1) == 1 이 되어서 정의에도 어긋나지 않음 import sys num_test = int(sys.

10757 https://www.acmicpc.net/problem/10757 단순한 생각 가장 단순하면서도 파이썬스러운 방식으로 다음과 같이 구현할 수 있다 파이썬은 임의의 아주 큰 정수 저장을 지원하기 때문에, 문제없이 문제를 풀 수 있다 Java에서는 상상도 못할 일… import sys a, b = map(int, sys.stdin.readline().split()) print(A + B) list로 구현해 보기 다음과 같이 문자열을 이용해 구현 가능 입력 받은 숫자를 String list로 변경 후, 각 자릿수끼리 더하면 됨 만약 한 숫자가 다른 숫자보다 자릿수가 작다면, 자릿수를 초과할 때는 0을 더해주면 됨 아랫 자리수부터 더해서, 더한 결과를 list에 append로 저장 당연하지만 insert(0, x)는 O(N)이므로, 사용이 지양됨 이 경우 원래 자릿수의 역순으로 저장되므로, 출력도 역순으로 하면 됨 데이터 전체를 숫자로 저장하지 않고도 연산이 가능 import sys a, b = map(list, sys.

BOJ 1016 문제 설명 문제: 백준 1016 이 문제는 m 이상 M 이하의 모든 제곱 ㄴㄴ 수를 구하면 됩니다. 제곱 ㄴㄴ수란 어떠한 제곱수로도 나누어지지 않는 수를 의미합니다. m은 10^12 이하의 자연수이고, M은 m보다 최대 10^6 큰 수입니다. m과 M의 상한이 아주 크기때문에 $O(M)$의 시간으로는 풀기 힘든 문제입니다. 사전 지식 에라토스테네스의 체 이 문제를 보기 전에 에라토스테네스의 체를 다룬 이전 포스트를 보고 오시는 것을 추천드립니다. 이 문제와 긴밀히 연결되어 있고 중간중간 이전 문제에 대한 설명을 인용할 것입니다.

BOJ 1929 문제 설명 문제: 백준 1929 이 문제는 주어진 두 수 사이의 모든 소수를 찾는 문제입니다. 주어지는 M,N 이 $10^6$이하이므로 $O(N^2)$이상의 시간 복잡도가 아닌 이상 크게 시간 제약을 받는 문제는 아닙니다. 사전 지식 소수 판별 시간 복잡도 다들 아시겠지만 소수(素數)란 자기 자신과 1을 제외하고는 어떤 자연수로도 나누어지지 않는 1보다 큰 자연수를 의미합니다. 대표적으로 2, 3, 5, 7, 11 등등이 있습니다. 그렇다면 특정한 자연수가 소수인지를 알 수 있는 방법은 뭘까요? 간단합니다.

BOJ 1806 문제 설명 문제: 백준 1806 이 문제는 자연수 배열을 받아서, 부분합 중 주어진 값을 넘는 가장 짧은 부분합의 길이를 구하는 문제입니다. 배열의 길이 N이 100,000 이하이므로, $O(N^2)$의 알고리즘으로는 주어진 시간 내에 푸는 것은 사실상 불가능합니다. 사전 지식 이 문제를 풀기 위해, two pointers(투 포인터) 알고리즘과 그것을 사용하는 이유에 대해 간단하게 설명해보려 합니다. 그전에 용어를 정리하고 갑시다. 어떤 배열 arr과 이 배열의 인덱스 A, B에 대해, A 이상 B 미만의 인덱스를 가지는 부분 배열을 [A, B)라고 표현하고, arr[A]부터 arr[B-1]까지의 모든 값을 합친 것을 [A, B)의 부분합이라고 합시다.

BOJ 1074 문제 설명 문제 : 백준 1074 이 문제는 $2^N * 2^N$의 크기를 가진 2차원 배열을 특정 규칙에 따라 각 칸을 방문하고, 그 순서대로 0부터 번호를 새긴 다음 r행 c열의 값을 찾아내는 문제입니다. 문제에서 설명된 바와 같이 작은 사각형부터 큰 사각형까지 모두 Z방향으로 방문하면 됩니다. 사전 지식 이 문제는 재귀에 대한 기본적인 지식만 있으면 풀 수 있기 때문에 별도의 설명을 하지는 않겠습니다. 접근 방법 아주 단순한 접근 코딩을 제대로 배우기도 전에 이 문제를 접하고, “재귀를 이용해 모든 칸을 다 채운 다음에 r행 c열의 값을 알면 되지 않을까?

BOJ 2239 문제 설명 문제: 백준 2239 매우 간단한 문제입니다. 각 칸이 한 자리 정수로 이루어진 9*9 격자 칸이 입력이 주어집니다. 0은 빈칸을, 0이 아닌 수는 스도쿠에 미리 들어가 있는 수를 의미합니다. 스도쿠 규칙에 따라 빈칸을 채워서 그대로 출력하면 됩니다. 사전 지식 문제를 푸는데 가장 중요한 점은 백트래킹이라는 기법입니다. N-Queen 문제의 해법으로 널리 알려져 있는 풀이법이고, 여기서는 간단하게만 설명할 예정입니다. 자세한 설명은 참고 자료를 확인하시기 바랍니다. 백트래킹을 쉽게 설명하자면 일종의 미로 찾기라고 생각하시면 됩니다.

BOJ 1019 문제 설명 문제: 백준 1019 이 문제는 겉보기에는 굉장히 간단한 문제입니다. N을 입력받아, 1부터 N까지 모든 수에 대해 0부터 9까지의 숫자가 몇 번씩 나왔는지를 구하면 됩니다. 입 출력이 간단하고, 언뜻 보면 간단한 반복문을 통해 풀 수 있을 것이라 생각되지만, N의 조건을 잘 살펴봐야 합니다. N이 $10^9$이하의 자연수라는 사실 때문에 $O(N)$보다도 더 빠른 알고리즘이 필요합니다. 사전 지식 이 문제를 푸는 데는 큰 사전 지식을 필요로 하지 않습니다. 다만 문제를 푸는데 도움이 되었던 사실 몇 가지를 짚어보려 합니다.