15686 치킨 배달 / 순열 조합.

phoenixKim·2021년 8월 18일
0

백준 알고리즘

목록 보기
147/174

15686 치킨 배달

-> struct로 next_permutation 할때는 sort를 할수 없기 때문에 따로 vector 변수 만들어서 진행해야 한다.

언제 순열? 언제 조합?

  • 언제???

    : 순열은 순서를 변경하면서 경우의 수를 찾을 때.
    조합은 고정된 순서에서 경우의 수를 찾을 때.

조합은 언제 사용할까?

: n 개 중에서 순서에 상관없이 몇개를 선택해야 할 경우에 사용함.

c++에서의 필수조건

필수 조건 : 정렬을 먼저 해야 함.

순열과는 다르고, 순열로 할 때는 문제가 있음.

  • 어떤 알고리즘을 활용 하냐면?
    : 백트래킹을 활용함.

    순열은 순서대로 나열한다라는 의미임.

방법.

1) 해당 카운트 숫자에 벡터가 도달시에 추출하도록 함.
2) combi 재귀 함수에서 for문으로 시작 인덱스를 설정해서 벡터에 넣어줌.
3) 그리고 바로 다음 인덱스의 원소로 재귀를 시작
4) 벡터에서 pop_back을 함으로써 완료시키고 다음 원소 집어넣음.

특징

: 중복 발생할 수 없음.

problem , 코드

: {1,2,3,4,5} 에서 3개를 뽑았을 때, 오름차순일 때만 추출하라.

  • 코드

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>

int cnt = 3;
vector<int>res;

void combi(vector<int>&v , int start)
{
	if (res.size() == cnt)
	{
		for (auto iter : res)
		{
			cout << iter << " ";
		}
		cout << endl;
	}

	for (int i = start; i < v.size(); ++i)
	{
		// 이걸로 하면, 첫인덱스에서 오류 발생함. 
		//if (v[i] > res.back())
		//	continue;
		res.push_back(v[i]);

		// 이렇게 하면 안됨. 
		//combi(v, start + 1);

		// 다음 원소의 값을 넣어야 하므로
		combi(v, i + 1);
		res.pop_back();

	}
	return;
}


int main() 
{
	vector<int> v{ 1,2,3,4,5 };
	combi(v, 0);
}
  • 결과

순열 사용시 알아야 할점.

: 반드시 정렬 하자.

순열과 pair - 중요함!

next_permutation() 의 3번째 인자는 비교함수임
, pair의 경우, first 끼리 동일할 경우, 다른 조건 처리를 해야 함.
: stl 철저 입문. p.406

핵심!

-> pair로 비교 처리하기 위해서는 직접 비교 함수 만들자.
--> 이때는 불체크 배열을 사용해서 처리하자.

여기 중요!!!

next_permutaion 할때는 반드시 1차원 벡터로 처리하자.
그리고 1차원 벡터와 pair를 동기화 하면서 진행하자.

  • 관련 문제
    : 백준 15686 치킨 배달.

수학 콤비네이션

: 64C3 : 64개 중에서 3개를 선택할 수 있는 모든 경우의 수를 뜻함.

계산 : 64! / (64- 3)! * 3!

추가. 순열에 대해

next_permutation

  • 순서에 관계없이 stl 이 알아서 순번을 랜덤으로 만들어줌.
  • 반환값.
    - 순열의 가장 마지막 내림차순이 되었다고 판단했을 때 false를 반환함.

특징
-> 반드시 오른차순으로 정렬된 상태에서 진행해야 함.
1) 오름 차순아닌 상태에서 조합 사용했을 경우.

2) 오름 차순으로 정렬된 상태에서 조합 진행할 경우

-> 1,2,3으로 조합 만들 수 있는 모든 경우의 수가 출력됨

  • next_permutation 함수를 call 하자마자, 바로 컨테이너 간의
    순번을 바로 변화시킴
    1) while문으로 돌리면,,
    -> 10,20,30 이 나오지 않는 것을 확인할 수 있음.
    => 출력 하기 전에 조합 한 번 진행됨을 확인할 수 있음.

    2) 그래서 한 번 출력한 후에 call하는
    do~while문으로 해야 함을 확인할 수 있음.

    -> 모든 조합이 출력됨을 확인함.

관련 문제

  • 카카오 : 수식최대화
  • 프로그래머스 : 소수찾기
  • 백준 : 일곱 난쟁이

https://programmers.co.kr/learn/courses/30/lessons/42839


: do_while 내부에서 v의 컨테이너들이 조합순으로 변경되는 것이다.

순열이란?

: 서로 다른 n개의 원소를 한 줄로 세우는 것이다.

해당 함수의 특징
1. 오름 차순으로 정렬된 값을 가진 컨테이너만 사용가능하다.
2. 디폴트로 operator < 를 사용한다.
3. 중복을 제외한다.
4. do - while문을 사용하자.

순열 소스코드

int main()
{
	vector<int> v{ 1,2,3 };

	do
	{
		for (auto iter : v)
		{
			cout << iter << " ";
		}
		cout << endl;

	} while (next_permutation(v.begin(), v.end()));

}

1. 오름차순으로 정렬해야 한다.

  • 정렬하기 않았을때 , 조합 수가 덜 나온것을 확인할 수 있다.

  • 모든 조합이 나왔다.

3. 중복을 제외 한다.

: 컨테이너에 들어가 있는 수의 중복을 제외한다는 것이 아니라,
조합으로 나열했을 때 발생하는 경우의 중복을 의미하는 것이다.

string에 순열 함수를 사용하면?

: 벡터처럼 동작한다.

profile
🔥🔥🔥

0개의 댓글

관련 채용 정보