알고리즘 썸네일형 리스트형 13. FESTIVAL 알고라파덕13. FESTIVAL 소스.#include int a[1010]; int main() { int testcase, n, m; int i, j; double sum, ave, min; scanf("%d", &testcase); while(testcase >= 1) { --testcase; scanf("%d %d", &n, &m); for(i=1; i 더보기 14. TRIANGLEPATH 알고라파덕.14. TRIANGLEPATH 소스.#include void TRIANGLEPATH(); int main() { int testcase; scanf("%d", &testcase); while(testcase >= 1) { --testcase; TRIANGLEPATH(); } return 0; } void TRIANGLEPATH() { int data[105][105] = { 0}; int sum[105][105] = { 0 }; int N, i, j, max = 0; scanf("%d", &N); for(i=1; i 더보기 15. LIS 알고라파덕 LIS 소스.#include void LIS(); int cnt[510][510]; int main() { int testcase; scanf("%d", &testcase); while(testcase >= 1) { --testcase; LIS(); } return 0; } void LIS() { int num[510]; int N, M, i, j, max = 0; scanf("%d", &N); for(i=1; i 더보기 [알고스팟/ALGOSPOT] 15. LIS 안녕하세요~ 알고라파덕입니다~ 이번 문제는 동적 계획법 관련 문제입니다. 동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법입니다. LIS 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는.. 더보기 [알고스팟/ALGOSPOT] 14. TRIANGLEPATH 안녕하세요~ 알고라파덕입니다~ 이번 문제는 동적 계획법 관련 문제입니다. 동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법입니다. TRIANGLEPATH 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테스트 케이스의 수 C(C 더보기 지금은 시험기간!! 지금은 시험기간입니다... 흑흑 포스팅도 못하고.. 알고리즘 공부도 못하고있네요.. 다다음주 금요일!! 6월19일이 끝난후부터!! 알고리즘, 그리고 다른 공부한것들도 다 올리겠습니다아!! 더보기 [알고스팟/ALGOSPOT] 13. FESTIVAL 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 기초 구현 문제인 FESTIVAL입니다~~ FOR문을 능숙하게 사용하시는 분들은 쉽게 푸실 수 있습니다1 쉬어가요! 문제 개요 테스트 케이스가 주어지고 각 테스트 케이스마다 날짜 수와 공연 날짜 수가 입력된다.그리고 날짜 수마다 비용이 입력된다. 그러면 여기서 우리는 연속으로 공연을 할 것인데 공연장 최소 평균 임대룔를 구해야 한다. K일 K+1일 K+2일 대여해도 되지만 최소로 하루당 임대비용이 작은 것을 찾아야 한다. 문제 풀이 간단한 구현문제이다. 쉬어가자 FOR문이 이렇게 작동할 수 있도록 구현하고 매번 평균값을 구하여 MIN값과 비교한다. 문제 출처 : https://algospot.com/judge/problem/read/.. 더보기 [알고스팟/ALGOSPOT] 12. STARCRAFT 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 STARCRAFT라는 문제인데요! 수학 문제입니다 ㅎㅎ.. 문제 개요 2K-1판 K선승제로 우리가 이길 확률이 P퍼센트 일 때 2K-1판 K선승제를 하면 우리가 우승할 확률은 어떻게 되는가?? 수학문제 되겠습니다.테스트 케이스가 주어지고, 각 테스트 케이스마다 확률 P와 판수 K가 주어집니다. 소수점 첫째 자리에서 반올림하여 정수를 출력합니다. 문제 풀이 수학적으로 담을 구할 수 있습니다.한번도 안질 때, 1번질 때, 2번 질 때 ,3번 질 때 등등 경우의 수를 따져보면최종 식이 나오게 됩니다. 최종식에서 K가 10이되면 마지막 계산에서 인트 21억값을 넘어가기 때문에 long int로 변수를 설정하셔야 오답이 나오지 않습니다..(찾.. 더보기 [알고스팟/ALGOSPOT] 11. ORIVIRUS 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 오리바이러스라는 문제입니다! 저는 흠.. 약간 BFS같은 느낌으로 풀어보았습니다~ 문제 개요 테스트 케이스가 입력으로 주어지면 먼저 오리의 수 N이 주어지고 NxN 오리들끼리의 친구관계가 주어집니다. 그리고 여기서 또 테스트 케이스가 나와 개수만큼 처음 바이러스을 갖는 오리의 번호가입력됩니다. 그럼 여기서 처음 2마리의 오리가 바이러스를 다 퍼트렸을 때 감염된 오리의 수를 구해주시면 됩니다. 문제 풀이 먼저 오리들의 친구 관계를 인접 행렬 리스트로 바꾸어 줍니다. 인접 행렬 리스트란 0번째 열에 연결된 노드의 개수, 그리고 1~노드의 개수까지 연결된 노드의 번호를 저장합니다. 인접 행렬 리스트도 따로 블로그에 포스팅하겠습니다. 이렇게.. 더보기 [알고스팟/ALGOSPOT] 10. PACKING 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 10번 문제는 PACKING이라는 문제입니다.!! 이 문제는 동적계획법 대표 문제입니다. 가방 문제라고도 불리구요! 문제 개요 입력에서 테스트 케이스가 주어집니다. 테스트 케이스당 물건의 개수 N과 가방의 용량 W가 주어집니다 그리고 N개의 줄에 걸쳐 물건의 이름과 부피, 절박도(가치)가 주어집니다.N개의 물건을 용량내로 최대한의 가치, 절박도로 채워야 하는 것이 목표입니다. 최대 가치와, 물건 개수, 물건의 이름들을 출력해야 합니다. (경로 추적이 필요합니다~) 문제 풀이 최대 가치만 구하라 하면 동적계획법만을 사용하면 되지만, 물건의 개수와 이름을 구해야하기 때문에 추가적으로 재귀함수를 이용하여 경로를 추적합니다. 동적 계획법 부분 점화.. 더보기 이전 1 2 3 다음
