알고리즘/BOJ 썸네일형 리스트형 2056번 2056번 - 작업 위상정렬을 이용한 문제풀이다. 위상정렬은 2가지 풀이방식이 있는데, 그 중에서 BFS로 풀었다. indegree 값을 구하고, dist[i] 배열에는 i번 작업이 끝나는 시간으로 정의했다. (처음에 dist[i]=i번 작업이 시작하는 시간으로 정의했는데, 그럴 경우 맨 마지막에 호출되는, out-degree 가 0인 작업들은 다시 한번 계산해줘야 하는 번거로움이 있었다.) 또 처음에 while 문 안에서 queue 가 empty 가 될 때, dist 값을 구했는데, 그러면 안됐다. 마찬가지로 out-degree 가 0인 작업들 중에서 시간이 최대로 많이 걸리는 애가 선택이 되는게 아니기 때문이다. 1234567891011121314151617181920212223242526272829.. 더보기 10826번 10826번 - 피보나치 수 4 처음에 행렬을 이용해서 풀려고 했는데, 범위가 10000까지 밖에 되지 않았다. 그래서 그냥 DP를 이용해서 피보나치 수를 구했다. 근데 N=10000 일때 피보나치 수가 long long 을 벗어나고, unsigned long long 까지 벗어난다고 하였다.. 그래서 어쩔 수 없이 string 을 써서 문제를 풀었다. operator + 를 오버라이딩하여 string 끼리의 덧셈 연산을 재정의 했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808.. 더보기 10757번 10757번 - 큰 수 A + B 자료형으로 저장할 수 없는 큰 수를 더하는 계산이 필요했다. 처음에는 어떤식으로 할까 하다가 이를 문자열로 대체하면 되겠다는 생각으로 문제를 풀었다. 그리고 문자열을 뒤집어서 끝을 맞춘다음, 실제로 덧셈하는 것처럼 계산하였다. while 문의 조건 중 && 을 || 로 풀어서 처음에 어리둥절 했었다. 나는 string 으로도 풀어보고 vector 로도 풀어봤다. 배열로 많이들 푸시던데 나는 쓰레기값을 제어하기 귀찮아서 저렇게 풀었다 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172.. 더보기 10757번 10757번 - 큰 수 A + B 자료형으로 저장할 수 없는 큰 수를 더하는 계산이 필요했다. 처음에는 어떤식으로 할까 하다가 이를 문자열로 대체하면 되겠다는 생각으로 문제를 풀었다. 그리고 문자열을 뒤집어서 끝을 맞춘다음, 실제로 덧셈하는 것처럼 계산하였다. while 문의 조건 중 && 을 || 로 풀어서 처음에 어리둥절 했었다. 나는 string 으로도 풀어보고 vector 로도 풀어봤다. 배열로 많이들 푸시던데 나는 쓰레기값을 제어하기 귀찮아서 저렇게 풀었다 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172.. 더보기 11778번 11778번 - 피보나치 수와 최대공약수 이 문제는 처음에 피보나치 수를 각각 구하고, 유클리드 호제법을 이용하려 했으나 실패. 일단 범위가 너무 크기 때문에, 피보나치 수를 구할 수 없었다. 그래서 차선책으로 피보나치 수의 나머지를 구하고, 그 값을 유클리드 호제법을 이용했으나... (a%m, b%m)의 최대공약수와 (a, b의 최대공약수)%m은 다르므로.. 이는 성립할리가 없었다. 그래서 피보나치의 성질 중 하나인 GCD(F[N],F[M])=F[GCD(N,M)] 을 사용할 수밖에 없었다. 이를 이용하면 굉장히 편하게 풀린다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354.. 더보기 11443번 11443번 - 짝수번째 피보나치 수의 합 홀수번째 피보나치 수의 합과 비슷한 방식으로 증명해가면서 풀었다. 기존의 피보나치 방정식 F[N+2]=F[N]+F[N+1] 에서 짝수의 합을 만들어 내기 위해 N 대신 2N-1 을 대입해서 세개중 하나만 짝수로 만들어서 증명했다. 즉 F[2N] = F[2N+1] - F[2N-1] 을 이용해서 문제를 풀었다. 1~2N 까지 짝수번째 피보나치 수의 합은 F[2N+1] - 1이 된다. 입력으로 주어지는 N이 짝수인지, 홀수인지를 점검해서 문제를 풀어야 하는 건 주의점 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061.. 더보기 11442번 11442번 - 홀수번째 피보나치 수의 합 홀수번째 피보나치 수의 합도 쉽게 구할 수 있다. 기존의 피보나치 식 F[N+2]=F[N]+F[N+1] 에서 하나만 홀수로 만들어서 정렬하여 증명을 하기 위해서 나는 N 대신 2N을 대입했다 (다른 분들 코드를 보니 2N-2 를 대입한 코드들이 많았다. ) 그래서 F[2N+1] = F[2N+2]-F[2N] 을 이용해서 문제를 풀었다. 단, 이 문제에서 주의할 점은 입력으로 들어오는 N의 값이 홀수인지 짝수인지 파악해야 한다! 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#in.. 더보기 11440번 11440번 - 피보나치 수의 제곱의 합 참고용 게시판에 피보나치 수열의 특징에 대한 글이 있다. 그 글을 읽고나서 피보나치와 관련된 문제를 풀면 훨씬 수월하다. 피보나치 수열의 제곱의 합(1~N까지) 은 F[N]*F[N+1] 이라는 것을 구할 수 있다. 이를 행렬의 곱과 활용하여 이용하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include#include using namespace std;const long long mod = 1000000007;typedef vector matrix;matrix operator *(matrix &A, mat.. 더보기 이전 1 ··· 21 22 23 24 25 26 27 ··· 40 다음 목록 더보기