문제 https://programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 풀이 백트래킹을 통해서 문제를 해결할 수 있었다. nCr 조합이라 가정할때 n은 numbers 배열의 인덱스 기반으로 2개를 뽑으면 돼서 numbers의 크기가 될 것이고 r은 2개를 뽑아서 더하는 것이니까 2가 될 것이다. n과 r이 무엇인지 알았으니 조합을 돌려주면 되고, 조합의 합산 결과들의 중복을 방지..
문제 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 백트래킹이란 것은 바로 알아차렸지만 코드도 좀 더러워지고 구현하는데 애를 좀 먹었던 문제이다. 풀이 백트래킹 + 구현 문제이다. '0'인 로또 칸에 대해 갯수를 세고 이를 바탕으로 이미 나온 번호를 제외한 0 ~ 45의 번호들에 대해 조합을 구해주면 된다. 조합을 구한 후에는 정답 로또와 조합을 통해 맞은 로또..
문제 https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 풀이 백트래킹으로 해결할 수 있었다. nums의 모든 요소에 대해 n개 중 3개를 뽑는 조합을 만들어주고 조합이 완성되면 소수 판별 함수를 통해 소수인지 아닌지 판별해주었다. 코드 #include using namespace std; int result = 0; int arr[1001]; bool isused[1001]; bool isP..
문제 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 백트래킹으로 문제에 대한 조합을 구해주면 되는데 (문제가 2개일때 ~ 모든 문제를 전부 사용했을때)에 대한 모든 상황에 대해 조합을 돌려주어야 모든 경우의 수를 확인할 수 있다. 조합을 돌리다 조합이 완성되면 check함수를 통해 그 조합이 문제의 조건에 성립하는지 확인해주었고 성립한다면 경우의 수를 증가시켜주었다. 코드 #include #include #include #include using namespace std; int n, l, r, x; int result = 0; vector leve..
