안 쓰던 블로그

이분 그래프란? 정점에 색깔을 부여한다고 할 때, 절반씩 그룹으로 나눌 수 있는 그래프. 인접한 정점끼리 색깔이 같으면 안 된다 골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로 끝나는 계단 수로 해야 계산..

입력 4 6 101111 101010 101011 111011 입력 코드 cin >> n >> m; for (int i = 0; i > a; for (int j = 0; j < m; j++) { map[i][j] = a[j] - '0'; } }

6068 시간 관리하기 1263 시간 관리 '늦잠을 언제까지 잘 수 있냐'가 문제이기 때문에 끝나는 시간을 기준으로 내림차순 정렬하고 앞에서부터(가장 끝나는 시간이 늦은 일부터) 일을 최소 언제부터 시작해야 하는지를 계산한다 예제로 보면, 5 20은 최소 15에는 시작해야 한다 1 16은 최소 15에는 시작해야 하지만, 15에는 5 20이 해야 하므로 앞으로 밀려서 14에는 시작해야 한다 8 14는 최소 6에는 시작하면 된다 3 5는 최소 2에 시작하면 된다 github.com/proqk/Algorithm/blob/master/greedy/6068%20%EC%8B%9C%EA%B0%84%20%EA%B4%80%EB%A6%AC%ED%95%98%EA%B8%B0(1263%20%EC%8B%9C%EA%B0%84%20..