문제 1. N과 M(1) www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 사용하여 풀 수 있는 문제입니다. 코드를 설명하기 앞서, 백트래킹이 무엇인지 살펴보겠습니다. [백트래킹] 모든 경우를 방문하지만, 규칙을 가지고 방문하지 않아도 될 노드는 방문하지 않는 알고리즘입니다. 해당 노드의 답이 될 수 있는 가능성을 따져보고, 답이 될 수 있는 가능성이 있다면 계속 진행, 그렇지 않다면 부모노드로 돌아가 탐색을 계속합니다. 우리는 이미 이 알고리즘을..
www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 드디어 마지막 문제 풀이입니다! 고생 많으셨어요! 이 문제는 탐색 문제입니다. 이번 포스팅에서는 bfs탐색으로 같이 풀어보겠습니다. 이러한 xy좌표가 있는 문제는 풀이 과정이 거의 비슷한 것 같습니다. 깊이 우선 탐색과 너비 우선 탐색은 잘 알고 있다고 가정하고, 어떻게 이 알고리즘들이 적용되었는지 먼저 코드를 보면서 살펴보겠습니다. #include #include using namespace std; int field[5..
www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이번 문제는 이분 탐색을 이용해 풀 수 있었습니다. 이분 탐색은요, 이분동안 탐색을 하는게 아니라 긴 수를 2개로 나누어 탐색하는 방식입니다. 간단한 알고리즘이니 같이 살펴보겠습니다! [이분 탐색] 1 부터 100까지의 숫자가 있고, 63을 찾는다고 생각해봅시다. 이분 탐색에는 세가지 변수가 필요합니다. low : 찾는 수 중 제일 작은 수 High : 찾는 수 중 제일 큰 수 mi..
www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 예시로 주어진 그림을 자세히 보면, 대각으로 규칙이 있습니다. 빨간 대각 선을 기준으로, 분자와 분모의 합은 같습니다. 우리가 찾아낸 규칙을 통해 다음과 같은 규칙을 생각해 볼 수 있을 것 같습니다. 1. 우리가 찾을 X번째의 대략적인 위치를 찾는다. (분모 + 분자를 통해서 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, . . .) 2. 대략적으로 찾은 위치에서 분자/분모를 하여 분자가 1 ~ n까지 분모는 n ~ 1까지 하여 X의 위치를 찾아냅니다. 코드는 다음과 같습니다. #include int main() { int user_i..
