심플하고 차분하게

|  자료구조란?

- 자료를 목적에 따라 효율적으로 관리하기 위한 구조이다.

- 데이터를 CRUD할 때 유용하다.

- 적절히 사용하면 속도를 높히고, 메모리 사용도 줄일 수 있다.

|  자료구조의 분류

* 선형 자료구조는 기차처럼 길쭉하게 하나의 몸으로 구성되어 있다.

* 자료구조를 직접 구현하여(=추상 자료형) 사용할 수도 있다.

|  선형 자료 구조

* queue, deque에서 poll을 사용하면 비어있는 공간일지라도 null을 반환한다. 그러나 remove를 사용하면 예외가 발생

  (offer / poll 보다는 add / remove 를 사용하는 것이 안정성면에서 더 좋다)

|  자바 컬렉션들의 시간 복잡도

1. List

2. Set

3. Map

4. Queue

[ 참조 ] 

스택, 큐

- https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque

데크

- https://hbase.tistory.com/128

- https://jee-young.tistory.com/31

해시테이블

- https://hee96-story.tistory.com/48

-https://velog.io/@roro/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94

- https://jtoday.tistory.com/73

자바 컬렉션의 시간 복잡도

- https://hbase.tistory.com/185

|  점화식과 재귀함수

✏️ 개념 정리

(1) 점화식 (Recurrence) : 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식

- ex. 피보나치 수열

- 1, 1, 2, 3, 5, 8, 13....

- F1 = F2 = 1, Fn+2 = Fn+1 + Fn

(2) 재귀함수 (Recursion) 

- 종료조건 + 자기 자신을 호출

🛎재귀함수 문제풀기_백준 17478 재귀함수가 뭔가요?

|  문제 

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.

매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.

중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.

떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.

JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.

|  입력

교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.

|  출력

출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다.

|  예제 입력

2

|  예제 출력

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
____"재귀함수가 뭔가요?"
____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.
____라고 답변하였지.
라고 답변하였지.

🔎 문제분석

- 재귀함수가 호출때마다 들여쓰기가 이루어졌다. 

- N을 -1하여, N이 0이 될 때 "재귀함수는 자기 자신을 호출하는~"을 답하는 걸 볼 수 있다.

- 답변이 모두 끝나면 추가로 "라고 답변하였지"가 들어갔다.

💻 코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void solution(int N, StringBuilder sb, String indent) {

        String ask = "\"재귀함수가 뭔가요?\"\n";

        String[] answer1 = {"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n" ,
                "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n" ,
                "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n"};

        String answer2 = "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";

        String closing = "라고 답변하였지.\n";

        //탈출문
        if (N == 0) {
            sb.append(indent);
            sb.append(ask);
            sb.append(indent);
            sb.append(answer2);
            sb.append(indent);
            sb.append(closing);
            return;
        }

        sb.append(indent);
        sb.append(ask);
        for (String s : answer1) {
            sb.append(indent);
            sb.append(s);
        }
        solution(N - 1, sb, indent + "____");
        sb.append(indent);
        sb.append(closing);

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        String indent = "";//들여쓰기 최초

        sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n");
        solution(N, sb, indent);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}

🛎점화식문제풀기 _   백준 13699_점화식

|  문제 

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

• t(0)=1
• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

|  입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

|  출력

첫째 줄에 t(n)을 출력한다.

|  예제 입력

25

|  예제 출력

4861946401452

🔎 문제분석

- F0 = 1

- F1 = (F0 * F0) = 1 * 1 = 1 

- F2 = (F0 * F1) + (F1 * F0)  = (1 * 1) + (1 * 1) = 1 (1 + 1) = 2                                                         

- F3 = (F0 * F2) + (F1 * F1) + (F2 * F0)  = (1 * 2) + (1 * 1) + (2*1) = 2 (1 + 1) + (1 * 1) = 5

- F4 = (F0 * F3) + (F1 * F2) + (F2 * F1) + (F3 * F0) =  (1 * 5) + (1 * 2) + (2 * 1) + (5 * 1) = 5 ( 1 + 1 ) + 2 ( 1 + 1 ) 

**재귀로 풀어보려다가 몇 시간을 썼다... 하아.. 

**결국 반복문으로 풀어보았다.

