Microsoft MVP성태의 닷넷 이야기
.NET Framework: 590. C# - 모든 경우의 수를 조합하는 코드 (2) [링크 복사], [링크+제목 복사],
조회: 25354
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 1개 있습니다.)

C# - 모든 경우의 수를 조합하는 코드 (2)

지난번 글에서 모든 경우의 수를 조합하는 코드를 알아봤는데요.

C# - 모든 경우의 수를 조합하는 코드 (1)
; https://www.sysnet.pe.kr/2/0/10977

글을 보시면 아시겠지만, "모든 경우의 수"는 2n과 같습니다. 2의 n승이니, 이는 포화 2진 트리 형식으로도 표현이 가능합니다. 가령 2개의 요소를 갖는 경우의 수를 보면 다음과 같이 트리로 표현됩니다.

bin_tree_combination_1.png

루트에서부터 하위 리프 노드로 가면서 (또는, 거꾸로) 이어지는 숫자의 배열을 나열해 보면 경우의 수와 동일한 구성을 볼 수 있습니다.

0 [0 0]
0 [0 1]
0 [1 0]
0 [1 1]

따라서, 경우의 수를 탐색하는데 재귀호출로 이렇게 표현하는 것도 가능합니다. (트리 구성은 임의 구현이 가능한데, 아래의 코드는 그 하나의 사례라고 보시면 됩니다.)

public class Node
{
    public readonly Node Parent;
    public readonly int Index;

    public Node(Node parent, int index)
    {
        this.Parent = parent;
        this.Index = index;
    }
}

public class Combination
{
    readonly int _depth;
    readonly int[] _sourceList;

    List<Node> _leafNodes = new List<Node>();

    public Combination(int [] elems)
    {
        _sourceList = elems;
        _depth = _sourceList.Length;

        Prepare();
    }

    void Prepare()
    {
        VisitElement(1, new Node(null, 1));
        VisitElement(1, new Node(null, 0));
    }

    private void VisitElement(int depth, Node node)
    {
        if (depth == _depth)
        {
            _leafNodes.Add(node);
            return;
        }

        VisitElement(depth + 1, new Node(node, 1));
        VisitElement(depth + 1, new Node(node, 0));
    }

    internal IEnumerable<int []> Combinations()
    {
        foreach (Node leaf in _leafNodes)
        {
            Node node = leaf;
            List<int> elems = new List<int>();
                
            int index = 0;
            while (node != null)
            {
                if (node.Index == 1)
                {
                    elems.Add(_sourceList[index]);
                }

                index++;
                node = node.Parent;
            }

            yield return elems.ToArray();
        }
    }
}

사용은 이렇게 할 수 있고,

static void Main(string[] args)
{
    int[] list = new int[] { 200, 300, 500, 600 };

    Combination c = new Combination(list);

    foreach (var item in c.Combinations())
    {
        PrintElems(item);
    }
}

private static void PrintElems(int[] elems)
{
    Console.Write("{ ");

    foreach (var elem in elems)
    {
        Console.Write(elem + ", ");
    }

    Console.WriteLine(" }");
}

출력 결과는 모든 경우의 수입니다.

{ 200, 300, 500, 600,  }
{ 300, 500, 600,  }
{ 200, 500, 600,  }
{ 500, 600,  }
{ 200, 300, 600,  }
{ 300, 600,  }
{ 200, 600,  }
{ 600,  }
{ 200, 300, 500,  }
{ 300, 500,  }
{ 200, 500,  }
{ 500,  }
{ 200, 300,  }
{ 300,  }
{ 200,  }
{  }

역시 개념만 알아두면, 언제든 쉽게 만들 수 있는 코드입니다.

(첨부 파일은 이 글의 예제 코드를 포함합니다.)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 6/27/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




... 106  107  108  109  [110]  111  112  113  114  115  116  117  118  119  120  ...
NoWriterDateCnt.TitleFile(s)
11209정성태5/25/201770270Windows: 143. Windows 10의 Recovery 파티션을 삭제 및 새로 생성하는 방법 [16]
11208정성태5/25/201729008오류 유형: 390. diskpart의 set id 명령어에서 "The specified type is not in the correct format." 오류 발생
11207정성태5/24/201729892Windows: 142. Windows 10의 복구 콘솔로 부팅하는 방법
11206정성태5/24/201723056오류 유형: 389. DISM.exe - The specified image in the specified wim is already mounted for read/write access.
11205정성태5/24/201722830.NET Framework: 658. C#의 tail call 구현은? [1]
11204정성태5/22/201732357개발 환경 구성: 316. 간단하게 살펴보는 Docker for Windows [7]
11203정성태5/19/201719680오류 유형: 388. docker - Host does not exist: "default"
11202정성태5/19/201720759오류 유형: 387. WPF - There is no registered CultureInfo with the IetfLanguageTag 'ug'.
11201정성태5/16/201724304오류 유형: 386. WPF - .NET 3.5 이하에서 TextBox에 한글 입력 시 TextChanged 이벤트의 비정상 종료 문제 [1]파일 다운로드1
11200정성태5/16/201721070오류 유형: 385. WPF - 폰트가 없어 System.IO.FileNotFoundException 예외가 발생하는 경우
11199정성태5/16/201722264.NET Framework: 657. CultureInfo.GetCultures가 반환하는 값
11198정성태5/10/201724341.NET Framework: 656. Windows Forms의 오류(Exception) 처리 방법에 대한 차이점 설명
11197정성태5/8/201720532개발 환경 구성: 315. VHD 파일의 최소 크기파일 다운로드1
11196정성태5/4/201721946오류 유형: 384. Msvm_ImageManagementService WMI 객체를 사용할 때 오류 상황 정리 [1]
11195정성태5/3/201722725.NET Framework: 655. .NET Framework 4.7 릴리스
11194정성태5/3/201724249오류 유형: 383. net use 명령어로 네트워크 드라이브 연결 시 "System error 67 has occurred." 오류 발생
11193정성태5/3/201722190Windows: 141. 설치된 Windows로부터 설치 이미지를 만드는 방법
11192정성태5/2/201723577Windows: 140. unattended.xml/autounattend.xml 파일을 마련하는 방법
11191정성태5/2/201724411Windows: 139. Dell Venue 8 Pro 태블릿에 USB를 이용한 윈도우 운영체제 설치 방법
11190정성태5/2/201729820Windows: 138. Windows 운영체제의 ISO 설치 파일에 미리 Device driver를 준비하는 방법
11189정성태5/2/201721173Windows: 137. Windows 7 USB/DVD DOWNLOAD TOOL로 98%에서 실패하는 경우
11188정성태4/27/201723952VC++: 118. Win32 HANDLE 자료형의 이모저모 [2]
11187정성태4/26/201724873개발 환경 구성: 314. C# - PowerPoint 확장 Add-in 만드는 방법 [1]파일 다운로드1
11186정성태4/24/201722812VS.NET IDE: 117. Visual Studio 확장(VSIX)을 이용해 사용자 매크로를 추가하는 방법 [1]파일 다운로드1
11185정성태4/22/201720421VS.NET IDE: 116. Visual Studio 확장(VSIX)을 이용해 사용자 메뉴 추가하는 방법 (2) - 동적 메뉴 구성파일 다운로드1
11184정성태4/21/201722089VS.NET IDE: 115. Visual Studio 확장(VSIX)을 이용해 사용자 메뉴 추가하는 방법파일 다운로드1
... 106  107  108  109  [110]  111  112  113  114  115  116  117  118  119  120  ...