본문 바로가기

Programming

 (110)
배낭 알고리즘(Knapsack Algorithm) 1. 개념 무게 W를 감당할 수 있는 배낭이 있을 때 n개 종류의 다른 가치를 가진 물건을 선택해서 넣어 최대의 가치를 구하는 알고리즘이다. Knapsack 문제는 0-1 Knapsack과 Fraction Knapsack이 있다. 0-1 Knapsack은 물건을 자를 수 없고, Fraction Knapsack은 자를 수 있다. 2. 구현 물건을 하나씩 담아보면서 용량을 초과하면 담지 않고, 용량을 초과하지 않는다면 담아보고 가치가 더 크면 그 용량의 가치를 바꿔준다. 점화식은 다음과 같다. D[i][j] = max(D[i-1][j-weight[i]]+price[i], D[i-1][j]);여기서 D[i][j] 는 D[capacity][n], capacity = 배낭의 용량, n = 물건의 개수로 선언한다...
[백준 1535번] 안녕 link : https://www.acmicpc.net/problem/1535 안녕 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB122361241050.617%문제세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면,..
[백준 1837번] 암호제작 link : https://www.acmicpc.net/problem/1837 암호제작 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB138624118625.514%문제원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 ..
[백준 1644번] 소수의 연속합 link : https://www.acmicpc.net/problem/1644 소수의 연속합 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB44861824133341.787%문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5..
[백준 11653번] 소인수분해 link : https://www.acmicpc.net/problem/11653 소인수분해 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB58593209258155.458%문제정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.입력첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.출력N의 인수를 한 줄에 하나씩 증가하는 순서대로 출력한다.예제 입력 1 복사72 예제 출력 1 복사2 2 2 3 3 예제 입력 2 복사3 예제 출력 2 복사3 예제 입력 3 복사6 예제 출력 3 복사2 3 예제 입력 4 복사2 예제 출력 4 복사2 예제 입력 5 복사9991 예제 출력 5 복사97 103 소인수분해 문제이다. 그냥 풀었다. 123456789101112131415161..
[백준 2960번] 에라토스테네스의 체 link : https://www.acmicpc.net/problem/2960 에라토스테네스의 체 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB51302590227252.027%문제에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 숫자 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 숫자를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) ..
최소 공통 조상(Lowest Common Ancestor / LCA) 1. 개념 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A와 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점이다. 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A 혹은 A의 조상이면서 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 2. 구현 보통 parent[i] 처럼 일차원 배열로 표현하던 부모 배열을 parent[u][k] 2차원 배열로 만든다. 이것이 뜻하는 바는 정점 u의 2^k 번째 부모라는 뜻이다. 이것을 풀어쓰면 2^(k+1) = 2^k + 2^k 이므로 , parent[u][k+1] = parent[parent[u][k]][k] 의 점화식을 구할 수 있다. 이 점화식에서 수 있듯이 k=i 일 때의 정보로 k=i..
에라토스테네스의 체(get Prime Number) 소수를 구할때 최대로 효율적인 알고리즘을 만드는데 도움이 되는 것인데, 따로 개념을 설명하지는 않겠다. 내가 보기 위한 메모용 글이다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include#include#include using namespace std; #define MAX 50001 int num[MAX]; void func(int n){ int sqt = sqrt(n); for(int i=2; i n; for(int i=2;i

티스토리툴바