- 원리는 바깥 for문에서는 F0부터 Fn까지를 하나씩 호출하고, 안쪽에서는 점화식에 따라 F0에서 Fn의 값을 계산하여 넣어주는 방식이다.

- 점화식의 값을 넣어주는 tArr 배열의 크기는 n의 범위 (0~35)에 맞추어 총 36개를 지정해주었다.... 

💻 코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static long solution(int N) {

        long[] tArr = new long[36];

        for (int i = 0; i <= N; i++) {

            if (i == 0) {
                tArr[i] = 1;
                continue;
            }

            for (int j = 0; j < i; j++) {
                tArr[i] += tArr[j] * tArr[i - 1 - j];
            }
        }

        return tArr[N];
    }

    public static void main(String[] args) {
        //System.out.println(solution(3)); // 5
        //System.out.println(solution(25)); // 4861946401452
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        try {
            int N = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(solution(N)));
            bw.flush();
            bw.close();
        } catch (Exception e) {
            System.out.println("Error Occured!");
        }

    }
}

|  조합 (Combination)

✏️ 개념 정리

(1) 조합 : 서로 다른 N개의 수에서 R개를 뽑아 나열하는 경우의 수

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)

- nCr = n! / (n-r)!r! = nPr / r!  (단, 0 < r <= n)

(2) 중복 조합 : 순서 X, 중복 O

- nHr = n+r-1Cr

💻 구현하기

[ 조합 구현 _ 재귀 :  교환 없이 방문배열을 통해 출력하기 ]

✅  조합 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하지 않고 나열하는 것

✅  구현 방법

[입력]

서로 다른 n개의 수를 담은 배열(int[] arr)과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r=2),

방문위치를 알려줄 배열(int[] visited)을 인자로 받는다.

*알고리즘이 시작되면, 선택 가능 갯수(r)는 처음입력받은 수(r=2)이다.

*깊이는 선택하려는 숫자의 인덱스를 의미한다.

*조합 알고리즘에서는 순서를 고려하지 않기 때문에, r을 기준으로 depth를 조정한다.

[처리]

선택 가능 갯수(r)를 기준으로, depth를 하나씩 방문하며 r == 0 일때에 출력한다.

※ 그림으로 본 조합 알고리즘 모습

✅  구현 하기

void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
}

|  컴퓨터 구조

01. 컴퓨터의 큰 구조

- 컴퓨터는 크게 하드웨어와 소프트웨어로 나누어집니다. 

- 집에 있는 컴퓨터를 열어보면 그 안에 하드웨어를 볼 수 있는데,

   크게 1) CPU, 2) 메모리, 3) Storage, 4) Network, 5) IO 장치로 나누어져요.

- 소프트웨어에는 시스템 소프트웨어와 응용 소프트웨어가 있는데요,

  시스템 소프트웨어는 운영체제(OS) 나 장치 드라이버와 같이 사용자가 컴퓨터를 작동할 수 있게 하는 유틸리티를 말하며

  응용 소프트웨어(= Application software)는 오라클이나 게임과 같이 특정 문제나 업무를 처리하기 위한 목적으로 만들어진 소프트웨어를 말합니다.

02. 폰노이만 구조

- 컴퓨터의 구조는 다양한 방식으로 분류될 수 있는데, 폰노이만에 의해 그 구조가 깔끔하게 정리되었다고 합니다.

- 간략하게 요약하면, 폰노이만 구조는 1) CPU, 2) 메모리, 3) 프로그램 으로 이루어진다고 해요.

- 이 구조에 따르면 컴퓨터는 키보드와 같은 입력장치로부터 받아온 데이터를

   (1) CPU의 메모리를 통해 저장하는데, 

   (2) 레지스터에서는 변수와 같은 작은 데이터 및 중간처리과정에서의 데이터를 저장하고

        캐시에서는 자주 사용하는 데이터를 임시 저장해 빠르게 접근하며

        RAM(요즘엔 DRAM, DDP4)을 통해서는 전반적인 처리를 위한 데이터를 보관한다고 합니다.

   (3) 프로그램은 어떤 문제를 해결하기 위해 만들어진 명령문의 집합체를 의미하는 것으로, 앞서 말한 시스템 프로그램이나, 응용 프로그램이 이에 해당됩니다. 사용자는 프로그램을 통해 컴퓨터와 소통을 하는데요. 프로그램이 돌아가면서 사용자의 명령을 컴퓨터가 이해할 수 있게 0과 1로 변환하고 CPU의 연산장치(ALU)를 통해 명령을 처리합니다.

