알고리즘 분류 (그래프 탐색)https://www.acmicpc.net/problem/7569   # 문제 # 필요개념지금까지 했던 2차원 배열 탐색과 달리, 토마토가 들어있는 3차원 상자를 탐색해야 한다. 그래서 삼차원 배열을 생성해주었다. 지금까지 BFS로 그래프탐색을 할 때 방문 여부를 확인하는 isVisit 배열을 생성했었는데, 이 문제는 애초에 전체 토마토를 익게 할 수 있는 "시간" 을 물어보고 있기 때문에, 시간을 넣어줄 배열(map)을 생성해주었다. 토마토 입력이 0인 자리에 초기값을 -1로 설정해주어서 -1이면 방문하지 않은 곳임을 알 수 있도록 했다. 모든 익은 토마토들은 동시에 주변을 익게 만들기 때문에, 입력이 1인 토마토들을 일단 모두 Queue에 담고, 다 담은 후에 bfs 탐색..

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1707  # 문제  # 필요개념이 문제를 풀기 위해서는 이분 그래프의 개념에 대해 먼저 이해해야한다. 개념 공부를 제대로 하지 않고 접근했다가 내 정답률만 잔뜩 낮춰버렸다 😇 그래서 개념 정리겸 블로그 작성 완료 ! 아래 링크를 걸어두었다https://wanna-developer02.tistory.com/191 [Data Structure] Bipartite Graph (이분 그래프) | 자바백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단wanna-developer02.tistory...

class 4+ https://www.acmicpc.net/problem/2206    # 문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. # 예제입력 :  첫째 줄..

Class 3+ 에센셜https://www.acmicpc.net/problem/1697  # 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. # 예제입력 :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.5 17 출력4 # 필요..

백준 알고리즘 분류 (깊이 우선 탐색)https://www.acmicpc.net/problem/1260  # 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.  # 예제입력 :  첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.4 5 11 21..

이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS Monte Carlo Algorithm (몬테카를로 알고리즘) Solve problem 1. N Queens Problem 2. Sum-of-Subsets Problem 3. Graph Coloring Problem 4. Hamiltonian Circuits Problem 1. Backtracking Algorithm (백트래킹 알고리즘) 백트래킹 알고리즘은 어떤 조건을 가진 문제의 해결책을 찾기위해 탐색하는 알고리즘 중 하나이다. 모든 경우의 수를 탐색하긴 하지만, 완전탐색 알고리즘과 달리 어떤 조건을 가지고 있으므로 배제되는 경우들이 많아 효율이 더 높다..