저번 포스트에 이어 이번에는 조합과 중복조합에 대해 정리하고자 합니다. 조합 먼저 조합입니다. 조합은 "N개의 숫자 중에서 R개의 숫자를 순서 없이 뽑는 것"을 말합니다. 예를 들어 1, 2, 3 이라는 숫자가 있을 경우, 여기 2개의 숫자를 순서 없이 뽑으면 {1, 2}, {1, 3}, {2, 3} 을 얻을 수 있습니다. 순열이었다면 {2, 1}, {3, 1}, {3, 2} 등을 얻을 수 있었지만, 조합은 순열과 달리 순서 없이 뽑기 때문에 제외합니다. 그렇다면 이제 이를 구현해보기 위해 필요한 것들을 생각해보면, 조합을 구하고자 하는 데이터(숫자)와, 조합에 현재 숫자가 뽑혔는지를 알아야 합니다. 그리고 이를 구현하는 방법은 2가지가 있습니다. 백트래킹을 이용하거나, 재귀 호출을 이용할 수 있습니다...
알고리즘 문제를 풀면서, 매번 순열과 조합에 관한 문제가 나오면 헉!하고... 제대로 구현해보지 못한 것 같아, 이번 기회에 코드를 정리하고자 합니다. 순열 먼저 순열(permutation)입니다. 순열의 정의는 "서로 다른 N개에서 R개를 뽑아서 나열한 것"입니다. 또한 이로 인해 모든 순열의 시간복잡도는 O(n!)입니다. 그렇다면 순서가 상관있을까요? 맞습니다. 순서가 상관있습니다. 이 말의 의미는 다음과 같습니다. 숫자가 0, 1, 2로 총 3개가 있고, 이 중 2개를 뽑는 순열을 생각해봅시다. 순열은 순서가 상관있기 때문에, 즉 순서를 고려하기에, 같은 숫자를 뽑더라도 순서가 다르다면 다른 것입니다. 그렇다면 다음과 같은 순열을 얻을 수 있을 것입니다. {0, 1}, {0, 2}, {1, 0}, ..
하반기 코딩테스트가 곧 몰아칩니다.. 스스로 해결한 문제도 있고, 그렇지 못한 문제도 있지만 모두가 이해할 수 있게끔 풀이하면서 복기할 목적으로 문제 풀이를 해보려 합니다. 레벨 순으로 가면서 풀었던 코드를 분석해보겠습니다. 1. 크레인 인형뽑기 게임 (Level 1) https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import java.util.*; class Solution { // 인형 담을 바구니 Stack basket = new Sta..
