전체 글

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제는 7576번 토마토와 유사한 문제이다. 하지만 이 문제는 x, y 뿐만 아니라 z 방향이 추가된 문제이다. 따라서 익은 토마토를 계산하기 위해 앞, 뒤도 추가해서 검사해야한다. 이를 위해 dz라는 배열을 선언하였다. 이동 가능한 범위를 검사하고 방문하지 않은 위치이면 토마토를 익히고 큐에 경로를 삽입한다. #include #include using namespace..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제는 BFS를 사용하면 해결할 수 있다. 이 문제에서 가장 어려웠던점은 메모리 관리였다. 처음에 queue와 방문 확인을 위한 행렬을 전역 변수로 생성하였다. 이러한 접근은 메모리 초과라는 오류를 발생시켰다. 따라서 bfs 함수 내에서 queue를 할당하고 함수가 끝나면 queue를 소멸하게 하여 메모리 초과를 막을 수 있었다. 주요 알고리즘은 다음과 같다. 1. 입력 숫자 A와..

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..

- DFS란, 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동하는 방법이다. - 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드로 돌아가서, 다시 깊이우선 탐색을 반복 - 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법 https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif# stack 또는 recursive(재귀 함수)로 구현. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리..