노는 게 제일 좋아

// 2022.02.27 다시 품 어려운 문제는 아닌데.. 정확하게 시키는대로 하는 것이 어렵다. 아니.. 하는 것이 어려운 것보다 우리가 짜는 알고리즘이 어떻게 진행될 지 정확하게 알아야 한다는 것이 포인트다. https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 큐를 이용하는 것 같지만. 여기서 중요한 조건이 뒤에 문서를 확인해야한다는 말이 있다. 즉, 탐색이 가능해야한다는 것이다. 스택, 큐는 전체 탐색이 불가능하다. 그렇게 만들어졌다. 때문에 전..

이 문제도 BFS의 기본적인 문제라고 볼 수 있지만 역시나 BFS를 어렵게 하려면 입력을 이상하게 주면 된다. https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이번 풀이의 핵심은 BFS가 아니다. 문제에서 이 사각형의 넓이를 무엇으로 구할 것이냐? 가 문제다. 또한 주어진 조건에 대해서 어떻게 예외처리를 할 것이냐? 가 문제다. 우리가 지금 노드의 개수와 사각형의 개수가 1:1 대응하는가? 꼭짓점이 노드라고 한다면 8 * 6..

뭐 이것도 BFS의 기본문제라고 볼 수 있겠다 다만 이건 입력을 특이하게 받는 케이스? 라고 보면 된다. https://www.acmicpc.net/problem/1012 #맞는 풀이 하지만 정제되지 않음 손에 익지 않아서 20분정도 걸림 주석포함 솔직히 다른 사람은 어떻게 그렇게 정제된 풀이가 바로 생각나는거지??... 아직 갈 길이 멀다. #include #include #include #define X first #define Y second using namespace std; int tc; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //t..

BFS의 응용문제로 BFS라고 생각지 않지만 의외로 BFS라서 놀라는 초보인 나에게는 놀라움의 대상이었던 문제다. https://www.acmicpc.net/problem/1697 이 문제도 내가 풀긴 풀었지만 왠지 더 잘 풀수 있을 것 같다. #1 뭔가 틀린 풀이 #include #include #include using namespace std; int dist[100001]; // 0 m >> n; queue Q; fill(dist, dist+100000, -1); // 0~ 100000까지 -1 dist[m] = 0; Q.push(m); while(!Q.empty()){ int cur = Q.front(); Q.pop(); if(cur-1 >= 0 && dist[cur-1] < 0){ dist[c..

BFS의 응용문제다. 어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다. www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제도 BFS를 이용한다는 감이 온다. 고려해야 할 조건이 몇가지 있다. 1. 지훈이의 탈출 조건 2. 불이 있는 곳에 지훈이 있을 수 없다. 우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다. 즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다. -> 다시 말해서 가..

이것도 BFS의 기본이라고 볼 수 있다. www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전 문제의 최단경로의 경로문제라고 해도 무방하다. 하지만 약간 꼬아놨으니 BFS의 시작점이 여러군데다. 근데 뭐 별다를 거 없다. 시작점을 큐에 다 넣고 시작하는 것과 같이 얘도 똑같이 해주면 된다. #맞는 풀이 다만 최적화는 되어있지 않은 풀이 #include #include #define X first #define Y second using nam..

이 문제도 이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데 뭐 메모리랑 관련이 있다고만 해두겠다. **사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다. # 맞는 풀이 #include #include using n..

경로 탐색의 핵심은 탐색 방법이다. 그 중 얘는 BFS다. www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 왜 BFS일까?는 최단경로를 찾아야하기 때문이다. DFS는 최단경로를 보장하는 방법이 아니다. 어떠한 경우에 대해서도 최단경로를 찾기 위해서는 BFS를 쓸 수 있다. 일반적으로 메모리는 DFS보다 BFS가 많이 먹을 수 있는..가능성이 높다 나는 이것을 논리가 맞다고 생각하고도 엄청 많이 틀렸다. 바로 입력에 대해서 확인을 소홀히 해서 그렇다. 이 문제에서 입력은 공백없이 주어졌다. ..

물론 생각은 한 번에 났으나 구현이 20분은 걸렸다. www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 처음 문제보면서.. ?? 어떤 자료구조를 쓸까.. 만약 shift를 하면 앞 뒤 둘다에서 삭제 삽입이 일어나는구나. -> Deque를 쓰자. Double ended queue 왼쪽으로 미는 거랑 오른쪽으로 미는 거랑 구분을 해야겠다. **덱을 복사해서 쓰고 이동횟수가 적은 쪽을 다시 원본으로 복사해서 쓰자. -> 다른 방법이 바로 생각안나서 N도 적어서 ..

음 0.5초에 추가 시간이 없네 ㅎ 문제 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 첫째 줄에 분수를 출력한다. 음 보면 행렬의 행과 열을 맞춘 느낌이다 ㅎ 분수로 위장한 행렬느낌 즉, 분자가 행 분모가..