1. 문제 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 주어진 수열의 점화식에서 A[N]을 구하는 문제 2. 풀이 처음에 그냥 이게 문제?하면서 점화식 그대로 작성했는데 메모리 초과남.. from sys import stdin n,p,q = map(int,stdin.readline().split()) dp = [0]*(n+1) dp[0] = 1 for i in range(1,n+1): dp[i] = dp[i//p]+dp[i//q] print(dp[n]) n의 최대 범위는 $10^{12}$인데 메모리 제한은 128mb라서 그런 것 같다 근데 dp[n]을 구할려면, dp[n//p]와 d..
1. 문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리라고 부르고 모든 집의 치킨 거리의 합이 해당 도시의 치킨 거리이다. 최대 m개의 치킨 집만 선택해서 가능한 도시의 치킨 거리의 최솟값은 2. 풀이 항상.. 문제를 잘 읽어야한다 "어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리" 이것부터 제대로 보질 못했는데.. 빨리 봐서 다행이긴해 조합을 구현한..
1. 문제 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이차원 배열에 주어진 블록중 하나를 놓아봐서 거기에 적힌 수의 합의 최댓값을 구하는 문제 2. 풀이 항상 이걸 어떻게 해?라고 두려워하지말고 어렵게 생각하지 말고 성실하게 완전탐색을 구현하면 풀린다는 생각으로 심플하게 5가지 블록의 회전,대칭 모든 가능한 경우를 만들어서 모든 좌표에 대해 조사해보면 진짜로 최댓값이 나오긴 해 근데 변수를 어디서 초기화해야하는지, 그런 실수가 쉽게 나오더라 블록의 회전,대..
1. 문제 16198번: 에너지 모으기 (acmicpc.net) 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 2. 풀이 기본적인 dfs 완전탐색 문제다 조건대로 구현하면 될 것같다 에너지 리스트에서 0번과 n-1번은 고를 수 없으니까 1번부터 n-2번까지 모두 골라본다 고른 번호가 k번이면.. k-1번과 k+1번의 원소를 곱해서 누적합을 시킨다 k번 원소를 삭제한다 dfs로 재귀호출 for k in range(1,w-1): de = e + (w_list[k-1]*w_list[k+1]) w_list_co..
1. 문제 17478번: 재귀함수가 뭔가요? (acmicpc.net) 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 출력 예시를 보고, 재귀함수로 똑같이 출력하는 문제 2. 풀이 from sys import stdin def chatbot(n,s1,s2,s3,s4,s5,s6): if n == 0: print(s1) print(s6) print(s5) else: print(s1) print(s2) print(s3) print(s4) chatbot(n-1,'____'+s1,'____'+s2,'____'+s3,'..
1. 문제 사용할 수 있는 동전이 1원,4원,6원이 있다. 거스름돈 8원을 내주기 위해 사용할 수 있는 최소 동전의 개수는? 그리디 방법으로 접근하면, 가장 큰것부터 내주면 최소라고 생각할 수 있으니까, 6원, 1원, 1원 그러나 실제 최적해는 4원, 4원으로 2개이다 그리디 방법이 항상 최적해를 보장해주지 않아서, 다른 방법으로 문제를 해결할 필요가 있다 - 완전 검색(백트래킹 이용가능) - 다이나믹 프로그래밍 2. 재귀 알고리즘 3가지 동전 각각 선택하면 작은 부분문제가 생긴다 1원짜리 동전을 선택하면 >> 7원에 대한 최적해 + 1원 1개 >> 7원에 대한 최적해는 1원,4원,6원으로 다시 나눌 수 있음 4원짜리 동전을 선택하면 >> 4원에 대한 최적해 + 4원 1개 6원짜리 동전을 선택하면 >> ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
