알고리즘/BOJ 썸네일형 리스트형 11047번 11047번 - 동전 0 그리디 알고리즘 공부중.. 예제 문제여서 풀었다. 그리디 라는 것을 알고 푸니까.. 근데 그 정당성 증명을 어떻게 해야할 지 잘 모르겠다. (추가) 내가 한 정당성 증명 - 맞게 한 것인지는 모르겠다. 만들어야하는 K보다 작은, 가장 큰 동전을 CoinMax 라고 하자. 정답 S의 최적해 중 CoinMax 를 선택하지 않는 답이 존재한다고 하자. 그렇다면 문제에서 나와있듯이, 동전들은 모두 배수 관계에 있기 때문에, S의 답에서 적절한 합을 통하여 CoinMax를 만들 수 있습니다. 따라서 새로 만든 목록도 최적해 중 하나가 됩니다. 따라서 항상 CoinMax를 포함하는 최적해가 존재합니다. ##질문게시판## 이렇게 쉽게... 내 말을 요약.. 1234567891011121314.. 더보기 9466번 9466번 - Term Project 이 문제를 풀기까지는 오래걸렸다.. 혼자 그래프 문제를 풀다가 막혀서 못 풀었다가 종만북에서 나오는 간선을 구분짓고 사이클을 찾는 방법을 이해를 못해서 못 풀다가.. 문득 종만북을 다시 읽다가 간선 구분하는 것을 이해하고 이 문제가 생각나서 바로 풀어보았다. 예전에는 사이클을 그냥 막 이렇게 해보고 저렇게 해보고 하면서 매번 다르게 문제를 풀었다면, 종만북을 보고는 사이클은 이런 방식으로 풀어야 겠다! 라고 생각을 하고 풀게 된 것 같다. 이 문제는 유향식 그래프에서 사이클을 구하는 방식과 똑같다. 내가 참고용으로 필기해서 올려놓은 간선 구분 방법에 따라서 문제를 풀었다. 이 문제는 순방향 간선, 교차 간선일 때 구해야 할 값도 없고 ( 정점에서 간선이 하나씩 밖에 .. 더보기 2004번 2004번 - 조합 0의 개수 우선 처음에 푼 방식으로는 시간초과가 발생했다. 이전에 팩토리얼의 0의 갯수 구하기 같은 문제는 범위가 작다보니 시간초과가 발생하지 않았지만, N의 범위가 20억이다보니 시간 초과가 발생하게 되었다. 그래서 다른 사람들의 코드를 보았더니, 더 쉽게 계산할 수 있는 방법이 있었다. 예를 들어 100! 에서 5가 몇개나 인수로 들어가있는지 계산하기 위해서는 100 / 5 + 100 / 25 + ... 이런식으로 계산을 해야한다. 25에는 5가 2개 들어있기 때문에, 125에는 3개 들어있기 때문에, 이런식으로 계산을 하면 쉽게 갯수를 구할 수 있다. 이와 같은 방식으로 코드를 구현하였다. ==> N, M은 20억 이하의 숫자이기 때문에 N,M 은 int 형 자료를 썼다. 그런데.. 더보기 1676번 1676번 - 팩토리얼 0의 개수 언뜻 보면 N의 범위가 400!... 이 엄청난 수를 어디에 담아야할지 조차 보자마자 머리가 아득해졌다. 근데 항상 이럴수록 더 힌트가 되는 것 같다. 오히려 너무 크기 때문에 다른 방법을 생각해보게 되었다. 호랑이 굴에 들어가도 정신만 바짝! 소인수 분해를 통해서 2와 5의 갯수를 구하고, 2와 5의 갯수의 최솟값을 출력하면 된다. 최종적으로 10의 갯수만 구하면 되기 때문이다. 12345678910111213141516171819202122232425262728293031323334#include#includeusing namespace std; int main(){ int N; int cnt2 = 0; int cnt5 = 0; cin >> N; for (int i .. 더보기 11653번 11653번 - 소인수 분해 처음에 코드가 굉장히 헷갈렸다.. 뭔가 어떻게 짜야할지 막막했다. 근데 이전에 소수인지 확인 할때 2부터 나눠서 나누어 떨어지는 지 확인하는 것처럼 소인수 분해라는 것도 결국은 약수로 계속 나눠서 소수를 만드는 것이라 생각하면 됐다. 그래서 소수를 만들기 위해서, 1과 자기 자신 말고는 나누어 떨어지는 수가 없도록 하기 위해 그 외의 나눠질 수 있는 숫자로 계속 나눈다. 그게 바로 소인수 분해가 되는 것이다. 그리고 결국은 1과 자기 자신이 남게 되는데, 1은 소인수 분해에 들어가지 않으므로 자기 자신의 숫자를 if(N>1) 에서 출력해주면 된다. 123456789101112131415161718192021222324252627#include using namespace st.. 더보기 6588번 6588번 - 골드바흐의 추측 에라토스테네스의 체를 응용한 문제라고 볼 수 있다. 이 문제를 풀면서 문제점 1. 에라토스테네스의 체를 한번만 써도 되는데 while 문 안에 넣어서, 반복적으로 계산하게 함 -> 시간 초과를 야기함. 2. while 문 안에 반복적으로 에라토스테네스 체를 쓰면서 vector 및 변수를 초기화 안함 -> 메모리 초과를 야기함. 3. 차이를 최대로 하는 두 소수를 구하는 방법 => 이미 N이 주어져 있기 때문에 v[i] 의 최소값만 구하고, N-v[i] 의 값이 소수인지만 확인이 된다면 문제에서 요구하는 b-a 가 최대이고 , 둘다 홀수 소수인 값이 결정이 되는데, 무식하게 이중 for문을 통해서 모든 b-a를 구해서 최대값일 때마다 변경하는 수고를 하다보니, 엄청난 시간 초.. 더보기 1929번 1929번 - 소수 구하기 에라토스테네스의 체를 이용해서 소수를 구했다. 에라토스테네스의 체는 원하는 범위에서의 모든 소수를 구하고 싶을 때, 배수를 체크해가면서 남은 소수를 찾아가는 방법이다. 기존에 소수를 구하던 방법 보다 소수를 더 빠르게 구할 수 있다는 장점이 있다. 백준 강의를 들을 때 안쪽 for 문에서 j = i * i 로 구현하면 더 빠르겠지만, n제한이 100만 일경우에는 j = i * 2 로 구현한다고 하였다. i * i 가 좀 더 빠르겠지만, 귀찮게 조건을 살펴야 하느니 i * 2 로 사용해야겠다. 12345678910111213141516171819202122232425262728293031#include#includeusing namespace std; bool .. 더보기 1978번 1978번 - 소수 찾기 소수를 찾는 방법 (에라토스테네스의 체 배우기 전) 소수 : 약수가 1과 자신 밖에 없는 수 *첫번째 방법 2 ~ 자기자신-1 까지 다 나눠서 나누어 떨어지면 소수가 아니다. O(N) *두번째 방법 2 ~ 자기자신/2 까지 다 나눠서 나누어 떨어지면 소수가 아니다. O(N/2) *세번째 방법 2~ 루트 자기자신 까지 다 나눠서 나누어 떨어지면 소수가 아니다. O(루트N) 12345678910111213141516171819202122232425262728293031323334353637#include using namespace std;int checkPrimeNum(int num){ if (num N; for (int i = 0; i > tmp; ans += checkPrime.. 더보기 이전 1 ··· 28 29 30 31 32 33 34 ··· 40 다음
