본문 바로가기

Programming/Algorithm

2018. 09. 01 백준 알고리즘 파이썬 정리 2133 - 타일채우기 소스코드 import sys num = int(sys.stdin.readline()) D = [0 for i in range(num+1)] D[1] = 0 if num >= 2: D[2] = 3 for i in range(3, num+1): D[i] = 3*D[i-2] for j in range(i-4, 0, -2): D[i] += 2*D[j] if i % 2 == 0: D[i] += 2 sys.stdout.write(str(D[num])) 코멘트 2n때랑 다르게 아래에 한칸이 더 생겨버렸으므로 더 생각을 해야만 했던 문제. 결국엔 초반 패턴을 직접 그려서 경우의 수를 구한 다음에, 그 이후에 나오는 것들은 다이나믹 프로그래밍으로 구하는 형식이었다. 결국 초기 값은 직접 파악해야한.. 더보기
2018. 08. 15 백준 저지 알고리즘 정리(파이썬) 문제 1912 - 연속합 링크 - https://www.acmicpc.net/problem/1912 소스코드 import sys num = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().rstrip().split())) D = [0 for i in range(num)] D[0] = arr[0] for i in range(1, num): D[i] = max(D[i-1] + arr[i], arr[i]) sys.stdout.write(str(max(D))) 코멘트 솔직히 봐도 봐도 봐도 계속 틀려서 고심 끝에 답을 봐야했던 문제였다. 문제 접근 방법부터가 잘못 되었었다. 나는 D를 "해당 index까지 범위에서 가장 큰 연속합"으로 정의.. 더보기
2018. 08. 14 백준 저지 알고리즘 정리(파이썬) 문제 2156번 - 포도주 시식 링크 - https://www.acmicpc.net/problem/2156 소스코드 import sys wine = [] num = int(sys.stdin.readline()) for i in range(num): wine.append(int(sys.stdin.readline())) T = [[0 for i in range(2)] for j in range(num+1)] for i in range(1, num+1): T[i][0] = max(T[i-1]) if i > 1: T[i][1] = max(T[i-2][0] + wine[i-1] + wine[i-2], T[i-1][0] + wine[i-1]) else: T[i][1] = wine[i-1] sys.stdout.wri.. 더보기
2018. 08. 13 백준 저지 알고리즘 정리(파이썬) 오늘은 별거 없다. 문제 9465 - 스티커 링크 - https://www.acmicpc.net/problem/9465 소스코드 import sys num = int(sys.stdin.readline()) result = '' for i in range(num): size = int(sys.stdin.readline()) arr = [[0] * 2 for i in range(size)] line = sys.stdin.readline().rstrip() line += ' ' + sys.stdin.readline().rstrip() for (j, e) in enumerate(line.split()): arr[j % size][j // size] = int(e) T = [[0] * 3 for i in rang.. 더보기
2018.08.12 백준 저지 알고리즘 정리(파이썬) 문제 1463 - 1로 만들기 링크 - https://www.acmicpc.net/problem/1463 소스코드 import sys import math num = int(sys.stdin.readline()) arr = [0]*(num+1) for i in range(1, num+1): if i == 1: continue val = [] if i % 3 == 0: val.append(arr[i//3] + 1) if i % 2 == 0: val.append(arr[i//2] + 1) val.append(arr[i-1] + 1) arr[i] = min(val) sys.stdout.write(str(arr[num])) 코멘트 딱히 없다. 다이나믹 프로그래밍의 전형적인 예. 문제 11726 - 2xN 타일링.. 더보기
2018. 08. 11 백준 저지 알고리즘 정리(파이썬) 문제 - 1158번 조세퍼스 순열 https://www.acmicpc.net/problem/1158 문제 조세퍼스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 이다. N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000) 출력 예제.. 더보기
2017. 08. 08 알고리즘 정리(백준 저지) 문제 1924번 - 2007년 https://www.acmicpc.net/problem/1924 문제 오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 빈 칸을 사이에 두고 x(1≤x≤12)와 y(1≤y≤31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. 출력 첫째 줄에 x월 y일이 무슨 요일인지에 따라 SUN, MON, TUE, WED, THU, FRI, SAT중 하나를 출력한다. 소스코드 month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] day = ['.. 더보기

티스토리툴바