03. 비트(bit, 0과 1)와 비트논리연산(AND, OR, NOT)

- 폰노이만 구조에서 잠시 언급된 CPU의 연산장치(ALU)에는 마이크로 연산 곧,

   1) 논리연산을 수행하는 부분과 2) 산술연산을 수행하는 부분, 그리고 3) 시프트 연산을 수행하는 부분이 있습니다.

- 여기서 연산을 수행할 때에 "비트"라는 단위가 사용됩니다.

- 비트는 2진수 1과 0을 나타내는 것으로, 스위치를 키고 끄는 것과 같이 ON과 OFF를 의미해요.

- 이 2진수의 수에 대해 비트 논리 연산을 수행할 수 있는데, 그것이 바로 AND/OR/NOT 연산입니다. 

- 컴퓨터 내부 회로는 AND, OR, NOT을 토대로 다시 NAND, NOR, XOR...을 만들어내는데요. 

- 논리회로를 엮어내어 산술연산을 만들 수도 있습니다.

04. 비트 산술연산, 조합회로와 순차회로

- 앞에서 ALU에는 논리연산 외에도 산술연산을 수행한다고 이야기하였습니다. 그 중에서도 덧셈을 담담하는 것이 바로 아래의 '가산기'에요.

(1) 가산기(Adder)

- ALU에는 가산기라는 것이 있는데요. 논리회로를 조합해 반가산기 -올림을 제외한 한 자릿수 덧셈만 처리-를 만들고, 다시 추가으로 논리회로를 조합해 전가산기-올림까지 처리-를 만들면 제대로된 덧셈이 가능해집니다.

- 전가산기를 여러개를 묶으면 이젠 여러 자릿수를 계산할 수 있게 됩니다. 8개를 묶으면 8bit, 16개를 묶으면 16bit... 더 나아가서는 64bit의 자릿수를 처리할 수 있게 돼요.

(2) 발진기와 클럭

- 앞에서는 논리회로를 조합해서 만든 가산기(=덧셈기)를 말했다면, 이번엔 NOT을 만들어주는 발진기를 소개하려 합니다.

- 발진기(Oscilliator)는 전자회로를 통해 연속파의 교류신호를 발생하는 회로를 말하는데요. (말이 참 어렵다)

- 쉽게 말하면 0 -> 1 -> 0 -> 1.. 을 마치 매트로놈처럼 주기적으로 반복해서 만들어주는 녀석이라고 생각하면 됩니다.

- 다시, Oscilliator를 통해서 0이 들어오면 1을, 1이 들어오면 0을 반환하는 걸 하나의 사이클로 보는데요.

- 클럭(Clock)은 1초 동안 이 사이클이 움직이는 주파수를 말하는 것으로, 단위는 Hz로 표기됩니다.

- 클럭이 높을 수록 처리속도는 빨라지는데, 클럭을 높힌다고 다 놓은 것이 아닌 것이, 그만큼 발열량과 소비 전력이 커지는 단점이 있다고 합니다. 그래서 최근에는 클럭(클럭 - 비유 : 도로 제한 속도)을 높히기 보다는 멀티 코어(코어 - 비유 : 도로 차선) 또는 멀티 스레드를 통해 CPU 성능을 높이는 것을 추구한다고 해요.

(3) 플립플롭과 비트의 Write/Read

- 플립플롭(flip-flop)은 래치(latch)라고도 하며, NOR게이트를 조합해 만든 회로인데요, 최근에 스위치가 ON이었는지, OFF였는지를 알 수 있게 해주는 회로입니다.

- 결국 다시 말해, 플립플롭은 0 or 1 곧, 비트를 저장할 수 있는 회로를 말해요.

- 플립플롭의 종류는 R-S flip-flop, Level-triggered flip flop, D-type flip-flop, JK flip-flop 등 종류가 매우 다양하다고 합니다.

- 전원이 공급되는 한, 플립플롭은 상태의 변화를 위한 신호(클럭)이 발생할 때까지 현재 상태를 유지해요.

