https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si > N; for (int i=0; i> x >> y; p[i].first..
알고리즘 문제풀이/백준
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/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net - 이분 탐색 (Binary Search) 1. 국가예산의 총액은 한정되어 있고, 여러 지방의 예산 요청액은 국가 예산 총액을 넘어설 수도 있다. 그렇기에 여러 지방의 예산 요청액을 최대한 충족하는 선에서, 국가예산 총액을 최대한 써야 한다(상한가 지정). 2. 상한가 지정은 Binary Search 로 진행을 한다. 1. Binary Search 진행 시에 low, mid, high 관계를..
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net - 자료구조(Data Structure) - 덱(Deque) 1. C++에서 배열을 지원하는 컨테이너로 대표적인 가 있지만, 문제를 보면 양쪽에서 pop과 push를 해야하는 상황이므로 배열을 더 유연하게 다룰 수 있는 를 쓰기로 했다. 1. 문제 이해가 우선이다. 1~N까지 적혀 있는 카드들을, 한꺼번에 왼쪽으로 밀거나 오른쪽으로 옮기면서 순서대로 원하는 카드들을 뽑는다는 것을 이해해야 한다..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net - Graph Searching - DFS(Depth First Search) 1. 한마디로 말하자면, 배추밭이 몇 덩이(영역)있냐는 것이 문제다. 2. 바로 DFS를 떠올렸다. 배추가 있는 한 지역을 확인하면, 그 주변의 배추들을 다 찾을때까지 DFS한다. 위의 과정을 반복한다. 1. DFS는 재귀이므로, 현재 영역의 다음 영역(동서남북)에 대한 인덱스를 미리 받아야 한다. 이때, 주어진 N*M 배열을 넘어..
