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

비밀번호

댓글 작성자
 




[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
13971정성태7/17/2025366닷넷: 2343. C# 14 - (2) 속성 구문에서 문맥 키워드로 추가되는 field 예약어파일 다운로드1
13970정성태7/17/2025398닷넷: 2342. C# 14 - (1) (예약)
13969정성태7/17/2025370닷넷: 2341. snap으로 설치한 .NET 리눅스 실행 환경
13968정성태7/16/2025373오류 유형: 969. lddtree - TypeError: 'type' object is not subscriptable
13967정성태7/16/2025402오류 유형: 968. snap으로 설치한 "dotnet run" 실행 시 "undefined symbol: _dl_audit_symbind_alt, version GLIBC_PRIVATE" 오류
13966정성태7/15/2025594디버깅 기술: 223. WinDbg - .kframes 명령어
13965정성태7/11/2025957오류 유형: 967. 디버깅 모드로 실행 시 "Could not find file 'C:\Program Files\IIS Express\Oracle.DataAccess.Common.Configuration.Section.xsd'" 예외
13964정성태7/10/20251507닷넷: 2340. C# - Win32 Multimedia Timer 주기파일 다운로드1
13963정성태7/8/20251118VS.NET IDE: 202. Visual Studio 2022 + Copilot 기본 사용법
13962정성태7/7/20251192스크립트: 79. 파이썬 - onnxruntime_genai에서 지원하지 않는 모델 사용
13961정성태7/5/20251109디버깅 기술: 222. WinDbg 분석 사례 - IISreset 시점에 w3wp.exe의 crash 발생
13960정성태7/3/20251201개발 환경 구성: 752. ProcDump - C/C++ 예외 코드 필터를 지정한 덤프 생성 [2]
13959정성태6/25/20251375오류 유형: 966. Ubuntu - ping: connect: Network is unreachable
13958정성태6/21/20251820닷넷: 2339. C# - Phi-4-multimodal 모델의 GPU 가속 방법 (ORT 사용)파일 다운로드1
13957정성태6/20/20251569닷넷: 2338. C# / Foundry Local - Phi-4-multimodal 모델을 사용하는 방법 [1]
13956정성태6/19/20251708개발 환경 구성: 751. Triton Inference Server의 Python Backend 프로세스
13955정성태6/18/20251839오류 유형: 965. Hugging Face 모델 다운로드 시 "requests.exceptions.HTTPError: 401 Client Error: Unauthorized for url: ..." 오류
13954정성태6/18/20251681닷넷: 2337. C# - Hugging Face에 공개된 LLM 모델을 Foundry Local에서 사용하는 방법파일 다운로드1
13953정성태6/16/20251480스크립트: 78. 파이썬 - 소스 코드의 파일 경로를 지정한 모듈 로드
13952정성태6/15/20251917닷넷: 2336. C# - IValueTaskSource로 인해 주의가 필요한 ValueTask 호출파일 다운로드1
13951정성태6/15/20251741오류 유형: 964. Outlook - 일정이 "You cannot make changes to contents of this read-only folder." 오류 메시지로 삭제가 안 되는 경우
13950정성태6/12/20252482닷넷: 2335. C# - 간단하게 구현해 보는 IValueTaskSource 예제파일 다운로드1
13949정성태6/11/20252418오류 유형: 963. SignTool - "Error: SignerSign() failed." (-2146869243/0x80096005)
13948정성태6/10/20251790오류 유형: 962. 파이썬 - Linux 환경 + TCP 서버 소켓을 사용하는 프로세스 종료 후 재실행하는 경우 "OSError: [Errno 98] Address already in use" 오류 발생
13947정성태6/9/20252413개발 환경 구성: 750. 파이썬 - Azure App Service에 응용 프로그램 배포 후의 환경
[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...