1. 문제 1952. [모의 SW 역량테스트] 수영장 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권을 사용하여 주어진 1월~12월까지 수영장 이용 계획을 최소 비용으로 이용하고 싶을때, 그러한 최소 비용을 찾는 문제 2. 풀이 다이나믹 프로그래밍을 연습할 수 있는 아주 좋은 문제다 dp[i]를 1~i번째 달까지 사용한 최소 요금으로 정의하자 각각의 i번째 달에 사용할 수 있는 경우의 수는 무엇일까? 1) 1일 이용권을 모두 사용하는 경우 예를 들어 3월에 2일 사용했는데, 2일을 1일 이용권 2번으로 사용할 수 있다 2) ..
1. 문제 17175번: 피보나치는 지겨웡~ (acmicpc.net) 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 피보나치 함수의 호출 횟수를 구하는 문제 2. 풀이 재귀 함수의 호출 횟수를 곧이 곧대로 구하면 풀 수 없다 def fibonacci(n): global cnt cnt += 1 if n < 2: return n return fibonacci(n-2)+fibonacci(n-1) 중간에 cnt를 넣어가지고 cnt를 구하면 함수의 호출횟수가 되는데 n이 조금만 커져도 도저히 시간안에 함수가 끝나질 않..
1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제 2. 풀이 가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다 1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다 그래서 한번 해보면 from sys import stdin n = int(stdin.readline()) dp = [0] * 1000001 dp[1] = 1..
1. 문제1 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선형으로 정삼각형을 만들었을때, 정삼각형의 가장 긴 변의 길이를 구하는 방법은? 2. 풀이1 이런 문제는 그냥 몇개 나열해보면서 규칙을 찾으면 되겠다고 생각하는게 제일 편하다 이런 규칙 찾는 문제가 다이나믹 프로그래밍의 가장 기본형태라고 생각하면 된다 그래서 몇개 해보면 규칙이 나올거야 p(1)부터 p(10)까지는 1,1,1,2,2,3,4,5,7,9라고도 친절하게 나와있고 그림에서 p(1..
1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 주어진 n개의 임의의 수열에서 1개 이상의 연속된 부분 수열을 선택할 때, 가장 큰 합을 출력 2. 나의 풀이 단순한 규칙, 점화식으로는 풀기 어렵다 메모리, 시간제한 문제로 $O(N^2)$으로도 통과하기 어렵다 처음에 i번째부터 j번째까지 수열의 합을 dp[i][j]에 저장해서 테이블을 완성하려고 했는데 n의 최대가 100000이라 10만*10만 만들자 마자 메모리 초과 from sys impo..
1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1이상의 정수 x가 주어질때, 1) x가 3으로 나누어 떨어지면 3으로 나눈다 2) x가 2로 나누어 떨어지면 2로 나눈다 3) x에서 1을 뺀다 3가지 연산을 적절히 사용해서 1을 만들고 싶다 연산을 사용한 횟수의 최솟값을 출력한다면? 2. 나의 풀이 다이나믹 프로그래밍 연습문제니까 다이나믹 프로그래밍을 써야겠지 기본이 바텀업이고 반복문 구현이라고 배웠으니까 이에 따라보자 작은 문제부터 구해놓고, 이들을 이용해서 반복문을 구현한다면.. 1이상이니까 dp[0] = 0, 1은 연산을 안해도 1이니까 d..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
