본문 바로가기

재귀

 (3)
백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 2 지금까지 강의 중에 제일 어려웠다. 백트래킹 부분이 많이 약한 것 같다. 보통 앞의 문제를 풀어보면 요령이 생겨 뒤의 문제를 곧잘 푸는데 이건 정말 손도 못 댔던 것 같다. 그만큼 더 잘 이해하고 넘어가야 하는 이유다.. 하나하나 곱씹으면서 정리해보자. - * N -Queen (high) : 크기가 n*n인 체스판 위에 n개의 queen을 놓는 경우의 수를 구하는 문제다. 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net - queen은 상하, 좌우, 대각선까지 다 갈 수 있다. 따라서 queen의 위치를 잡았을 때, 상하좌우..
백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 1 주로 풀었던 문제를 다른 방법으로 푸는 식이었다. 더 빨리 풀리는 문제도 있었고, 오히려 더 느리게 풀리는 문제도 있었다. 어쨌든 재귀를 사용하면 식 자체는 간단해진다. 하지만 까딱 잘못하다가는 메모리가 오버 되거나 무한 루프에 빠지기 쉽다. 제한 조건을 잘 걸어줘야 한다. 정리 시작! - * 로또 (mid) : 앞에서 순열을 사용해서 풀었던 문제를 재귀로 풀어봤다. 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net #include using namespace std; int k, a[13],..
백준 알고리즘 기초 - 브루트 포스 (재귀, 백트래킹) 재귀에는 어느정도 익숙해진듯 하다. 재귀를 풀었을 때 특유의 쾌감도 있는듯.. 하지만 갈 길은 아직 멀다.... 정리 시작! - 이전에 풀었던 문제를 재귀를 사용해서 풀어보자. * 1, 2, 3 더하기 (low) : 정수 n을 1,2,3의 합으로 나타내는 방법의 수 구하기 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net #include using namespace std; int ans = 0; void go(int left, int n)..

티스토리툴바