알고리즘

📖 문제  알고리즘❓ 풀어내기❗️모든 경우의 수는 각 원소를 뽑는다 / 안 뽑는다로 나뉜다. 따라서 완전탐색을 통해 합이 S가 되는 모든 경우의 수를 탐색하고, 트리구조를 이루기 때문에 DFS 방식으로 풀 수 있다.예를 들어, 원소 {A, B, C} 라면,index = 0 일 때는 아무것도 선택하지 않았을 때, 부분수열 = {0} (공집합)index = 1 일 때는 이전 부분 수열에 A를 가졌냐 안 가졌냐로 나뉨. 부분수열 = {A}, {0}index = 2 일 때는 이전 부분 수열에 B를 가졌냐 안 가졌냐로 나뉨. 부분수열 = {AB}, {A}, {B}, {0}index = 3 일 때는 이전 부분 수열에 C를 가졌냐 안 가졌냐로 나뉨. 부분수열 = {ABC}, {AB}, {AC}, {BC}, {A},..

조합(Combination)이란?조합은 주어진 집합에서 특정 개수의 원소를 선택하는 방법을 의미한다. 순서에 상관없이 선택된 원소들로 구성된 집합을 조합이라고 한다. 예를 들어, 집합 {A, B, C, D, E}에서 3개의 원소를 선택하는 경우, 가능한 조합은 {A, B, C}, {A, B, D}, {A, B, E}, {A, C, D}, {A, C, E}, {A, D, E}, {B, C, D}, {B, C, E}, {B, D, E}, {C, D, E}이다.쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 3으로 고정되어 있다.) 조합을 고려해 볼 수 있겠다.  시간 복잡도조합 생성의 시간 복잡도는 O(C(C, R) 또는 O(N! / (R..

부분집합(Subset)이란?부분집합은 주어진 집합의 원소들 중 일부를 선택하여 형성된 집합을 말한다. 주어진 집합 S의 모든 가능한 부분집합을 구하는 것이 부분집합 문제이다. 예를 들어, 집합 S = {A, B, C}의 부분집합은 0(공집합), {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}와 같다.쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 따로 고정되어 있지 않은 모든 경우라면 부분집합을 고려해 볼 수 있겠다.  시간 복잡도부분집합을 생성하는 시간 복잡도는 O(2^N)이다. 이는 각 원소에 대해 두 가지 선택(포함 또는 미포함)이 가능하므로, 모든 가능한 부분집합을 생성하기 위해 2^N개의 경우를 탐색해야 함을 의미한다. 이로 인해..

순열이란?순열(Permutation)은 집합에서 일부 원소를 선택하여 순서를 고려해 나열하는 방법을 말한다. 선택된 원소들의 순서가 다르면 다른 순열이 된다. 예를 들어, 주어진 집합 {A, B, C}에서 2개를 선택하여 나열할 수 있는 순열은 AB, AC, BA, BC, CA, CB 등이 있다.쉽게 말해 순서가 바뀌면 연산(혹은 값)이 달라지고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 2로 고정되어 있다.) 순열을 고려해 볼 수 있겠다. 사용 사례문제 해결 : 원소들을 모든 가능한 방법을 나열해야 할 때 사용된다. 예를 들어, 순열을 이용하면 문제의 가능한 모든 경우의 수를 탐색하거나, 정렬된 순서대로 원소들을 나열하는 경우에 활용된다.암호 해독 : 암호 해독 문제에서 가능한 모..

투 포인터 알고리즘 (Two Pointer Algorithm)배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 '정렬되어 있을 때' 사용한다.투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다.또는 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가진다.해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있다. 투 포인터 수행 단계배열 또는 리스트의 시작 위치에 첫 번째 포인터와..

📖 문제 ☑️ 입출력 예제 알고리즘❓ 풀어내기❗️다른 풀이 코드들을 보면 나와는 다르게 푼 게 대부분이었다. 내가 작성한 코드는 그렇게 깔끔한 코드는 아니지만 정말 단순하게 풀 수 있다. 풀이는 다음과 같다.모든 크로아티아 알파벳을 각각의 새로운 변수에 대입해 준다. 그런 다음 입력받은 문자열을 이전에 크로아티아 알파벳으로 대입해 준 변수들로 하나씩 replace() 메서드를 사용하여 "a"로 대체해 준다. 이렇게 하고 나면 문자열은 a로만 이루어져 있을 것이고, 이 문자열의 길이가 답이 된다. 🧑🏻‍💻 풀이 코드import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner ..

📖 문제 ☑️ 입출력 예제 알고리즘❓ 풀어내기❗️각각의 말에 정해진 개수로 초기화를 해주고 입력받은 수를 빼주면 된다. 🧑🏻‍💻 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int king = 1;        in..

📖 문제 ☑️ 입출력 예제 알고리즘❓ 풀어내기❗️StringBuffer 클래스의 reverse() 함수를 사용하면 쉽게 풀 수 있다. 🧑🏻‍💻 풀이 코드import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        String str = sc.next();        StringBuffer sb = new StringBuffer(str);        String reverse = sb.reverse().toString();        if (str.equals(reverse)) {            Sys..