곽로그

문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 - 2 X n 타일링 문제와 비슷하다 - F(N) 을 구할때 F(N-1) + F(N-2)에서 F(N-2) 즉 2*(N-2)의 직사각형을 구하는 방법은 마지막에 2*2타일을 채우는 방법, 1*2 타일로 채우는 방법 2가지가 있으므로 F(N) = F(N-1) + F(N-2) *2가 된다 [백준 11726, Java] 2 Xn 타일링 문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 ..

문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 1.처음 접근 방법 (1 X 2 타일의 갯수를 기준으로) - 1 X 2 타일을 0개 쓴다. 2개 쓴다, 4개 쓴다를 기준으로 잡았다. 예를 들어 N = 5라고 했을 때 1 X 2 타일을 0 개쓰면 2 X1 타일로만 채우게 되므로 경우의 수는 1이다. 1 X 2 타일을 1개를 쓴다고 했을 때, 1 X 2 타일 위 또는 아래에는 반드시 1 X 2 타일이 올 수 밖에 없으므로 1X2 타일은 짝수개를 쓰게 된다. 따라서 1 X ..

문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net check * 두번째 풀이 외우기 1. 처음 푼 풀이 (단순재귀) - 모든 경우의 수를 재귀를 이용해서 풀었다. - 이때의 시간 복잡도는 모든 수가 3, 2로 나누어 떨어진다고 했을때 하나의 함수가 3개의 함수를 호출하게 된다. 따라서 3의 N-1 제곱이 되고 입력의 최대는 10의 6제곱이니까 시간초과가 나게 된다. check - 위 문제는 최소의 값을 구하는 거다. 따라서 함수를 호출하였을때 연산횟수가 이전에 호출했던 함수의 연산횟수보다 크면 다시 호출할 필요가 없다. 위의 경우에 (2,1)을 호출했으면 (2,3)을 ..

문제 www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 1. 1부터 1,000,000까지 소수를 구한다(에라토스테네스의 체 이용) 2. 입력(num)으로 0이 나오기 전까지 반복문을 수행한다 2-1 1번에서 구한 소수배열(isPrimeNum)을 순회(n)하면서 n, num-n이 모두 소수일때 반복문을 종료한다 check 1. 에라토스테네스의 체의 시간복잡도는 nlog(log n)이다. 따라서 1,000,000인경우 근사값 778,1..

문제 www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net check 1. 소수의 정의를 이용하여 3가지로 풀 수 있다. 2. isPrimeNum3에서 두번째 for문에 n

문제 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net check 1. 어렵게 보인다, 복잡해 보인다 라는 생각이 들면 어짜피 못풀거다 라는 생각에 생각하기를 멈춘다. 따지고 보면 그렇게 어려운게 아닌데 지레짐작해서 포기해버린다. 2. 예전 코드를 보니 '소수는 귀찮다'라는 생각에 풀다 안 푼 흔적이 있다. 3. 막상 해보면 별거 아니다. 소스코드 package november.first; import java.io.BufferedReader; import java.io.BufferedWri..

문제 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 1. 순회 (시간초과) - 오큰수를 순회로 풀면 시간 초과가 난다. 즉 수열을 순회하면서 index번째 수의 오큰수를 구할 때, 다시 index+1 부터 순회를 하게되면 시간 복잡도는 N제곱이 되어서 시간초과가 난다. 2. 스택이용 - A의 오큰수 B를 구하는 게 아닌, B가 어떤 수의 오큰수가 되는지를 역으로 구해야한다. - B가 A의 오큰수이면 A와 B사이의 수 중에서 B가 가장 큰 수인 것을 이용한다. - 스..

문제 www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net check 1. 천천히 꾸준히 2020년 1월에 푼 쇠막대기를 보니 이 문제를 왜 어려워했나 하는 생각이 든다. 천천히 꾸준히 하다보면 지금 어려워 하는 문제도 언젠간 쉬워지겠지 2. 구분 같은 괄호라도 상황에 따라 역할이 다르다. )의 경우 바로 앞 괄호가 (이면 레이저이고 아닌 경우 나무의 끝이다. )의 두가지 상태에 따라 구현을 다르게 하면 된다. 3. 다시풀기 종종 예전에 풀었던 문제를 다시 풀어야겠다. 얼만..