- 플립플롭을 여러개 묶으면 8bit latch를 만들수 있는데요, 8-to-1 selector와 3-to-8 decoder로 온전한 8 bit latch를 만들 수 있다고 합니다. 그리고 이 8bit latch가 우리가 말하는 RAM이라고 해요. RAM에서는 8-to-1 selector와 3-to-8 decoder를 통해 3개의 Address가 있으면 8개 중 하나의 비트를 선택해서 쓰거나 읽을 수 있다고 합니다.

- 이제 이 8 X 1 latch를 여러개 연결하게 되면 하나의 비트에서 여러개의 비트를 쓸 수 있는 m * n RAM array를 만들 수 있다고 해요. 그렇다면 64k RAM은 얼만의 데이터를 쓸 수 있을까요? 65536(2^16) x 8bits라고 합니다.

* 1 Megabytes = 1 Mega x 8 bits = 8 Megabits

(4) 누산기(Accumulator)와 레지스터

- 앞서 가산기에서 덧셈을 처리한다는 이야기를 하였고, 쭉쭉 내려와 RAM에서 특정 데이터를 저장하고 읽을 수 있다는 걸 이야기했어요. 이번에는 누산기에 대해 이야기를 할 건데요.

- 누산기는 산술 및 논리연산의 결과 또는 중간계산과정을 저장하는 레지스터를 말합니다.

- 구체적으로 들어가면 8-bit Adder와 8-bit Latch로 구성되어 있으며, Clear스위치가 눌리면 어떤 데이터든 기존 값을 삭제하고, Adder를 통해 덧셈이 이루어진다고 해요.

(5) Program Counter (PC) 

- Program Counter, 16-bit counter는 1씩 증가하는 조합논리회로를 말한다고 해요.

- 프로그램 카운터는 다음에 실행될 명령어가 들어갈 주기억장치의 주소를 기억하는 레지스터입니다.

* 인터럽트시 PC는 1, R = 0이 된다. 

* Set(Preset) : 101010 | 111111 = 111111,  Clear(Reset) : 101010 & 000000 = 000000 

05. 어셈블리어(저급 언어)와 고급언어. 

- 어셈블리어는 기계어와 일대일 대응이 되는 저급 언어로, 컴퓨터 구조에 따라 사용하는 기계어가 달라집니다. 컴퓨터의 CPU마다 지원하는 오퍼레이션의 타입과 갯수, 레지스터의 타입과 갯수, 저장 데이터 표현 형태도 다 다르기 때문에 컴퓨터 제조업체에 따라서 어셈블리어도 다를 수 밖에 없어요.

- 어셈블리어는 니모닉이라고 하는 일련의 숫자를 단어로 바꿔준 언어를 사용합니다. (ex. MOV, LOAD, ADD, h)

- 어셈블리어의 한계를 극복하기 위해 고급언어가 등장하게 되었는데요,

- 이 중에서도 컴파일 언어는 소스 코드를 어셈블리어에서 기계어로 변환하는 "컴파일링"을 통해 먼저 메모리에 기계어로 번역된 코드를 올려두고 실행을 하는 언어를 말합니다. 예를 들어, C언어가 있죠. (자바도 컴파일 언어라고도 하는데, 사실상 컴파일과 인터프리터가 섞인 형태입니다)

- 반면 인터프리터 언어는 사전의 컴파일링 없이, 소스 코드를 한 줄씩 실행하며, 컴파일링을 진행하고 변환 코드를 실행하는 언어를 말합니다. 예를 들어, javascript, SQL, python, Ruby, 스크래치 등이 있습니다.

06. 다시 폰노이만. CPU의 구조와 실행과정

- 다시 폰노이만 구조로 돌아오면, 컴퓨터는 아래와 같이 구성됩니다.

[1] CPU : Controller Unit(Program Counter, 주소) + ALU (가산기 + 논리연산 + 레지스터)

[2] Memory

[3] 프로그램

- CPU의 기본 구조

- CPU의 기본 실행 구조

* Instruction은 여기서 '명령어'라는 의미

- CPU의 명령어 구조 : opcode(사전 약속된 명령어) + operand(argument, 데이터)

[참조] 

- 마이크로 연산, https://devraphy.tistory.com/308?category=1014713 

