https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net - 이분 탐색(Binary Search) - 깊이 우선 탐색(Depth First Search) 1. 30개의 물건이 있고, 이를 선택하는 경우의 수를 모두 더하는 최대 경우의 수는 이다. 따라서 O(2^N)의 시간복잡도를 가지므로 제한시간 1초인 문제에서 시간초과가 발생한다! 결국 이것을 줄일 수 있는 방법은 1. 물건들을 절반으로 분리한다.(part1 집합과 part2 집합으로 분리) 2. 각..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net - 그래프 탐색(Graph Search) - DFS(Depth First Search) - BFS(Breadth First Search) - 이분 그래프 (Bipartite Graph) 1. 이분 그래프란? 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 주어진 그래프가 이분그래프인지 아닌지 검사하는 방법은, 인접한 정점끼리 서로 다른 색으로 칠해서 ..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net - 그래프 탐색(Graph Search) - DFS(Depth First Search) 1. 한마디로 말하자면, 섬이 몇 덩이(영역)있냐는 것이 문제다. 2. 바로 DFS를 떠올렸다. 아직 지나치지 않은 땅을 확인하면, 그 주변에 걸어갈 수 있는 땅을 다 찾을때까지 DFS한다. 위의 과정을 반복한다. 1. DFS는 재귀이므로, 현재 영역의 다음 영역(동서남북+대각선)에 대한 인덱스를 미리 받..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 그래프 탐색(Graph Search) - 너비 우선 탐색(Breadth-First Search) - 깊이 우선 탐색(Depth-First Search) 1. DFS와 BFS의 기본 개념을 잘 이해하고, 이를 코드에 적용할 수 있는지를 스스로 판단할 수 있는 대표적인 좋은 문제다. 2. 문제에서 시키는 대로, DFS와 BFS 코드 공식을 활용해서 풀어내면 된..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net - Graph Searching - DFS(Depth First Search) 1. 한마디로 말하자면, 배추밭이 몇 덩이(영역)있냐는 것이 문제다. 2. 바로 DFS를 떠올렸다. 배추가 있는 한 지역을 확인하면, 그 주변의 배추들을 다 찾을때까지 DFS한다. 위의 과정을 반복한다. 1. DFS는 재귀이므로, 현재 영역의 다음 영역(동서남북)에 대한 인덱스를 미리 받아야 한다. 이때, 주어진 N*M 배열을 넘어..