거의 알고리즘 일기장

https://www.algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subseque www.algospot.com O(n^2) 풀이 반복문 풀이 #include #include using namespace std; ..

https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테 algospot.com 접근 시간 : 5초, 테스트케이스 : 최대 50개, n : 최대 100 딱봐도 이 ..

https://codeforces.com/problemset/problem/455/A Problem - 455A - Codeforces codeforces.com 풀이방법 ak를 선택시 ak-1, ak+1은 선택 못한다는것을 유의해서 점화식을 짜야한다. dp[i] = max( dp[i-1], dp[i-2] + cnt[i]+i ) 전체코드 #include #include using namespace std; int n; long long cnt[100002]; long long dp[100002]; void Input() { cin >> n; int value; for (int i = 0; i > value; cnt[value]++; } } int main() { Input(..

https://codeforces.com/problemset/problem/230/B Problem - 230B - Codeforces codeforces.com 조건 2초, n (1 ≤ n ≤ 10^5), xi (1 ≤ xi ≤ 10^12) 접근 이 문제는 약수가 3개인 수를 구한다. 약수가 3개인 수가 뭘까? 잘 생각해보면 소수를 ^2하면 약수가 3개인 수를 구할수 있음을 깨달을 수 있다. ex) 소수 2, 3, 5, 7의 제곱수들을 보면 4, 9, 25, 49로 모두 약수가 3개인 수들이다. 그렇다면 소수만 빨리 풀수 있다면 이 문제도 시간내에 충분히 풀수있을것이다. 풀이방법 일단 범위는 루트를 씌워 구할것이기 때문에 10^12의 루트를 씌운 10^6 + 1로 설정했다. 그외에는 그냥 에라스토테네스..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 www.acmicpc.net 풀이방법 현재 연결되어 있는 가전제품중에 이후에 제일 늦게 사용되거나 더이상 사용되지 않는 가전제품을 빼고 연결하면 된다. 처음에 ..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 접근 주어진 시간은 1초, N의 최댓값은 20만, S와 T는 최대10^9 S, T가 INT의 범위를 넘으므로 다른 자료형을 써야한다. 나는 long long씀. 그리고 완전탐색으로는 풀수가 없으므로 다른 방법을 찾아야 한다. 나는 priority_queue를 이용했다. 풀이방법 첫번째 생각 처음에는 방을 배열로 만들고 끝나는 시각을 값으로 넣어두면 아슬아슬하게 시간내에 풀지 않을까? 라는 생각을 했었다. 그런데 곰곰히 생각해보니 그저 배열로 만..

4796번 https://www.acmicpc.net/problem/4796 4796번: 캠핑 문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 www.acmicpc.net #include #include #include using namespace std; int L, P, V; int main() { ..

https://codeforces.com/problemset/problem/189/A Problem - 189A - Codeforces codeforces.com 풀이방법 시간은 1초, n,a,b,c는 최대 4000이다. 조건은 1. piece는 무조건 a or b or c 2. 최대로 자를수 있는 값을 구하라 완전탐색으로 할시 최악의 경우 ( a,b,c가 1, n이 4000일때 ) 4000! * 3일수 있다. 그러므로 완전탐색은 탈락이고 시간을 줄일수 있는 dp를 써보자. dp[value] : value일때 최대로 자를수 있는 개수 그리고 a, b, c를 하나씩 순서대로 밑의 조건대로 넣어보자. 1. value % piece (a or b or c) == 0 일때 dp[value] = max(dp[va..

https://codeforces.com/problemset/problem/492/B Problem - 492B - Codeforces codeforces.com 풀이방법 주어진 조건은 시간은 1초, n은 최대 1000, l은 최대 10^9 이다. n이 1000 밖에 안되므로 그냥 정렬해서 풀면 끝이다. slt sort가 어느정도의 시간이 걸리는지 정확히는 모르겠지만( 내 기억엔 O(nlogn)이었던걸로 기억함 ) 퀵소트의 최악의 경우인 O(n^2)이라도 시간은 충분하다. ㅎㅎ 전체코드 #include #include #include #include using namespace std; int N; long long L; vector a; void Input() { cin >> N >> L; long l..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이방법 완전탐색으로 푼다면 16!로 말도안되는 시간이 걸린다. 그러므로 dp를 추가해서 적절히 중복되는 연산을 저장하고 그 값을 이용함으로써 연산을 줄이는 방법이 필요하다. 예를 들어 1 2 3 4 5 6 7 1 2 3 4 5 7 6 1 2 3 4 6 5 7 1 2 3 4 6 7 ..