C | C++ 알고리즘 & 자료구조

Mertens Trick & Boj 17372, 16123 정리 공유

[boj 8878] Hey, Better Bettor

Boj 8878, Hey, Better Bettor 이 문제를 해석해보자면 먼저, 나는 도박을 하는 중이고, 0$를 가지고 있다. 이때, 내가 도박에서 이기면 1$를 얻고, 지면 1$를 잃는다. 이길 확률은 p (0 정지 => 단조 감소 그래프를 그리므로 Pred(A,B)에 비해 Pred(A+1,B)가 증가하면 계속 탐색, Pred(A+1,B)가 감소하면 탐색을 멈춘다. 이때, 엄청나게 정밀한 부동소수점 연산이 요구되기에 최대점 갱신은 그냥 기존의 부등식 연산을 사용하고, 단조 증가, 단조 감소 판별은 Epsilon을 정의하여 사용한다. ("최대점보다 Epsilon만큼 작으면 단조감소이다."와 같은 식으로 사용함) 이때, Epsilon은 크면 클수록 탐색을 더 진행한다는 뜻이 되므로 시간초과가 나게 하지..

boj 13728 행렬식과 GCD C++ 풀이

백준 플레 4에 해당하는 행렬식과 GCD 문제이다. 이 문제의 설명을 간단히 해보자면, M이라는 행렬이 위와 같이 정의된다고 할때, D(i) = det(M_i*i) 로 정의된다. 즉, 크기가 i*i인 M의 행렬식인즉, D(i)가 된다. 그 이후, S = sum(gcd(D(i), D(N)) ( 1

boj 13308 주유소 C++ 풀이

이 문제는 DP+dijkstra 알고리즘으로 풀이가 가능하다.사실 말만 이렇지 정확히 이들의 교집합은 아니라서 "그래프탐색" 문제라고 하는게 정확하다.  이 문제를 처음 봤을 때 당황하는 이유는, 플레 이전에는 항상 변수가 1개인 다익스트라 혹은 다변수 DP 정도를 다뤄봤을 것이기 때문이다. 이 문제는 다익스트라의 관점에서라기 보다 DP의 관점에서 깊게 파고들면 충분히 해결 가능한 문제이다.   우리가 최종적으로 구하고자 하는건 "N번째 노드까지 도달하는 데 드는 최소비용" 이다. 고로, 평소 같았으면은 최소비용을 값으로 가지는 DP 테이블을 생각했을 것이다. 하지만 여기서 막막한게, DP[i] = i번째 노드까지의 최소비용 이라고 한다면 언제 어디서 주유를 해야하는지가 너무 큰 변수가 되어 아마 이대로..

BOJ 2449 전구 풀이

이 문제는 dp의 정의만 잘 해주면 충분히 풀 수 있다. 먼저, 색의 개수인 k는 고려치 않아도 된다. 왜냐하면 어차피 입력값은 k범위 내에서 주어지고, 구하는 과정에서 서로 색이 다르다면 같게 만들거나 할 뿐이지, 색을 1만큼 추가한다와 같은 연산을 하지는 않을 것이기 때문이다. 고로, dp[left][right] := left에서부터 right까지 색을 같게 만드는 데까지 바꾸는 횟수 라고 한다. 그러면, dp[l][r] = dp[l][k] + dp[k+1][r] + a (ln>>k; for(int i=0;i>arr[i]; cout

가우스 소거법 with C++

가우스 소거법이란, 연립일차방정식(System of linear equations)의 해를 구하는 알고리즘이다. 기본적인 아이디어는, 계수로 이루어진 행렬 M이 있다고 할 때, M을 행사다리꼴행렬로 변환하는 것이다. 즉, 가우스 소거법은 어떤 임의의 행렬을 행사다리꼴로 변환하는 방법이다. 자세한 것은 아래를 참고하라. https://ko.m.wikipedia.org/wiki/%EA%B0%80%EC%9A%B0%EC%8A%A4_%EC%86%8C%EA%B1%B0%EB%B2%95 가우스 소거법 - 위키백과, 우리 모두의 백과사전 선형대수학에서 가우스 소거법(Gauß消去法, 영어: Gaussian elimination)이란, 연립일차방정식을 풀이하는 알고리즘이다. 풀이 과정에서, 일부 미지수가 차츰 소거되어 결국..

814-2 도전 - 1

namespace Simulated_Annealing{ // int GEN_CYCLE = 1000; // for genetic algorithm int max_score; double t = 1; double d = 0.9995; double k = 2.5; double lim = 0.05; vector2 max_board(8,vector1(14,0)); vector2 now_board(8,vector1(14,0)); void Start(){ int nwscore=scoring(now_board),prevscore,cnt=0; vector2 prev_board; while(t>lim){ prevscore=nwscore; //Todo : change state 1 to 2 /*****************..

백준 13887 ( 루비 도전기 < Day - 2 > )

오늘은 기본적인 splay tree 구현을 했다. #include using namespace std; /// 처리해야 할 것 // 1. (4번 쿼리) key==z인 노드 오른 쪽에 y추가하고, 그 다음 노드들의 key ++ ( lazy_propagation 처리 ) // 2. interval ( l ~ r ) 처리 이후 sumC3 출력 // 3. sumC ( 1 ~ 3 ) 모두 modular 처리 // 4. 서로 다른 수의 개수 쿼리 처리 // 5. delete 이후 삭제한 노드 오른쪽 서브트리의 노드들의 key -- ( lazy propagation 처리 ) // 6. 메인함수 및 input 작성 ( tree initializing은 insert n번 ( O( n ln n ) 처리 ) ) // 이것만..