본문 바로가기
728x90
반응형

코딩

알고리즘 - Python / 백준 - 11726번 : 2Xn 타일링 11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 DP문제 이므로 점화식을 찾는다. 1, 2, 3, 4 단계까지 직접 찾아본후 첫 사각형이 세로 1개일때와 가로 2개일때로 구분하면 된다는 사실을 알았다 이를 통해 점화식 dp[i] = dp[i-1] + dp[i-2] 를 찾았다 전체 크기만큼 돌려 DP 배열을 모두 구한후 원하는 답을 출력하자 import sys dp = [0]*1001 dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 for i in ra.. 더보기
알고리즘 - Python / 백준 - 9375번 : 패션왕 신해빈 9375번: 패션왕 신해빈 (acmicpc.net) 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 의류의 이름이 아니라 종류로 구분하여 종류별로 옷이 몇개 존재하는 지가 중요함 의류 종류 개수를 파악해야 하므로 딕셔너리를 통해서 의류 종류를 구분함 구분된 각 의류 종류수를 전체 경우의 수를 구하는 식에 넣어 답을 구함 import sys n = int(sys.stdin.readline()) for _ in ra.. 더보기
알고리즘 - Python / 백준 - 1003번 : 피보나치 함수 1003번: 피보나치 함수 (acmicpc.net) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 DP 문제 이므로 점화식을 먼저 찾는다 문제에 친절하게 모든 경우에 대해 점화식을 설명해두었다 구한 점화식을 통해 모든 DP 배열을 채우고 원하는 답을 출력하면 된다 import sys stack = [[0 for i in range(2)] for j in range(41)] n = int(sys.stdin.readline()) stack[0][0] = 1 stack[1][1] = 1 for i in range(2,41): stack[i][0] = stack[i-1][0] + stack[i-2][0] .. 더보기
알고리즘 - Python / 백준 - 9461번 : 파도반 수열 9461번: 파도반 수열 (acmicpc.net) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 DP 문제이므로 점화식을 먼저 찾는다 점화식을 찾기위해 해당되는 수열을 처음 부터 나열하여 규칙을 찾아본다 DP[i] = DP[i-1] + DP[i+5] 라는 점화식을 찾았으므로 이를 통해 전체 DP 배열을 구하고 답을 내면 된다 import sys stack = [0,1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ] for i in range(11,101): stack.append(stack[i-1] + .. 더보기
알고리즘 - Python / 백준 - 2579번 : 계단 오르기 2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 DP 문제이므로 먼저 점화식을 찾아 정리한다. 연속해서 3개의 계단을 밟으면 안되고 점수를 더해야 하므로 이를 통해 점화식을 세울 수 있다. arrays 라는 계단별 점수 배열과 dp 배열을 동시에 이용해 각 계단별 최대 점수를 구한다. 각 계단마다 나올 수 있는 값의 MAX 값을 찾아 마지막 계단까지 계산해 답을 출력한다. import sys n = int(sys.stdin.readline()) arrays = [0].. 더보기
알고리즘 - Python / 백준 - 6603번 : 로또 6603번: 로또 (acmicpc.net) 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 입력 받은 수들을 배열에 저장한다 이후 배열을 정렬하고 combinations 을 통해서 나올 수 있는 모든 경우를 구하고 출력한다. import sys from itertools import combinations while True: n = list(map(int, sys.stdin.readline().split())) if n[0] == 0: break n.pop(0) n.sort() ans = l.. 더보기
알고리즘 - Python / 백준 - 14397번 : 해변 14397번: 해변 (acmicpc.net) 14397번: 해변 단위 정육각형 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하시오. 해변은 정육각형의 변 중에서 한 쪽은 물인데, 한 쪽은 땅인 곳을 의미한다. www.acmicpc.net 난이도 치고 제출이 적은 것 같아 궁금해서 풀어본 문제 , 어렵진 않았지만 조금 귀찮은 방법으로 풀었었다. 풀이 한줄씩 입력받은 지형을 2차원 배열에 저장한다. 육지와 바다 타일이 육각형 이므로 홀수줄과 짝수줄을 분리하여 위 , 아래 , 좌우의 해변 수를 센다. 연산 방향이 왼쪽에서 오른쪽 , 위에서 아래 이므로 중복되지 않도록 연산방향에 해당되는 해변 수만 체크한다. import sys count = int(0) n , m = map(int .. 더보기
알고리즘 - Python / 백준 - 1463번 : 1로 만들기 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 DP 문제 이므로 점화식을 찾는다. 3가지 연산에 대해서 점화식을 세우고 각 점화식의 결과 중 최소값을 택하여 DP 배열에 넣는다. 전체 DP 배열을 모두 구한후 해당하는 DP[N]을 출력한다. import sys n = int(sys.stdin.readline()) dp = [0,0,1,1] for i in range(4,1000001): dp.append(0) dp33 = 1000000 dp22 = 1000000 if i % 3 == 0: dp33 = dp[int(i/3)] if i % 2 == 0: dp22 = dp.. 더보기
반응형

티스토리툴바