뜌릅

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net bfs으로 풀게 되면 매우 쉽게 풀 수 있는 문제이다. #include #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(ll i=0;i> m >> n; vector box(n, vec..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 단순히 문제를 푸는 것보다 입력을 받고 해당 입력을 배열에 어떻게 표현해낼지가 더 어려웠던 문제이다. isdigit()라는 함수와 스트링 변수에 char이나 스트링변수를 더하면 뒤에 이어 붙어진다는 사실을 알게 되었다. 위의 2가지 사실을 활용하여 더 코드를 간단하게 만들었다. #include #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 재귀반복을 통하여 풀 수 있는 문제이다. 사각형으로 1사분면,2사분면,3사분면,4사분면으로 나누어서 해당 좌표가 어떤 사분면에 있는지에 따라서 재귀반복 하였다. #include #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); in..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 유기농 배추는 dfs혹은 bfs로 간단하게 풀어낼 수 있는 문제이다. 배추가 존재하고 이전에 방문하지 않았던 좌표만을 재귀를 통해 진입하는게 코드의 핵심이다. 다만 흰배추잎벌레는 뭉쳐있는 배추를 한번에 처리가 가능하므로 처음 dfs함수로 진입할 때에만 cnt의 값을 1 증가시킨다. #include #include using namespace std; #define endl '\n' #define fast_io..

두 배열의 합 2143번 [백준] 이번에 풀은 문제는 아이디어성 문제 였습니다. 두 배열의 부분합이 t값이 나오면 되는 문제입니다. 이 경우 또한 전체탐색으로 t값이 나오는 경우의 수를 찾기에는 시간복잡도를 초과하게 됩니다. 따라서 아이디어의 핵심은 각 배열을 통해 부분합을 모두 저장한 배열을 미리 만들어 두는 겁니다. 그 뒤는 부분합 배열을 통해 bianry search을 응용한 함수 upper_bound와 lower_bound을 통해 구하면 되는 간단한 문제였습니다. vector A; vector B; ll t, n, m, ans = 0;// ll is long long void solve() { cin >> t >> n; A = vector(n); for (ll& x : A)cin >> x; cin..

비숍 1799번 [백준] 이번에 풀은 문제는 비숍의 특징을 이용하여 체스판을 2개로 쪼개서 계산 복잡도를 초과하지 않는 방법으로 풀어냈습니다. 문제을 쪼개지 않고 완전탐색으로 문제을 풀게 될 경우, 서로에게 영향을 끼치므로 정확히는 모르지만 대략 최대 2^100번의 계산을 하게 된다고 볼 수 있습니다. 하지만 비숍의 특성상 검정칸에 있는 비숍은 검정칸에만 영향을 끼칠 수 있고, 하얀칸에 있는 비숍은 하얀칸에만 영향을 끼칠 수 있습니다. 아이디어는 칸을 나누는 것입니다. 만약 칸을 검정칸과 하얀칸을 따로 나누어 계산을 하게 된다면 10*10 은 5*5인 칸 2개를 계산하는 것과 같아집니다. 2의 25승은 대략 3000만이므로 요구하는 시간복잡도 10초에는 넉넉하게 들어가겠지요. 단순한 backtrackin..

외판원 순회 2098번 이번에 풀은 문제는 외판원 순회 TSP(Traveling Salesman Problem)입니다. 문제는 외판원이 외부의 지역들을 순회하면서 물건을 팔고 다시 집으로 돌아오는 것과 같이. 각 노드을 최소비용으로 한번씩만 순회하여 돌아오는 거리의 합을 구하는 것입니다. 먼저 문제을 풀기전에 전체 탐색으로 구해 보았는데요. 아래와 같이 Bitmask을 사용하여 방문한 노드를 인식함으로써 탐색할 수 있었습니다. 하지만 이렇게 풀게 되면 시간초과가 나게 될것입니다. int n, ans = inf; int path[17][17]; void find_path(int start, int end, int cur_path_distance, int visited) { int all_visited = (1

부분합 문제로 point to point 개념을 사용하여 쉽게 풀어내었다. 2003번 문제와 매우 비슷한 유형이다. #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(int i=0;i> n >> s; vector v(n); for (int& x : v)cin >> x; int low = 0, high = 0; int sum = v[0]; int length = inf; while (low s) { length = min(length, high - low + 1); sum -= v[low++]; if (low ..

오랜만에 백준 문제를 풀어 보았다. meet in the middle이라는 기법을 활용하여 푸는 문제이다. meet in the middle이라는 기법을 처음 접해 보았는데, 부분수열의 합1에서 모든 경우의 수를 구하여 풀었던 것을 같이 활용하여 문제를 풀 수 있었다. #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(int i=0;i> N >> S; vector v(N); rep(i, N)cin >> v[i]; int half = N / 2; vector first(1

위상정렬(Topological sort)의 아주 기초적인 문제입니다. 매우 기초적인 문제로, 메모리와 시간을 크게 신경 쓰지 않고 구현을 해도 되었으므로, 자료구조를 복습하는 차원에서 구현을 하였습니다. #import using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(int i=0;i>n>>m; vector v[1000]; queue q; vector result; rep(i,m){ int x,y,z; cin>>x; if(x == 0)continue; cin>>z; rep(j,x-1){ cin>>y; v[z-1].pb(y-1..