Baekjoon Review

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이 문제는 BFS를 통해 해결할 수 있다. 문제를 해결하면서 가장 어려웠던 부분이 동시에 여러개의 토마토를 익혀야 한다는 점이였다. 이는 익은 토마토와 안익은 토마토를 배열에 삽입하면서 동시에 큐에 삽입하여 해결하였다. 또다른 문제점으로는 순회가 끝나고 익지 않은 토마토를 찾아 -1을 출력하는 문제였다. 이는 토마토를 익힐 때 순회했던 경로에 익힘 시간을 저장하고 가장 큰 익힘 시..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 BFS를 사용하면 해결할 수 있다. 알고리즘은 다음과 같다. 1. 수빈이가 처음 있는 위치를 queue에 삽입한다. 2. 다음 이동할 수 있는 노드는 수빈이의 위치 - 1, +1 *2 를 queue에 삽입한다. 이때 방문하지 않았거나 100001보다 작아야한다. 3. 이동 중 위치를 찾았다면 시간을 출력한다. 가장 짧은 시간을 출력하라고 했으니 먼저 출력되는 ..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻www.acmicpc.net 이 문제는 BFS를 사용해서 해결할 수 있다. 알고리즘은 다음과 같다.1. 1 번부터 N 번까지 BFS를 수행한다. 2. BFS를 위한 queue는 친구인 번호와 이동한 횟수를 저장한다.3. queue에 저장할 때 케빈 베이컨 수를 증가시킨다.4. 케빈 베이컨 수가 최소인 사람의 번호를 저장한다.  #include #include #include usi..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 이 문제는 브루트포스를 사용해서 해결해야 한다. 브루트포스는 완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 알고리즘 방식 ① 주어진 문제를 선형 구조로 구조화한다. ② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다. ③ 구성된..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이 문제는 DFS의 탐색 결과와 BFS의 탐색 결과를 출력하면 된다. #include #include #include #include using namespace std; int graph[1001][1001] = {0, }; int N, M, V; int visited[1001] = {0,}; vector stack; queue q; void DFS(){ s..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 이 문제는 분할 정복을 사용하는 문제이다. 알고리즘은 다음과 같다. 1. 입력으로 배열의 크기와 찾고자하는 좌표를 받는다. 2. 배열의 크기를 통해 2의 N승을 size로 사용하고, 0, 0을 현재 좌표로 설정한다. 3. 현재 좌표가 찾고자하는 좌표이면 counter를 출력한다. 4. 만약 현재 좌표와 size를 더한 값이 찾고자 하는 좌표보다 크고, 현재 좌표가 찾고자 하는 좌표보다 작..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 배열을 생성하고 DFS와 BFS를 사용해서 해결해야한다. DFS를 한국어로 번역하면 깊이 우선 탐색이며, 이는 그래프 탐색 방법 중 하나이다. 또한 BFS는 너비 우선 탐색이다. 문제 풀이 방식은 다음과 같다. 1. 2차원 배열인 밭에 아무 것도 없게 초기화 한다. 2. 입력에 따라 배추를 심는다. 3. 2차원 배열을 순회하며 밭에 배추가 있고, 방문하지 않았던 좌표이면 DFS나 BFS를 진행한다...

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 처음 문제를 해결할 때는 주어진 함수를 그대로 사용하고, map을 사용하여 0일 때와 1일 때 value를 증가시키는 방식을 사용했다. 하지만 이 방식은 시간 초과 문제로 해결할 수 없었다. 이유를 생각해보니 C++에서 함수 호출은 시간이 오래 걸리는 문제가 있었고 이를 해결하기 위해서는 문제에서 규칙을 찾아야 하는 것을 알게 되었다. 문제를 보면 40까지의 수로 한정되어 있으며 이는 반복문으로 40까지의 수를 배열로 초기화하면 된다. 또한 0과 1, 2, 3을 보면 또다른 규칙을 가지고 있다..