[Algorithm] - 순열, 조합, 부분집합(Permutation, Combination, Subset)

개요알고리즘 문제들을 풀다보면 심심찮게 완전탐색을 진행하며 순열, 조합, 부분집합(순조부) 로직을 사용해야하는 상황이 나오는데, 매번 정확하게 생각이 안나서 이번 기회에 확실하게 정리해보고자 한다. SSAFY에서 배울 당시 기본 순열, 조합, 부분집합에 대해서는 보통 재귀 + 백트래킹 으로 구현하게 되며 각각의 매개변수는 순열 → 매개변수 1개 (depth)조합 → 매개변수 2개 (start, depth)부분집합 → 매개변수 1개 (index)로 구현한다고 기억한다. 따라서 가장 기본적인 순열, 조합, 부분집합에 대해 코드를 작성해보며 정리하고자 한다.순열(Permutation)순열: 서로다른 것들 중 몇개를 뽑아서 한줄로 나열하는 것 (nPr) 순열로 접근할 수 있는 문제 중에 유명한 문제로는 외판원..

• format_list_bulleted 알고리즘
• · 2026. 3. 14.
• textsms

[Programmers] - 2020 카카오 인턴십 / 수식 최대화 (JAVA)

[Programmers] - 2020 카카오 인턴십 / 수식 최대화 (JAVA)[Programmers] - 2020 카카오 인턴십 / 수식 최대화 (JAVA)1. 문제 접근해당 문제는 `+`, `-`, `*` 연산자와 숫자들로 이루어진 문자열이 주어졌을 때, 연산의 결과(절대값)가 최대가 되도록하는 연산자 간의 우선순위를 구한 뒤, 해당 연산의 결과를 반환하면 된다. 예를 들어 문제의 예시로 나온 `"100-200*300-500+20"`문자열이 주어졌을 때, `*` > `+` > `-` 로 연산자 우선순위를 정했을 때 연산의 결과가 |-60420|으로 최대가 되며 60420를 반환하면 된다. 문제를 크게 보면, 두개의 작은 문제로 나누어 볼 수 있다. 연산자 간의 우선순위 결정우선순위에 따른 연산먼저 연..

• format_list_bulleted 알고리즘
• · 2026. 3. 7.
• textsms

[Programmers] - 더 맵게 (JAVA)

[Programmers] - 더 맵게 (JAVA)[Programmers] - 더 맵게 (JAVA)1. 문제 접근해당 문제는 음식의 스코빌지수가 적힌 배열이 주어졌을 때, 음식을 주어진 규칙에 따라 섞은 뒤 모든 음식의 스코빌 지수가 `K`이상이 되도록 할 때 섞는 횟수를 반환하면되는 간단한 문제다. 음식을 섞는 공식은 아래와 같다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 따라서 주어진 스코빌지수 배열에서 순차적으로 가장 맵지 않은(스코빌지수가 가장 낮은) 음식을 2개씩 꺼내가며 확인하면 되는데, 주어지는 스코빌 지수 배열의 길이는 1,000,000으로 완전탐색으로 접근하면 시간초과가 발생한다. 따라서 Min Heap 자료구조..

• format_list_bulleted 알고리즘
• · 2026. 3. 4.
• textsms

[Programmers] - 큰 수 만들기 (JAVA)