- 레지스터 전송과 마이크로 연산 바로가기

- 클럭(Clock), https://soojong.tistory.com/entry/%ED%81%B4%EB%9F%ADClock

- 클럭과 코어와 스레드, 캐시메모리 https://library.gabia.com/contents/infrahosting/1227/

- 누산기 https://itpmw.tistory.com/578

🛎 2231 분해합

|  문제 

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

|  입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

|  출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

|  예제 입력

216

|  예제 출력

198

🔎 문제분석

어떤 수 N의 분해합을 구하는 거라면 쉬웠을 텐데, 분해합의 가장 작은 생성자(=곧, 어떤 수 N)를 찾는 문제라 난해했다.

(1) N의 생성자의 최대값은 N - 1이다.

주어진 분해합 값 N의 범위는 (1 ≤ N ≤ 1,000,000) 

==> 그렇다면 N의 생성자의 자릿수는 최대 6개 곧, 999,999가 된다. (생성자는 분해합 보다 적어도 1만큼 적을 것)

(2) N의 생성자의 최소치는 N - 54이다.

* M = N의 생성자

==> M의 각 자릿수의 최대치는 999,999이다.

==> N = 999,999 + (9 * 6)

==> (M의 각 자리수에 대한 합)의 최대치는 (9 * 6)이다.

==> M의 최소치는 곧, 54

(3) (1)~(2)를 종합해보았을 때, N의 생성자의 범위는 

⌨️ 코드

|  순열 (permutation)

✏️ 개념 정리

(1) 팩토리얼 : 서로다른 N개의 수를 일열로 나열하는 전체 경우의 수

- 1~n까지 모든 자연수의 곱 (n!) --- 단, 0!은 1이다.

- n! = n*(n-1)...*1

(2) 순열 : 서로 다른 N개의 수에서 R개를 뽑아 나열하되, 순서대로 나열하는 경우의 수 

- 서로 다른 n개 중 r개를 선택하는 경우의 수 (순서 O, 중복 X)

- nPr = n! / (n-r)! = n(n-1)(n-2)....(n-r+1) (단, 0<r<=n)

(3) 중복 순열 : 서로 다른 n개 중 r개를 선택하는 경우의 수 (순서 O, 중복 O)

- nㅠr = n의 r 승

(4) 원 순열 : 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수

- n!/n = (n-1)!

💻 구현하기

[ 순열 구현 1_ 재귀 : 깊이에 따른 순차 교환 ]

✅  순열 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하여 나열하는 것

✅  구현 방법

[입력]

서로 다른 n개의 수를 담은 배열과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r)를 인자로 받는다. 

*알고리즘이 시작되면, 깊이 인덱스(depth)는 0이다.

*깊이는 선택하려는 숫자의 인덱스를 의미한다.  

[처리]

현재 깊이(depth=0)와 깊이 인덱스부터(i=depth)~배열의 끝(i=n-1)까지 중 하나를 교환하고 깊이를 높혀줄 것이다. 

1. 현재 깊이 인덱스(depth=0)와 하나의 인덱스(i=depth=0)를 교환한다.

2. 깊이 인덱스를 하나 높혀준다.(depth=0+1=1)

2. 위의 1)~2) 과정을 반복한 뒤, 선택 가능 갯수를 초과할 때(depth == r) 탈출한다.

3. 탈출 후 더 낮은 깊이에서 정상교환이 이루어지도록 교환한 것을 재교환한다.

※ 그림으로 본 순열 알고리즘 모습

✅  구현 하기

void permutation(int[] arr, int depth, int n, int r) {

    if (depth == r) {
        for (int i = 0; i < r; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        return;
    }

    for (int i = depth; i < n; i++) {
        swap(arr, depth, i);
        permutation(arr, depth + 1, n, r);
        swap(arr, depth, i);
    }

}

public void swap(int[] arr, int a, int b) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

[ 순열 구현 2_ 재귀 :  교환 없이 추가배열을 통해 출력하기 ]

✅  순열 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하여 나열하는 것

✅  구현 방법

[입력]

서로 다른 n개의 수를 담은 배열(int[] arr)과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r),

방문위치를 알려줄 배열(int[] visited), 출력 배열(int[] out)을 인자로 받는다.

*알고리즘이 시작되면, 깊이 인덱스(depth)는 0이다.

