알고리즘
-
백준 11568번: 민균이의 계략최장 증가 수열(Long Increasing Subsequence) 2018. 7. 1. 19:43
https://www.acmicpc.net/problem/11568 LIS 문제 키워드 - DP, LIS O(n^2) Source #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long /* * @memory - 2380 kb * @time - 56 ms */ int arr[1001]; int dp[1001]; int main() { cin.tie(0); std::ios::sync_w..
-
백준 10986번: 나머지 합다이나믹프로그래밍(DP) 2018. 7. 1. 19:20
https://www.acmicpc.net/problem/10986 1. 문제수 N개 A1, A2, ..., AN이 주어진다. 이 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 2. 알고리즘키워드 - DP, 부분합참고 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-10986 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #..
-
백준 1019번: 책 페이지정수론(Number theory) 2018. 7. 1. 19:05
https://www.acmicpc.net/problem/1019 1. 문제지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 정수론참고 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #include #include #include ..
-
백준 3015번: 오아시스 재결합스택(Stack) 2018. 7. 1. 18:46
https://www.acmicpc.net/problem/3015 1. 문제오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 스택참조 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-3015?qid=9e270307-739a-4735-8689-e1b93d1d10fb&v=&b=&from_searc..
-
백준 1920번: 수 찾기이분 탐색(Binary Search) 2018. 6. 30. 16:30
https://www.acmicpc.net/problem/1920 1. 문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 2. 알고리즘키워드 - 정렬, 이분탐색 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #include #include #include #include #include #include #include #include #include #include using na..
-
Codeforces Round #479 (Div. 3)코드포스(CodeForce) 2018. 6. 30. 11:43
1. 문제 (http://codeforces.com/contest/977/problem/A)A. Wrong Subtractiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLittle girl Tanya is learning how to decrease a number by one, but she does it wrong with a number consisting of two or more digits. Tanya subtracts one from a number by the following algorithm:if the last digit of the number ..
-
백준 4673번: 셀프 넘버정수론(Number theory) 2018. 6. 29. 17:00
https://www.acmicpc.net/problem/4673 1. 문제셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114..
-
백준 1965번: 상자넣기최장 증가 수열(Long Increasing Subsequence) 2018. 6. 29. 16:43
https://www.acmicpc.net/problem/1965 1. 문제정육면체 모양의 상자들이 일렬로 늘어서 있다. 상자들마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자들을 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자들을 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다. 상자들의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 ..