[Programmers] - 큰 수 만들기 (JAVA)[Programmers] - 큰 수 만들기 (JAVA)1. 문제 접근해당 문제는 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하면된다. 처음 문제를 접근하였을 때는 이중 for문을 최적화하여 풀고자하였다. number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. 위 조건에 따라 완전 탐색을 진행할 수 없다고 판단하여, 수학적으로 `answer`배열의 검사 위치를 최적화하여 풀고자하였다. 주어진 예시인 "4177252841"를 바탕으로 `answer` 배열의 변화를 간략하게 살펴보면 초기상태 ------ `chkStartIdx = 0` / `currNum = 4` 4----- `chkStartIdx = 0` / `..

• format_list_bulleted 알고리즘
• · 2026. 3. 4.
• textsms

[Programmers] - 월간 코드 챌린지 시즌1 / 이진 변환 반복하기 (JAVA)

[Programmers] - 월간 코드 챌린지 시즌1 / 이진 변환 반복하기 (JAVA)[Programmers] - 월간 코드 챌린지 시즌1 / 이진 변환 반복하기 (JAVA)1. 문제 접근해당 문제는 이진수 형태의 문자열이 주어졌을 때, 문자열이 "1"이 될 때까지 정의한 연산의 횟수와 해당 연산 진행도중 제거된 "0"의 수를 1차원 배열로 반환하면 되는 간단한 문제다. 먼저 주어진 연산은 다음과 같다. x의 모든 0을 제거x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 변환따라서 주어진 순서대로 연산을 진행하면 쉽게 풀 수 있다. 첫번째 연산인 x의 모든 0을 제거하는 연산의 경우는 `replace()`연산을 통해 한번에 문자를 변환한다. s의 길이는 1 이상 150,000 이하이..

• format_list_bulleted 알고리즘
• · 2026. 2. 27.
• textsms

[Programmers] - 혼자 놀기의 달인 (JAVA)

[Programmers] - 혼자 놀기의 달인 (JAVA)[Programmers] - 혼자 놀기의 달인 (JAVA)1. 문제 접근해당 문제는 정수형 `cards` 배열이 주어졌을 때, 카드 수가 최대가 되는 그룹 2개를 찾은 후 두 그룹의 카드 수를 곱한 값을 반환하면된다. 임의의 상자(`cards[idx]`)를 하나 선택한 뒤, 해당 값의 위치의 있는 또 다른 상자(`cards[cards[idx]]`)를 열고 반복하며 하나의 카드 그룹을 구성하게되는데, 열어야 하는 상자가 이미 열려있을 때까지 반복한다. 해당 문제의 흐름에서 하나의 상자가 다른 상자를 탐색하게 한다는 것을 바탕으로 그래프 탐색을 사용하여 접근해야겠다는 생각을 하였다. cards에는 중복되는 원소가 존재하지 않습니다 위 조건을 통해 모든..

• format_list_bulleted 알고리즘
• · 2026. 2. 26.
• textsms

[Programmers] - 월간 코드 챌린지 시즌2 / 괄호 회전하기 (JAVA)

[Programmers] - 월간 코드 챌린지 시즌2 / 괄호 회전하기 (JAVA)[Programmers] - 월간 코드 챌린지 시즌2 / 괄호 회전하기 (JAVA)1. 문제 접근해당 문제는 괄호(`{`, `}`, `(`, `)`, `[`, `]`)로만 이루어진 문자열이 주어졌을 때, 문자열을 왼쪽으로 shift 시키며 올바른 괄호 문자열이 몇번 발생하는지 count하면 된다. 여기서 올바른 괄호문자열이란, 모든 여는괄호(`{`, `(`, `[`)와 닫는 괄호 (`}`, `)`, `]`)가 쌍이 맞는 경우를 말한다. 예를 들어 `()[{}]` 문자열은 모든 괄호들이 쌍을 이루므로 올바른 괄호 문자열이다. 하지만, `)[{}](` 문자열은 괄호들이 쌍을 이루고 있지 않으므로 올바르지 않은 괄호 문자열이다...

• format_list_bulleted 알고리즘
• · 2026. 2. 24.
• textsms

[Programmers] - 월간 코드 챌린지 시즌2 / 2개 이하로 다른 비트 (JAVA)

[Programmers] - 월간 코드 챌린지 시즌2 / 2개 이하로 다른 비트 (JAVA)[Programmers] - 월간 코드 챌린지 시즌2 / 2개 이하로 다른 비트 (JAVA)1. 문제 접근해당 문제는 `long` 자료형의 변수가 주어지면, 해당 수보다 큰 수 중 비트값이 2개 이하로 다른 수를 반환하면 된다. 처음 문제를 접근할 때, `numbers`의 변수 하나씩 순회, +1씩 증가시켜가며 완전 탐색 방식으로 접근하였다. 완전 탐색 방식은 주어진 수, 확인하고자 하는 수(+ 1, 2, 3 ...)를 1차원 `int`형 배열로 변환한 뒤, `cntDiff`함수를 통해 비교하였다. while(cntDiff(toBitString(chkNum), toBitString(numbers[idx])) > 2..

• format_list_bulleted 알고리즘
• · 2026. 2. 23.
• textsms

[Programmers] - 월간 코드 챌린지 시즌3 / n^2 배열 자르기 (JAVA)

[Programmers] - 월간 코드 챌린지 시즌3 / n^2 배열 자르기 (JAVA)[Programmers] - 월간 코드 챌린지 시즌3 / n^2 배열 자르기 (JAVA)1. 문제 접근해당 문제는 정수 `n`, `left`, `right`가 주어지고 규칙에 따라 만들어지는 `n`x`n` 행렬에 대해 일차원 배열로 바꾼 뒤, `left` ~ `right`까지 slice한 배열을 반환하면 된다. 행렬이 만들어지는 규칙은 아래와 같이 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채우면 된다.(i = 1, 2, 3, ..., n) 처음 문제를 접근했을 떄는 `n`x`n` 행렬을 만들어서 직접 값을 채운 후, 배열을 반환하는 방식으로 구현하였다. int[][] matrix = new i..

• format_list_bulleted 알고리즘
• · 2026. 2. 18.
• textsms

[Programmers] - 연속 부분 수열 합의 개수 (JAVA)

[Programmers] - 연속 부분 수열 합의 개수 (JAVA)[Programmers] - 연속 부분 수열 합의 개수 (JAVA)1. 문제 접근해당 문제는 주어진 원형 수열에 대해 도출될 수 있는 연속 부분수열 합의 개수를 구하면 되는 간단한 문제다. 몇가지 고려할 사항이 있다면, 해당 수열은 원형 수열로 주어지므로 `front` 인덱스와 `rear` 인덱스의 대소가 뒤바뀔 수 있다는 점과 중복된 값을 제외하고 개수를 반환해야한다는 점이다. 먼저 중복을 제거하기 위해서는 간단히 `Set`을 사용하였으며, 부분수열의 합을 구한 뒤 `add`하여 중복을 제거하고, 집합의 size를 반환하도록하였다. 두번째 고려사항인 원형수열에 대해서는 idx = (idx + 1) % N;...// front, rear ..

• format_list_bulleted 알고리즘
• · 2026. 2. 16.
• textsms