근황
글을 주기적으로 올리고 싶었건만... 토익 시험과 여러가지 기업 서류를 제출하면서 바빠버리는 바람에 ㅎㅎ..... 잠시 떠나게 되었지만 이제는 다시 코테 준비도 하고 공부도 해야하기 때문에 컴백하였습니다 ㅎㅎ 다시 열심히 달려보겠듭니다!!!
순열 & 조합
오늘은 순열, 조합을 c언어로 구현하는 방법에 대해 알아볼 예정이다.
사실 코딩테스트를 치루다 보면 brute force(모든 경우를 다 따져보고 답을 내는 방식)가 제일 뭔가 귀찮은(?) 느낌인데 순열, 조합 코드를 외우고 있으면 조금 더 수월하게 풀 수 있지 않을까 생각해본당
순열
순열과 조합의 큰 차이점은 누구나 아는 것 처럼 순열은 순서를 고려한다는 것!!! 순열, 조합은 보통 DFS를 이용해서 구현한다. 말로하면 어려우니까 일단 간단한 순열 코드부터 보자
void 순열(int 현재 얼만큼 뽑았나) {
if(현재 얼만큼 뽑았나 == 이만큼 뽑아야지){
다뽑았으니까 뭔가 해라!!
}
else {
for(int i=0;i<후보의 총 갯수;i++) {
if(checklist[i] == false){
뽑아라!!
checklist[i] = true;
순열(현재 얼만큼 뽑았나 + 1);
checklist[i] = false;
}
}
}그냥 나는 이렇게 한글로 한번 써보면 이해하기 빠르던데 ㅎㅎ..... 딱 저렇게만 구현하면 순열은 끝이다. 끝ㅌㅌㅌ!!!
그래서 실제 내가 문제에서 사용한 코드를 한번 가져와봤당
void makeOperatorArray(int idx) {
if(idx == total_num){
max_result = max_result > cal() ? max_result : cal();
min_result = min_result < cal() ? min_result : cal();
}
else {
for(int i=0;i<total_num;i++) {
if(checklist[i] == false){
operator_array_perm[idx] = operator_array[i];
checklist[i] = true;
makeOperatorArray(idx+1);
checklist[i] = false;
}
}
}
}boj14888 풀이 글에 올라온 코드중 일부이다. 순열을 구현할 때 고려할 사항은 크게 3가지라고 생각하는데
-
종료 조건 설정
- 원하는 갯수만큼 뽑고 나서 뭘 할건지를 생각해야댐
- 예를 들어, 위 코드의 경우 total_num 만큼을 뽑게 되면 최대 결과값과 최소 결과값을 업데이트 해준다.
-
방문 기록 확인
- 방문 기록은 보통 checklist 배열을 통해서 구현하고 나 역시도 checklist를 이용했당.
-
탐색은 항상 처음부터!
- 순열은 조합과 다르게 순서를 고려하기 때문에 2 다음에 3을 뽑는 것과 3 다음에 2를 뽑는 것은 다르다.
- (조합의 경우는 보통 오름차순으로 뽑기에 이 부분 유의하자 ㅎㅎ)
위 3개만 고려하면 구현은 간단하다. 이런 코드 쯤은 외우고 있는게 문제 풀때 훨씬 편할 것 같다
조합
위에서 순열을 봤으니 이제 조합을 봐야하는데 조합은 진짜 ㄹㅇㄹㅇㄹㅇㄹㅇ 쉽다. 순열 코드는 모르더라도 조합 코드 정도는 알아야 되지 않을까 ㅎㅎㅎ.......(근데 나는 둘다 못외움;;;;)
위에서 잠깐 말한 것 처럼 조합의 경우 오름차순으로 선택을 한다고 했는데 그러면 어떻게 해야할까???
바로 for문에서 시작지점을 지정해주는 것이다. 이해하기 어려우니까 이것도 먼저 코드를 보자.
void 조합(int 현재 얼만큼 뽑았나, 이제 어디서부터 뽑아야되나) {
if(현재 얼만큼 뽑았나 == 이만큼 뽑아야지){
다뽑았으니까 뭔가 해라!!
}
else {
for(int i=이제 어디서부터 뽑아야되나;i<후보의 총 갯수;i++) {
뽑아라!!
조합(현재 얼만큼 뽑았나 + 1, 이제 어디서부터 뽑아야되나 + 1);
}
}조합의 경우는 선택위치를 기억한다는 것이 핵심이다. 현재 어디서 뽑았는지를 보고 다음 뽑기를 시작할 위치를 인자로 넘겨주는 것인데 이렇게 되면 오름 차순으로 선택이 가능하게 된다. 오름차순 선택이 자동으로 가능하기에 checklist는 필요가 없어지고 코드도 훨씬 간단해졌다. 이제 조합을 실제로 이용한 코드를 보자.
void teamSelect(int level, int beginwith){
if(level == N/2){
cal();
}
else {
for(int i=beginwith;i<N;i++){
team1[level] = people[i+1];
teamSelect(level+1, i+1);
}
}
}진짜 위에랑 똑같다..... 조합에서 고려할 점은 두가지 정도 있당
- 선택 시작 위치를 기억해서 인자로 넘겨주기!!
- 넘겨받은 선택 시작 위치는 for문에서 인자의 초기값이 된다
- 오름 차순 정렬된 결과가 나온다는 것!!
- 작은 숫자부터 뽑아 나가고 순서를 고려하지 않기에 항상 오름차순 정렬된 순서로 결과가 나온다.
- 혹시 이를 바꿔야 한다면 반복문을 조정해주면 된다!!(큰수에서 작은수 순서로 뽑으면 된다 ㅎㅎ...)
순열, 조합은 코딩테스트에서 정말 많이 활용되기에 진짜 진짜 중요한데 위 코드 정도는 복잡하거나 어렵지 않으니까 편하게 외우고 사용하면 좋을 것 같다 ㅎㅎㅎㅎ. 다음에는 DFS, BFS 에 대해 다뤄봐야겠다!
