인프런 커뮤니티 질문&답변

안녕하세요 noah님 ㅎㅎ

    for(int i = 1; i < (1 << n) - 1; i++){ // -1 있는 이유는??

이부분은 모든 경우의수를 고려하는 부분이기 때문에 그렇게 해야 합니다.

예를 들어 3가지의 요소의 포함, 비포함의 모든 경우의 수는

000

001

010

011

100

101

110

111

이렇게 총 8개입니다. 이를

0 ~ 7까지의 값으로 나타낼 수 있죠.

이를 for문으로 나타내면

for(int i = 0; i < (1 << 3); i++) 이 됩니다.

그러나 이 개리멘더링 같은 경우는

반드시 2개의 영역으로 나눠야 하는 것입니다. 즉, 000과 111을 빼야 하기 때문에

for(int i = 1; i < (1 << 3) - 1; 이런식이 되어야 합니다.

또한, 세그먼트의 오류가 발생되는 것은.

여기 보시면 이 코드는 반드시 2개로 나눠진다는 것을 가정해서 짠 코드입니다.

        for(int j = 0; j < n; j++){
            if(i & (1 << j)) comp[j + 1] = 1, idx1 = j + 1;
            else idx2 = j + 1;
        }

때문에 만약 111 이런 꼴의 한개의 영역으로 나오는 경우에 대한 것을 수행하지 못하기 때문에 UB가 떠서 그런 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.