*깊이는 선택하려는 숫자의 인덱스를 의미한다.  

[처리]

현재 깊이(depth=0)에서 배열의 첫번째(i=0)~배열의 끝(i=n-1)까지 중 방문하지 않았던 곳을 출력배열에 출력할 것이다.

1. 현재 깊이 인덱스(depth=0) : 방문하지 않았던 곳(i=0)을 체크 후, 출력배열에 출력한다.(out[depth] = arr[i])

2. 깊이 인덱스를 하나 높혀준다.(depth=0+1=1)

2. 위의 1)~2) 과정을 반복한 뒤, 선택 가능 갯수를 초과할 때(depth == r) 탈출한다.

3. 탈출 후 더 낮은 깊이에서 정상출력이 가능하도록 방문했던 곳을 미방문상태(false)로 변경한다.

※ 그림으로 본 순열 알고리즘 모습

✅  구현 하기

void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {

    if (depth == r) {
        System.out.println(Arrays.toString(out));
        return;
    }

    for (int i = depth; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            out[depth] = arr[i];
            permutation(arr, depth + 1, n, r, visited, out);
            visited[i] = false;
        }
    }

}

|  집합(Set)

✏️ 개념 정리 

특정 조건에 맞는 원소들의 모임

- 특징

중복되지 않은 수들을 한 곳에 모아놓는 것으로, 자바에서는 Set을 사용해 중복데이터를 거를 수 있다.

- 종류

💻 구현하기

[ HashSet 구현해보기 ]

|  경우의 수

✏️ 개념 정리 

어떤 사건에서 일어날 수 있는 경우의 가짓수 : n(A)

(1) 약수 

- 6의 약수는 1,2,3,6

- N의 약수를 코드로 구할 때 루프를 사용한다면 N/2만큼만 루프를 돌려 나누어떨어지는 수를 구하고, 마지막으로 자기 자신을 더해주면 된다 (why? 2로 나누었을 때 절반까지만 나눠질것)

(2) 최대공약수

- A와 B의 약수 중 가장 큰 공통된 수

(3) 최소공배수 

- A와 B의 배수 중 가장 작은 공통된 수

- 최소공배수 = A x B / A와 B의 최대공약수 

💻 구현하기 

[ 경우의 수 - 합의 법칙과 곱의 법칙 ]

[ 약수, 최대공약수, 최소공배수 구하기 ]

|  개념

기수란? 수를 나타내는 데 기초가 되는 수. 

- 10진법에서는 0~9까지의 정수를 말하며, 2진법에서는 0~1까지 정수를 말한다.

|  기수 변환을 수행하는 프로그램

package _00_두잇;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class _01_기수변환 {
    //정수값 x를 r로 변환하여 배열 d에 아랫자리부터 넣어두고 자릿수를 반환한다.
	static int convert(int x, int r, char[] d) {
		int digits = 0;
		String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		
		//배열 안에 나눈 나머지를 하나씩 넣는다 
		while (x != 0) {
		  d[digits++] = dchar.charAt(x % r);
		  x = x / r;
		} 
		
		//배열의 역순이 변환한 진수값이다.
		for (int i = 0; i < digits/2; i++) {
			char tmp = d[i];
			d[i] = d[digits-1-i];
			d[digits-1-i] = tmp;
		}
		
		//변환한 수의 자릿수
		return digits;
		
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		//변환하려는 수
		int num;
		//기수
		int jin;
		//변환한 수의 자릿수
		int digits;
		//변환 후 각 자리의 숫자를 넣어주는 문자 배열
		char[] cvArr = new char[32];
		
		System.out.print("변환하려는 수 : ");
		
		num = Integer.parseInt(reader.readLine());
		
		System.out.print("자릿수(2~36) : ");
		
		jin = Integer.parseInt(reader.readLine());
		
		digits = convert(num, jin, cvArr);
		
		System.out.print(jin+"진수로 ");
		for (int i = 0; i < digits; i++) {
			System.out.print(cvArr[i]);
		}
		System.out.print("입니다.\n");
		
	}
}

>> 결과

변환하려는 수 : 35
자릿수(2~36) : 2
2진수로 100011입니다.

[출처]

[자료구조와 함께 배우는 알고리즘 입문], BohYoh Shibata지음