[백준] 11724번: 연결 요소의 개수 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 【 풀이 】 서로 연결되어 있는 정점의 그룹이 몇 개인지를 구하는 문제이다. 정점이 서로 연결되어 있는지만 확인하면 되므로, 비교적 구현하기 쉬운 DFS 로 문제를 해결했다. DFS 함수를 호출할 때 연결되어 있는 곳은 이미 다 방문처리가 되므로, 반복문으..
[백준] 18870번: 좌표 압축 [C++]
알고리즘 분류: 정렬, 값/좌표 압축 문제 링크: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 【 풀이 】 범위 내의 중복된 값을 뒤로 보내주는 unique 함수와, 이진 탐색 기반으로, 찾으려는 값보다 크거나 같은 숫자가 몇 번째 인덱스에서 처음 나오는지를 알려주는 lower_bound 함수를 이용하여 해결했다. 풀이 과정은 다음과 같다. 우선 원본 좌표를 저장한 벡터와 원본 좌표를 복사..
[백준] 1016번: 제곱 ㄴㄴ 수 [C++]
알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체 문제 링크: https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 【 풀이 】 에라토스테네스의 체를 활용하여 해결하는 문제이다. 처음엔 2부터 하나씩 제곱해 가면서 4, 9, 16, 25, 36.. 등의 제곱수들로 나누어 떨어지는 지를 체크해서 하나씩 제거해 가는 아이디어를 떠올렸다. 하지만 가능한 min 값이 0부터 1,000,000,000,000, 즉 1조나 된다. ..
[백준] 1002번: 터렛 [C++]
알고리즘 분류: 수학, 기하학, 많은 조건 분기 문제 링크: https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 【 풀이 】 중학교 때 배운 원의 성질을 기억하고 있다면 쉽게 해결할 수 있지만, 많은 조건을 분기해야 하므로 오답률이 꽤 높은 문제이다. '원'이란 평면 위의 한 점에 이르는 거리가 일정한 평면 위의 점들의 집합을 의미한다. 문제에서 말하는 조규현과 백승환의 좌표는 원의 중심이라고 볼 수 있고, 류재명과의 거리는 원의 중심으로부터 류재명이 있다고 판단한 거리, 즉 반지름이 된다. 즉, ..
[백준] 10811번: 바구니 뒤집기 [C++]
알고리즘 분류: 구현, 시뮬레이션 문제 링크: https://www.acmicpc.net/problem/10811 10811번: 바구니 뒤집기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 【 풀이 】 벡터에 1 ~ N 의 숫자를 push_back 하고 start와 end 변수를 받아주고 그 범위를 reverse 함수를 이용해 뒤집어주면 된다. 단 end는 그대로 쓰지만, 0번째 인덱스부터 접근해야 하기 때문에 start는 -1을 한 값을 이용해야 한다. 【 코드 】 #include #include #include using na..
[백준] 2667번: 단지번호붙이기 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 【 풀이 】 2차원 배열을 순회하면서 '1' 이 나왔을 때 모든 인접 접점을 방문하여 그 개수를 체크하는 문제이다. 즉 DFS, BFS 어느 것을 쓰든 무관하지만 여기선 BFS를 사용했다. 풀이 자체는 간단하다. 2차원 배열을 입력받고, 0부터 [n][n] 까지 순회하면서 '1' 이 적혀 있는 부분부터 그 부..
