본문 바로가기

Algorithm

 (57)
[백준] 2667번: 단지번호붙이기 문제링크 : https://www.acmicpc.net/problem/2667 문제풀이 dfs, bfs로 풀 수 있는 문제이다. 1) 1인 지점을 찾아 그 지점부터 상, 하, 좌, 우로 깊이 우선 탐색을 한다. 2) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다. 3) 탐색이 끝나면 다시 1인 지점을 찾아서 깊이 우선 탐색을 한다. 4) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다. 5) 탐색이 끝나면 다시 1인 지점을 찾아서 깊이 우선 탐색을 한다. 6) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다. 7) 더 이상 셀 집이 없다면 (1인 값이 없다면) co..
[백준] 7576번: 토마토 문제링크 : https://www.acmicpc.net/problem/7576 문제풀이 bfs로 풀 수 있는 문제이다. 1. 익은 토마토(값이 1인 것)들을 찾아 큐에 넣고, 방문 체크를 한다. 2. 큐에 있는 값들을 하나씩 빼면서 왼쪽, 오른쪽, 앞, 뒤 네 방향에 익지 않은 토마토가 있는지 체크한다. 3. 익지 않은 토마토(값이 0인 것)가 있으면, 큐에 넣고 방문 체크를 한다. 4. 큐에 값이 없을 때까지 반복한다. 큐에 값이 없을 때까지 작업을 반복했는데도 0인 토마토가 있으면 토마토가 모두 익지 못하는 상황이므로 -1을 출력한다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOExcept..
[백준] 1697번: 숨바꼭질 문제링크 : https://www.acmicpc.net/problem/1697 문제풀이 bfs로 풀 수 있는 문제이다. 1. X - 1로 이동 2. X + 1로 이동 3. X * 2로 이동 세 가지의 경우를 모두 큐에 넣는다. 최대 100,000까지 가능하므로 크기 100,000 + 1인 배열을 생성하여 방문여부를 체크한다. 동생을 찾을 때 까지 (X == K일 때 까지) 작업을 반복한다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.Queue; import java.util.Linke..
[백준] 2178번: 미로탐색 문제링크 : https://www.acmicpc.net/problem/2178 문제풀이 bfs로 풀 수 있는 문제이다. 필요한 데이터 - 미로 데이터를 저장할 N x M 크기의 배열 - 칸을 방문했는지 체크하기 위한 N x M 크기의 배열 - 상하좌우 이동을 위한 방향 배열 1) 첫 번째 칸부터 상, 하, 좌, 우로 한 번씩 이동한다. 2) 이동한 위치가 배열의 범위 안에 들면, 이동할 수 있는 칸인지 확인한다. (값이 1이고, 방문하지 않은 지점이면 이동 가능) 3) 이동할 수 있는 칸이면 이동 횟수 저장 후 큐에 삽입한다. 4) 큐에 있는 요소를 제거한 후, 그 칸부터 다시 상, 하, 좌, 우로 한 번씩 이동한다. (이하 반복) 따로 Point라는 클래스를 만들어 x, y, 그 칸 까지의 이동 횟수를..
[백준] 1260번: DFS와 BFS 문제링크 : https://www.acmicpc.net/problem/1260 문제풀이 DFS는 보통 재귀 또는 스택을 이용해 풀고, BFS는 큐를 이용하여 구현한다. 이차원 배열로 두 정점이 연결되어 있는지 간선 정보를 저장해놓는다. DFS : https://manzoo.tistory.com/69 [Algorithm] Depth-first-search (깊이 우선 탐색) 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노.. manzoo.tistory.com BFS : https://manzoo.tistory.com/12?cat..
[Algorithm] Depth-first-search (깊이 우선 탐색) 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 출처 : 위키백과 https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89 깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를..
[백준] 1912번: 연속합 문제링크 : https://www.acmicpc.net/problem/1912 문제풀이 동적 계획법으로 쉽게 풀 수 있는 문제이다. dp배열을 따로 만들어서, 각 자리까지의 최댓값을 저장한다. 소스코드 /* * 백준 1912번: 연속합 */ #include #include using namespace std; #define MAX 100001 int arr[MAX]; int dp[MAX]; int main() { int n; cin >> n; for (int i = 0; i > arr[i]; } dp[0] = arr[0]; int max_sum = arr[0]; for (int i = 1; i < n; i++) { // (현재 값, 현재 값 + 이전까지의 최댓값) 중 더 큰..
[백준] 1978번: 소수 찾기 문제링크 : https://www.acmicpc.net/problem/1978 문제풀이 소수란 1과 자기자신으로만 나눠지는 1보다 큰 양의 정수를 말한다. 따라서 입력받은 숫자 n이 2 ~ (n-1) 사이에서 나눠지면 그 수는 소수가 아니다. 소스코드 /* * 백준 1978번: 소수 찾기 */ #include using namespace std; bool isPrimeNumber(int number) { if (number == 1) return false; for (int i = 2; i > N; int count = 0; while (..

티스토리툴바