안 쓰던 블로그

(A,B)로부터 a+=b, b+=a 를 통해 만들어진 수를 (iA+uB, jA+vB) 라고 설정하면 이들의 합 (i+j)A + (u+v)B는 A, B 정수 계수를 갖는 선형결합이므로 배주 항등식에 의해 (i+j)A + (u+v)B = gcd(A,B)가 된다 배주 항등식 0이 아닌 정수 a, b에 대해 d를 a와 b의 최대 공약수라고 하면, 수식을 만족하는 해 (x,y)는 반드시 존재한다 $ax+by=d$ 특히 a와 b가 서로소이고 d=1이라면, 베주의 항등식에 의해 정수해가 반드시 존재한다 확장 유클리드 수식과 완전히 동일하지만, 여기서는 (x,y) 해가 반드시 존재함에 포커싱을 둔다 여기까진 질문탭에 있는 답변이었다. 다르게 생각해 볼까 처음 시작하는 a, b값을 각각 a0 b0이라고 하면, 두 명령을..

그래프에서 사이클 구간 찾는 문제 문제 이해 자체는 쉬운데 구현이 어려웠다 사이클을 찾아야 하는데, 다른 사람들 글을 보니까 finish배열을 써서 finish가 체크가 아닌데 visit는 체크이면 사이클이고 그런다던데 뭔소린지 직관적으로 이해되지 않아서 이해하는 데 좀 걸렸다 1. 사이클 확인 그래서 내 나름대로 이해해 보았는데, finish배열말고 아래처럼 생각하면 좋더라 void dfs(int now) { int next = v[now]; //가리키는 거 if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다 //구현 } visit[now] = 1; dfs(next); //다음 경로 } dfs를 돌면서 보통 이렇게 방문을 체크하고, 방문하지 않았으면 dfs를 또..

이분 그래프란? 정점에 색깔을 부여한다고 할 때, 절반씩 그룹으로 나눌 수 있는 그래프. 인접한 정점끼리 색깔이 같으면 안 된다 골4 문제이지만 이제까지 풀어왔던 dfs, bfs처럼 탐색으로 풀 수 있다 1. 탐색하면서 그래프에 색깔(1, 2)을 부여한다. visit를 체크할 때 방문/미방문이 아닌, 미방문/색1/색2 이렇게 세 가지로 주면 된다 위에 그림에서는 문제의 예시로 있는 두 케이스를 그림으로 그린 것이다 O가 색1, X가 색2라고 했을 때, 탐색이 끝나면 각 정점에 대해 O또는 X가 전부 부여된다(미방문이 없을 때까지 탐색) 2. 각 정점에 연결된 정점들을 확인하며 색1의 연속, 색2의 연속인 경우가 있는지 체크한다 각 정점에 연결된 정점들을 이중for문으로 확인하며 OO또는 XX가 나오면 이..

www.acmicpc.net/problem/2133 dp[n] = 3xn 직사각형 채우는 방법의 수 1. n이 홀수면 채울 수 없다 2. n=2면 3가지 방법이 있다 3. n=4면 3x2만큼은 dp[2]에서 했던 값을 사용, 나머지 3x2에 대한 방법이 또 3가지 있다 dp[2]에서 했던 부분을 왼쪽을 잡든 오른쪽을 잡든 같으니까 같은 수로 친다 dp[2]x3=9만큼의 경우의 수가 나온다 그리고 특수 케이스가 있다 이렇게 엇갈리는 방법 두 가지가 있다 dp[4]=dp[2]*3+dp[0]*2 가 된다. dp[4]=11 3. n=6이면 dp[2]+dp[4] 이렇게 볼 수 있지만 둘은 중복되는 모양이 너무 많다 그래서 일단 dp[2]*dp[4]를 해 놓고, 중복 없이 나머지를 넣어야 한다 dp[2]*dp[4]..

www.acmicpc.net/problem/2294 dp배열은 합이 j일 때의 최소 동전 개수를 나타낸다 현재 금액만 사용했을 때 최소 몇 개의 동전이 필요한가 하나씩 보며 전체 dp배열을 업데이트하는 식이다 1원 쓸 때는 1~15원까지 각 개수만큼 사용해서 1,2,3..15까지가 배열에 들어간다 다음 5원 쓸 때는 1~4원까지는 1원을 쓴 그대로 두고, 5원은 5원 1개로 만들 수 있으니까 1이 되고, 6,7,8,9까지는 5+x개의 1원을 쓰니까 각각 2,3,4,5개를 사용해서 만들 수 있다 이 때 이전에 1원 기준으로 계산했던 값에서+5원을 하면 (5원 1개+1원 x개)로 만든 값이 나오니까 j-a[i](1원 x로 만든 값)+1(5원 1개 더한 값)이 식이다. j-a[i]+1 이 값을 현재까지의 최소..

두 수의 합의 모듈러는, 각 수의 모듈러를 더한 모듈러와 같다 즉, 계산 중에 너무 큰 값이 만들어질 것 같고 결과값이 모듈러 연산한 나머지를 출력하는 문제라면, 중간에 연산하면서 바로 모듈러 연산을 해도 최종적으로 같은 결과가 나온다 (합 구하는 문제 같은 경우) (5+4)%2=9%2=1 (5%2)+(4%2)=1+0=1 이런 느낌이다

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include #include #include #include using namespace std; int dp[101][11]; //i자리 숫자면서 j로 시작하는 계단 수 -> 틀림 //이거 남들은 j로 끝나면~으로 하던데 시작해도 딱 떨어지는 것 같음(아마..일단 내가 계산한 만큼은) -> 이거 틀림 //다만 10으로 시작하는 건 1개씩 늘어나고 12로 시작하는 건 2개씩 늘어나니까 [1][0]은 10~, [1][1]은 12~로 나눠줌 ->틀림 //---------- //i자리 숫자면서 j로 끝나는 계단 수로 해야 계산..