leebaek

문제 주어진 배열의 수를 이용해서 사전순으로 배치된 로또번호 6개의 집합을 만드는 문제 생각 배열에서 중복원소 제거해야겠다 생각함 - 잘못된 인덱스 접근이라고 여러번 틀렸는데, T가 0일 때 바로 종료 안 시키고 func(0, 0) 호출시켜서 그런거임 문제풀이 1.T = 0 이면 프로그램 종료 2.배열에서 중복원소 제거 3.백트래킹 시작 3-1.만약 cnt == 6이면, res 배열의 원소 출력 3-2.사용하지 않은 원소를 res배열에 저장 + 사용표시 4.배열 초기화 코드 #include #include #include using namespace std; vector arr; int K, T=1; int res[15], isused[15]; void del() { while( !arr.empty() ..

문제 N개의 로마 기호를 이용하여 만들 수 있는 숫자의 개수 -중복되어선 안됨 -1, 5, 10, 50 -각 기호를 더해서 숫자를 만듦 생각 벡터 배열에 만든 수를 모두 넣고 마지막에 중복 제거해서 개수를 알아내려고 함 -> 메모리 초과 뜸 func 함수에서 cnt가 N개가 될 때, res를 정렬하고 num이 없으면 res 배열에 넣도록 함 -> 시간초과 뜸 구글링해봤는데, 어짜피 수는 1~1000 안에서 나오니 vis 배열을 만들어서 문제를 풀면 되는 것임!! 문제풀이 1.만약 cnt가 N개가 되면 1-1.isused[num]에 방문하지 않았다면 방문표시 + result++ ( 개수++ ) 1-2.return 2.cur부터 N까지 func(cnt+1, i, num+arr[i]) 함수 호출 - cur부터..

문제 도시 여행을 하는데 드는 비용의 최솟값을 구하는 문제 -방문했던 도시로 다시 갈 수 없음 -마지막에 여행했던 도시에서 처음 도시로 이동할 때는 다시 방문 가능 -성분값이 0이면 여행갈 수 없음 생각 배열에서 중복없이 부분수열 만드는 것처럼 모든 경우를 돌아보면 되겠다 생각함 내가 짠 코드에서 주의해야하는 점은 cnt를 1로 설정해야한다는 점인데, 처음 도시를 정해놓고 여행하기 때문임 모든 도시를 다 돌아봤을 때, 다시 처음 도시로 돌아오기 위해 드는 비용도 더해줘야 함 ( 성분표가 0이면 다시 순회가 안되는 것임 ) * 마지막 도시에서 처음 도시로 오는 비용 * res 최솟값 설정 문제풀이 1.0부터 N-1까지 시작도시를 설정해서 방문표시 + func(1, i, i, 0) 2.만약 cnt가 N개이면..

문제 주어진 N개의 원소로 이루어진 배열에서 M개의 수를 골라 수열을 만드는 문제 -중복되어도 됨 -비내림차순으로 정렬되어야 함 생각 수열을 만들 때 중복되어도 되기 때문에 사용표시를 저장할 배열이 필요없겠다 생각함 문제풀이 1.vector배열 정렬하고, 중복되는 요소 제거 erase함수와 unique함수 사용 2.func(cnt) - res 배열의 현재 원소 개수 3.만약 cnt가 M개가 되면, res 출력하고 return 4.0부터 N까지 arr[i]가 res[cnt-1]값보다 크다면, 4-1.res[cnt] = arr[i] 저장 4-2.func(cnt+1) 호출 코드 #include #include using namespace std; int N, M, num; vector arr; int res[..