Microsoft MVP성태의 닷넷 이야기
.NET Framework: 590. C# - 모든 경우의 수를 조합하는 코드 (2) [링크 복사], [링크+제목 복사],
조회: 27642
글쓴 사람
정성태 (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

비밀번호

댓글 작성자
 




... 76  77  78  79  [80]  81  82  83  84  85  86  87  88  89  90  ...
NoWriterDateCnt.TitleFile(s)
12028정성태9/26/201924382.NET Framework: 863. C# - Thread.Suspend 호출 시 응용 프로그램 hang 현상을 해결하기 위한 시도파일 다운로드1
12027정성태9/26/201917263오류 유형: 568. Consider app.config remapping of assembly "..." from Version "..." [...] to Version "..." [...] to solve conflict and get rid of warning.
12026정성태9/26/201925051.NET Framework: 862. C# - Active Directory의 LDAP 경로 및 정보 조회
12025정성태9/25/201923414제니퍼 .NET: 28. APM 솔루션 제니퍼, PHP, .NET 무료 사용 프로모션 2019 및 적용 사례 (8) [1]
12024정성태9/20/201925234.NET Framework: 861. HttpClient와 HttpClientHandler의 관계 [2]
12023정성태9/18/201925908.NET Framework: 860. ServicePointManager.DefaultConnectionLimit와 HttpClient의 관계파일 다운로드1
12022정성태9/12/201928536개발 환경 구성: 458. C# 8.0 (Preview) 신규 문법을 위한 개발 환경 구성 [3]
12021정성태9/12/201945642도서: 시작하세요! C# 8.0 프로그래밍 [4]
12020정성태9/11/201928153VC++: 134. SYSTEMTIME 값 기준으로 특정 시간이 지났는지를 판단하는 함수
12019정성태9/11/201921964Linux: 23. .NET Core + 리눅스 환경에서 Environment.CurrentDirectory 접근 시 주의 사항
12018정성태9/11/201921120오류 유형: 567. IIS - Unrecognized attribute 'targetFramework'. Note that attribute names are case-sensitive. (D:\lowSite4\web.config line 11)
12017정성태9/11/201925199오류 유형: 566. 비주얼 스튜디오 - Failed to register URL "http://localhost:6879/" for site "..." application "/". Error description: Access is denied. (0x80070005)
12016정성태9/5/201923587오류 유형: 565. git fetch - warning: 'C:\ProgramData/Git/config' has a dubious owner: '(unknown)'.
12015정성태9/3/201931116개발 환경 구성: 457. 윈도우 응용 프로그램의 Socket 연결 시 time-out 시간 제어
12014정성태9/3/201924127개발 환경 구성: 456. 명령행에서 AWS, Azure 등의 원격 저장소에 파일 관리하는 방법 - cyberduck/duck 소개
12013정성태8/28/201927516개발 환경 구성: 455. 윈도우에서 (테스트) 인증서 파일 만드는 방법 [3]
12012정성태8/28/201932254.NET Framework: 859. C# - HttpListener를 이용한 HTTPS 통신 방법
12011정성태8/27/201931770사물인터넷: 57. C# - Rapsberry Pi Zero W와 PC 간 Bluetooth 통신 예제 코드파일 다운로드1
12010정성태8/27/201923718VS.NET IDE: 138. VSIX - DTE.ItemOperations.NewFile 메서드에서 템플릿 이름을 다국어로 설정하는 방법
12009정성태8/26/201925334.NET Framework: 858. C#/Windows - Clipboard(Ctrl+C, Ctrl+V)가 동작하지 않는다면?파일 다운로드1
12008정성태8/26/201925060.NET Framework: 857. UWP 앱에서 SQL Server 데이터베이스 연결 방법
12007정성태8/24/201923147.NET Framework: 856. .NET Framework 버전을 올렸을 때 오류가 발생할 수 있는 상황
12006정성태8/23/201926478디버깅 기술: 129. guidgen - Encountered an improper argument. 오류 해결 방법 (및 windbg 분석) [1]
12005정성태8/13/201923897.NET Framework: 855. 닷넷 (및 VM 계열 언어) 코드의 성능 측정 시 주의할 점 [2]파일 다운로드1
12004정성태8/12/201931989.NET Framework: 854. C# - 32feet.NET을 이용한 PC 간 Bluetooth 통신 예제 코드 [14]
12003정성태8/12/201924144오류 유형: 564. Visual C++ 컴파일 오류 - fatal error C1090: PDB API call failed, error code '3'
... 76  77  78  79  [80]  81  82  83  84  85  86  87  88  89  90  ...