[백준] 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' 이 적혀 있는 부분부터 그 부..
[백준] 2178번: 미로 탐색 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 【 풀이 】 모든 인접 정점을 방문해야하는 문제라면 DFS와 BFS 둘 다 사용해도 무방하다. 이 문제는 최단 거리를 구해야하기 때문에 BFS 가 적합하다. (모든 가중치가 1이기에, BFS 로 구하면 최단 거리가 된다.) 즉 한칸 움직일 때마다 목적지 까지의 거리가 +1 씩 더해지는 것이다. 【 코드 】 #include #include #define MA..
[백준] 1049번: 기타줄 [C++]
알고리즘 분류: 수학, 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 【 풀이 】 그리디 알고리즘 기초 문제이다. 결국 문제에서 요구하는 것은 6개짜리 패키지의 가격과 낱개의 가격들을 입력받았을 때 어떤 조합으로 사야 최솟값으로 끊어진 기타줄을 바꿀 수 있는지이다. 최솟값을 구할 수 있는 아이디어는 세가지이다. 6개 패키지 중에서 가장 최솟값인 패키지로만 기타줄을 샀을 때(N 초과해도 무관) 낱개 중에서 가장 ..
[백준] 1026번: 보물 [C++]
알고리즘 분류: 수학, 그리디 알고리즘, 정렬 문제 링크: https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 【 풀이 】 A 배열을 정렬하고 B 배열을 정렬하지 않았을 때, 각 요소들을 곱해서 더한 값이 최솟값이 되게 하는 문제이다. 이 문제는 A 배열에서의 최댓값 * B 배열에서의 최솟값을 각각 더해가면 간단하게 해결할 수 있다. 그러나 이 문제는 B 배열을 정렬했다고 해서 큰 문제는 없다. 문제 의도에 맞지 않지만, 그렇다고 해서 더 ..
