백준[16991] 외판원 순회 3
2021. 8. 10. 15:33
Algorithm/BOJ
문제링크 http://icpc.me/16991 풀이 비트마스크를 이용한 dp문제이며 외판원 순회와 다를 게 없다. 코드 #include #include #include using namespace std; using pii = pair; pii arr[17]; double dp[17][1
vim 세팅
2021. 8. 10. 12:18
환경 세팅
1. Vundle 설치 https://github.com/VundleVim/Vundle.vim 2. 아래 설정 vi ~/.vimrc에 복붙 3. vim들어가서 :PluginInstall set shell=/bin/bash set rtp+=~/.vim/bundle/Vundle.vim set backspace=indent,eol,start " more powerful backspacing call vundle#begin() Plugin 'VundleVim/Vundle.vim' Plugin 'dracula/vim', { 'name': 'dracula' } Plugin 'nathanaelkane/vim-indent-guides' Plugin 'scrooloose/nerdtree' Plugin 'Raimondi/..
2021 SCPC Round 2 후기
2021. 8. 7. 21:03
후기
후기 1번은 보자마자 풀진 못했지만 30분 내에 해결했다. 2번은 처음 볼 때 문제를 약간 잘못 봐서 잘못된 풀이를 생각해냈고 약간 뿌듯했다. 하지만 코드를 짜면서 뭔가 잘못됨을 느꼈고 결국 못 풀었다. 3번은 아예 아무것도 생각나지 않았고 전탐색으로 부분점수라도 긁으려 했지만 그것도 시간 초과가 났다. 1. 원 안의 점 문제 설명 원의 반지름이 주어지고 원의 내부에 있는 격자점을 구하는 문제다. 풀이 위의 그림과 같이 원 내부 격자점의 개수 = 초록점 + 4 * (검은 점 한 세트)이다. 이때 초록점은 (r - 1) * 4 + 1로 구할 수 있다. 그렇다면 검은 점의 개수만 빠르게 구하면 되는데 이때는 이분 탐색 이용했다. 원 내부의 점 좌표를 (x, y) 라 할 때 x^2 + y ^2 < r^2인 성..
백준[3648] 아이돌
2021. 8. 6. 10:16
Algorithm/BOJ
문제 링크 http://icpc.me/3648 풀이 SCC를 응용한 2-SAT으로 문제를 해결할 수 있다. 2-SAT을 모른다면 BOJ 2-SAT - 3를 참고해라. 코드 #include #include #include #include using namespace std; vector v, rev; stack s; bool visited[2003]; int scc[2003], idx, n, m; inline int T(int x) { return x
mac 폴더 숨기기, 숨긴 폴더 보기
2021. 8. 5. 16:37
환경 세팅
폴더 숨기기 chflags hidden (숨길 폴더 경로) 폴더 경로는 터미널에 폴더를 드랍하면 바로 입력된다. 숨긴 폴더 보기 파인더에서 command + shift + . 단축키로 볼 수 있다. 터미널에서 보려면 ls -a 를 하면 된다.
백준[5557] 1학년
2021. 8. 4. 23:32
Algorithm/BOJ
문제 링크 http://icpc.me/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 dp를 이용하여 해결할 수 있다. dp[i][j] : j번째 숫자까지 봤을 때 숫자 i를 만들 수 있는 최댓값으로 정의할 수 있다. 코드 #include using ll = long long; ll dp[22][102], arr[102], n; ll dpf(ll cur, ll idx) { if (cur 20) return 0; ll &ret = dp[cur][idx]; if (re..
백준[2225] 합분해
2021. 8. 4. 22:49
Algorithm/BOJ
문제 링크 http://icpc.me/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp [남은 수][뺄 수 있는 횟수]로 정의할 수 있다. 코드 #include using ll = long long; ll dp[202][202], N, K; const ll mod = 1e9; ll dpf(ll n, ll k) { ll &ret = dp[k][n]; if (ret) return ret; // 남은 수와 뺄 수 있는 횟수가 0일때 1리턴 if (!n && !k) return 1; // 뺄 수 있는 횟수는 끝났는데 수가 남아있을 때 0리턴 if (n && !k) return 0; for (..
백준[9084] 동전
2021. 8. 4. 22:12
Algorithm/BOJ
문제 링크 http://icpc.me/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 dp로 풀이할 수 있다. dp정의는 dp[남은 돈][몇 번째 동전까지 썼는지]로 정의할 수 있다. 코드 #include #include int dp[10004][22], arr[10004], n; int dpf(int money, int coin_idx) { int &ret = dp[money][coin_idx]; if (ret) return ret; if (!money) return 1; fo..
백준[1915] 가장 큰 정사각형
2021. 8. 4. 19:18
Algorithm/BOJ
문제 링크 http://icpc.me/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 dp로 해결할 수 있다. dp 점화식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]), (i, j는 배열 인덱스)로 정의할 수 있다. 위의 그림과 같은 예제가 있을 때 (2, 2) 인덱스에서 한 변의 길이가 2인 정사각형이 만들어지기 위해서는 왼쪽, 위, 왼쪽 위 가 모두 1이어야 한다. 이 말을 바꿔 말하면 min(dp[1][1], dp[1][2], dp[2][1]) + 1 == 1 이어야 한다. (5, 5)에서 한 ..
백준[2602] 돌다리 건너기
2021. 8. 3. 13:13
Algorithm/BOJ
문제 링크 http://icpc.me/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp는 dp[악마다리 or 천사다리][몇 번째 패턴 문자까지 발견][몇 번째 돌다리까지 갔나]로 정의할 수 있다. 코드 #include #include using namespace std; int dp[2][22][100]; string pat, a, b; int dpf(int up_down, int pat_num, int cur_num) { int &ret = dp[up_down][pa..
백준 [11280] 2-SAT - 3
2021. 8. 2. 22:38
Algorithm/BOJ
문제 링크 http://icpc.me/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 풀이 이 문제는 SCC를 구하기 위해 코사라주 알고리즘을 이용한다. (xi V xj)가 항상 참이기 위해서는 xi 가 거짓이라면 xj는 항상 참이어야 한다. 또한 반대로 xj 가 거짓이라면 xi는 항상 참이어야 한다. 그렇기 때문에 not(xi) -> xj와 not(xj) -> xi 간선을 만든다. 이것은 위의 설명을 그래프로 나타낸 것이다. 이때 한 ..
백준[4013] ATM
2021. 7. 30. 16:28
Algorithm/BOJ
문제 링크 https://www.acmicpc.net/problem/4013 풀이 SCC, 유니온 파인드, 위상 정렬, dp를 이용하여 풀이하였다. 다 푼 후에 다른 사람의 코드를 보고 깨달았지만, 유니온 파인드는 굳이 사용하지 않아도 된다. 출발지점부터 순회하며 dp를 돌리면 될 것 같지만 사이클이 존재하기 때문에 그럴 수 없다. 그렇기 때문에 사이클이 없는 방향 그래프로 바꿔줘야 한다. 사이클을 제거하기 위해 SCC를 사용한다. 아래 코드는 코사라주 알고리즘을 이용하였다. 구해진 SCC를 이용하여 사이클을 하나의 큰 노드로 합친다. 나는 이때 유니온 파인드를 사용하였다. 하지만 이미 SCC들을 모두 구했기 때문에 이미 합쳐져 있는 상태여서 유니온 파인드를 사용하지 않아도 된다. scc vector의 ..
백준[3977] 축구 전술
2021. 7. 29. 00:26
Algorithm/BOJ
문제 링크 https://www.acmicpc.net/problem/3977 풀이 이 문제는 코사라주 알고리즘을 이용하여 SCC를 구해서 풀 수 있다. 백준 4196 도미노 와 매우 비슷하다. 도미노 문제와 동일하게 dfs를 돌리며 방문할 노드가 없을 때 스택에 추가하면 stack의 top에는 가장 많은 곳을 갈 수 있는 노드가 위치하게 된다. 그렇기 때문에 stack의 top에 있는 노드를 시작으로 다시 dfs를 돌려 모든 노드를 방문할 수 있는지 판별하고, 만약 모두 방문할 수 있다면 top에 있는 노드의 SCC를 출력하고 그렇지 않다면 Confused를 출력한다. 코드 #include #include #include #include #include using namespace std; vector ..
백준[4196] 도미노
2021. 7. 28. 18:27
Algorithm/BOJ
문제 링크 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 풀이 이 문제는 SCC를 이용하여 풀 수 있다. 처음에 이 문제를 보고 아무 점에서나 dfs를 돌려서 dfs를 몇 번 돌리나 카운팅 하면 될 것이라고 생각했다. 하지만 1 -> 2 -> 3 -> 4가 있을 때 1번에서 dfs가 시작하면 문제가 없지만 2, 3, 4번에서 dfs가 시작하면 1번은 처리가 되지 않는다. 그렇기 때문에 SCC를 활용해야한다. 코사라주 알고리즘을 이용하면 stack의 최상단에는..
백준[2150] Strongly Connected Compoment
2021. 7. 28. 14:44
Algorithm/BOJ
문제 링크 https://www.acmicpc.net/problem/2150 풀이 이 문제는 SCC를 구하는 문제이다. 나는 코사라주 알고리즘(Kosaraju's algorithm)을 이용하여 SCC를 구했다. 코사라주 알고리즘은 우선 방향 그래프와 역방향 그래프를 dfs로 탐색하며 진행된다. 1. 방향 그래프를 dfs로 탐색하며 더 이상 갈 수 있는 곳이 없을 때 stack에 push 한다. -이 과정을 모든 정점에 대해 dfs를 진행할 때까지 반복한다. 2. 역방향 그래프를 stack의 top부터 순회하며 이때 만나는 노드들이 SCC다. -이때 top에 있는 정점이 이미 방문한 정점이라면 pop을 한다. https://stonejjun.tistory.com/113 증명은 이 글을 참고하자. 코드 #i..