출처 : Google Codejam Qualification Round 2015 C. Dikstra (https://code.google.com/codejam/contest/dashboard?c=6224486#s=p2) ProblemThe Dutch computer scientist Edsger Dijkstra made many important contributions to the field, including the shortest path finding algorithm that bears his name. This problem is not about that algorithm. You were marked down one point on an algorithms exam for misspelli..

https://www.acmicpc.net/problem/1153 다양한 풀이방법이 있겠지만, Goldbach's Conjecture라 불리는 가설?을 이용하여 풀었다. 항상 소수관련문제는 정수론과 뗄레야 뗄 수 없는것 같기도하고.. Goldbach's Conjecture는 아직 증명이 되지않은 정수론 미해결문제중 하나로 "2보다 큰 모든 짝수는 두개의 소수의 합으로 나타낼 수 있다"는 가설이다. 물론 아직 반례를 찾지못해 미해결문제로 남아있다. 즉, 앵간히 큰 짝수(우리가 문제에서 접할 수 있는 수)까지는 다 성립한다는 뜻. #include int num[1000001] = { 0 };int N;void prime() { for (int i = 2; i*i

Maximum Sum Subarray라 불리는 문제에서 슬라이딩 윈도우기법으로 O(N)에 해결하는 알고리즘 Maximum Sum Subarray란 수열의 연속 부분합중 가장 큰 값을 찾는 문제 Kadane Algorithm을 간략히 설명하자면 1. 앞에서부터 수를 하나씩 더해가면서 sum이라는 변수에 매번 값을 저장한다. 2. 만약 sum이 음수가 되는 지점이 발생한다면, sum은 0으로 초기화한다. 3. 이 sum들을 매번 maximum값으로 갱신한다. 구간의 index가 필요하다면 sum을 갱신하는 부분에 추가하여 나타낼 수 있다. 위의 내용은 1-dim array에 관한 내용이고 이를 응용하면 2-dim array에서의 문제는 O(N^3)에 해결할 수 있다. (2차원 배열에서 최대 부분합) 참고영상..

https://www.acmicpc.net/problem/1750 naive하게 생각하면 포함-배제의 원리를 생각하기 쉬우나 조금 생각해보면 TLE가 떨어질거라는 확신이 드는 문제이다. DP를 이용해 N개의 원소중 1~i번째 숫자들을 후보로 하여 최대공약수가 j인 갯수를 d[i][j]라고 놓으면 생각보다 쉽게 점화식을 세울 수 있다. #include #define MAX 10000003#define LL long longint num[101];__inline int min(int a, int b) { return a > 1]; while ..

잘 정리된 블로그가 있어서 링크로 대체한다. 다익스트라 알고리즘(Dijkstra Algorithm) : 한점 - 다수의점 (음수가중치X)벨만-포드 알고리즘(Bellman-Ford Algorithm) 한점 - 다수의점 (음수사이클X)플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든점 - 모든점

#1. 막대기 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB801115 (14%)90문제n가지 종류의 막대기가 있다. 막대기의 길이는 모두 다르다. 이 막대기들을 적당히 사용해서, 총 길이가 K가 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 막대기는 여러번 사용할 수 있다.)입력첫째 줄에 n,k 가 주어진다. (1

Quick Sort : O(NlogN), 최악의 경우 O(N^2)을 보장하는 소팅. Heap Sort : O(NlogN)을 보장하는 소팅 Radix Sort : O(dN)을 보장하는 소팅(자리수) 으로 이론적으로만 알고있어서 오늘 구현해본결과, 속도차이가 그닥 나지않음을 발견했다 알고리즘공부하면서 Big-O표기법에 대해 항상 께림직했던게, 결국 Big-O는 수학에서 말하는 N이 충분히 큰 경우(sufficiently large) 계수는 무시할 수 있기에, 계수를 제외한 값을 표현해준다는 것이다. Quick Sort는 별 할말이없다. 워낙 유명한 소팅이라.. 굳이 한마디 하자면 pivot을 그지같이 잡거나 해서 최악의 경우 N^2이라곤 하지만, 생각보다?(이름만큼?) 속도가 빠르다 Heap Sort Hea..

#1. 이친수 시간 제한메모리 제한1.0 초512 MB문제0과 1로 이루어진 이진수중 다음 성질을 만족하는 수를 이친수라고 한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100 등이 이친수가 된다.하지만 010이나 110은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1≤N≤90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. 출력첫째 줄에 N자리 이친수의 개수를 출력한다. 입력 예제3출력 예제2 힌트다이나믹 프로그래밍(DP) 소스#include #define LL long long int N;LL d[2][91];LL dp(int num..

1. 다익스트라로는 B->C->D경로를 고려할 수 없다. 2. +@해서 모든값을 양수로 바꾼다면 거쳐가는 경로수*@가 되므로 제대로 된 계산이 될 수 없음.