링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 소요시간: 13분 22초 설계하기(접근방법) 1. n을 입력받는다 2. 알고리즘 해석 1) n = 1일 때 1 개 2) n = 2일 때 가로로 놓는 방법과 세로로 놓는 방법 -> 2가지 3) n = 3일 때 세로로 3 -> 1가지 (가로 2 세로 1) * 2 -> 2가지 총 : 3가지 4) n = 4일 때 가로 4 -> 1가지 세로 4 -> 1가지 가로 2 세로 2 -> 3가지 총 : 5가지 세로 직사각..
링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 소요시간 : 설계하기(접근방법) 1. 테스트 케이스를 입력받고, dp[]를 선언한다 2. 알고리즘해석 1) 정수 3을 생각해보자 3은 3, 2+1,1+2, 1+1+1로 나눌 수 있다 2) 정수 2를 생각해보자 2는 2, 1+1로 나눌 수 있다. 3) 정수 1을 생각해보자 1은 1로 나타낼 수 있다. 4) 정수 4를 생각해보자 5) 정수 5를 생각해보자 1+1+1+1+1 1,1,1,2 * 4 경우 1,2,2 * 3 경우 1,1,3 * 3 경우 2,3 * 2 경우 dp[1] = 1 d..
링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 소요시간:34분 10초 설계하기(접근방법) 1. n을 입력받는다. 2. 알고리즘 해석 1) 그리디로 하는 경우와 그 예외 사항 10 5 4 2 1 : 5번 10 9 3 1 : 4번 다음의 경우와 같이 그리디로 하는 경우(3으로 나누어지면 나눔, 안되면 2로 나눔, 안되면 1을 뺀다) 가장 효율적인 경우의 수가 아니다. 따라서 아래에서부터 수를 저장하는 동적 계획법으로 문제를 해결해야 할 것이다 2) 동적 계획법 총 3가지 검증 방법이 있다 1) n이 3으로 나누어지면 dp[n//3]의 값 2)n이..
링크 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 소요시간: X 설계하기(접근방법) 동적 계획법으로 풀어보기 1. n을 입력받는다 2. 알고리즘 해석 돌을 가져가는 경우 1 개 or 3 개 (2개만 가져가는 경우는 없다) 1 = 상근, 0 = 창영 돌이 1개 일때 1 -> 상근이가 가져간다 rock[1] = 1 돌이 2개 일때 1, 1 -> 창영이가 가져간다 rock[2] = 0 돌이 3개 일때 3 or 1,1,1 -> 상근이가 가져간다 rock[3] = 1 돌이 4개 일때 1,3 or 3,1 or 1,1,1,1 창영이가 가져간다 rock[4] = 0 ..
링크 : https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 소요시간:22분 12초 설계하기(접근방법) 1. 테스트 케이스를 입력받는다 2. 알고리즘 구현 팩토리얼을 구현한다. ex) 7개 중에 4개를 선택하여 순서와 상관없이 다리가 이어지는 조합(combination)문제다 따라서 7! / ((7-4)! *4!) 을 연산한다. 3. 답을 구현한다. 코드(출력) t = int(input()) def factorial(n): num = 1 fo..
링크 :https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 소요시간: 8분 20초 설계하기(접근방법) 1. n 을 입력받는다 2. 동적계획법 사용하기 메모이제이션 , 나왔던 값 저장하기 3. 피보나치 구현, result 값을 리스트에 apppend 코드(출력) fibo_list = [0, 1] n = int(input()) if n == 0: print(0) elif n == 1: print(1) else:..
링크 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제 소요시간: 시간 많이 초과 설계하기(접근방법) 1. 스위치 개수, 스위치 상태, 입력 횟수, 성별과 번호를 입력받는다 2. 문제 해석 입력 1: 남성의 경우 -> 해당 번호의 배수의 스위치를 invert한다. ex) 3이 입력으로 들어오면 3번째(인덱스 넘버 2), 6번째(인덱스 넘버 5) 를 invert 입력 2: 여성의 경우 (까다로웠다) -> 먼저 해당 번호를 기준으로 좌..
