제로베이스 백엔드 부트캠프 2주차 정리 - Chapter01. 기초수학

2주차가 끝났다.

이번 주차 강의는 기초수학과 자료구조/알고리즘이었는데 기초가 정말 부족했나보다...

개념은 알아도 그것을 코드로 구현하는게 좀 까다로웠다. 특히 알고리즘은 자바에서 제공하는 인터페이스나 클래스 외에도 배열로 구현해보는 실습이 있었는데 복잡하고 어렵긴 했지만 구조를 잘 알 수 있게 된 것 같다.

 

이해하고 넘기느라 시간이 정말 많이 걸려서 주말 전에 다 강의 끝내고 주말에 복습하며 블로그 쓰려했는데 절대 안 됐다.

다행히 이번 3주차에도 같은 강의 복습시간이 있어서 다행이다. 얼른 복습하면서 익혀야지 ㅎㅎ

 

7/10

자바 프로그래밍 -> 수학(중간다리) -> 자료구조/알고리즘

수학을 정말 싫어해서 문과갔다가 결국 공대를 오게됐는데...

더이상 외면할 수 없게 되었다.

 

이번 파트에서 배울 것은 집합 경우의 수, 순열/조합, 점화식과 재귀함수, 지수와로그, 알고리즘 복잡도

 

* 재귀함수를 규칙 만들어서 점화식으로 구현

* 공간복잡도 보다는 시간복잡도가 중요

 

<02. 집합(Set)> : 특정조건에 맞는 원소들의 모임

집합 표현 방법으로는 원소나열법, 조건제시법,벤다이어그램이 있다.

교집합 합집합 차집합 여집합

 

자바에서 집합을 사용할 땐 HashSet 사용. (Set : 순서가 없고 데이터 중복을 허용하지 않는 자료구조)

- 집합연산 :

  set1.addAll(set2) : 합집합

  set1.removeAll(set2) : 차집합

  set1.retainAll(set2) : 교집합

 

- ArrayList로 직접 구현해보기 실습

  우와 역시 두 번째 하니까 쉽군

 

<03. 경우의 수>

사건 A가 일어날 경우의 수 n(A)

합의 법칙 : 사건 A 또는 사건 B가 일어날 경우의 수 n(AuB) = n(A) + n(B) - n(A∩B)

곱의 법칙 : 사건 A와 사건 B가 동시에 일어날 경우의 수 n(AxB)

 

<04. 순열(Permutation)> 

-팩토리얼 : 1~n 모든 자연수의 곱 n!

-순열 : 순서를 정해서 나열

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

  ex) 5명을 3줄로 세우는 방법, 서로다른 4명 중 반장, 부반장 뽑는 방법

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

-중복순열 : 서로다른 n개 중 r개 선택 (순서 O, 중복 O) n^r

-원순열 : 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수 n! /n = (n-1)(n-2)....1 == (n-1)!

  ex) 원 모양의 테이블에 3명을 앉히는 경우

 

실습이 좀 어려웠다. permutation 메소드를 작성해서 1234에서 서로 다른 3자리 자연수 만들기 

두 번째 방법이 좀 더 직관적. 근데 복잡하긴 매한가지다

void permutation(int arr[], int depth, int visited[], int out[], int n, int r){
	if(depth == r){
    	for(int i = 0; i < r;i++){
        	System.out.print(out[i]+" ");
        }
        break;
    }
    
    for(int i = depth; i < n ; i++){
    	if(visited[i] != true){//방문한 적이 없으면
        	visited = true;
            out[i] = arr[i];
            permutation(arr, depth + 1, visited, out, n, r);
            visited = false;
        }
    }
}

 

<05. 조합(Combination)> 

-조합 : 서로다른 n개중 r개 선택 (순서 X, 중복 X)

  ex) 서로다른 4명 중 주번 2명 뽑기  4Cr

  nCr = n! / (n-r)!r! = nPr / r!

 

-중복조합 : 서로다른 n개 중 r개 선택 (순서 X, 중복 O)

  ex) 후보 2명, 유권자 3명일 때 무기명 투표 방법 2H3

nHr = n+r-1Cr

 

<06. 점화식과 재귀함수> 

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

 ex) 피보나치 수열 : 1,1,2,3,5,8,13,... F1 = F2 = 1 , Fn+2 = Fn + Fn+1

 

- 재귀함수 : 어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식 - > 이전에 점화식으로 나타낸 것들을 편리하게 표현 가능

  * 자기자신을 계속 호출하므로 탈출하기 위한 종료조건이 필수 !

 

<07. 지수와 로그> 

- 제곱 : 같은 수를 두번 곱합, 거듭제곱 : 같은 수를 거듭하여 곱합.

- 제곱근 : (== root, √) a를 제곱하여 b가 될 때, a를 b의 제곱근이라고 함.

- 로그 : logab a가 b가 되기 위해 제곱해야하는 수 -> 로그의 개념을 처음 알았다 ...

    log2 4 : 2가 4가 되기 위해 2번 제곱하면 된다 ! 와우

Math.pow(16, 0.1/0.2) -> 16의 1/2제곱 == 16의 제곱근

 

<08. 알고리즘 복잡도> 

- 복잡도 : 알고리즘 성능을 나타내는 척도.

시간복잡도 : 알고리즘의 필요연산 횟수

공간복잡도 : 알고리즘의 필요 메모리

 * 시간복잡도와 공간복잡도는 trade-off의 관계 (서로 상충.)

 

- 시간 복잡도 : 빅오 표기법을 통해 나타냄

O(1) < O(logn) < O(n) < O(NlogN) < O(n^2) < O(2^n)

상수     로그        선형      로그선형     이차       지수

 

- 공간 복잡도 : 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량

  빅오 표기법을 통해 나타냄

  일반적으로 메모리 사용량 기준은 MB 단위

  int a[] = new int[1000]; //4KB

  int a[][] = new int[1000][1000]; //4MB

 

<실습>

- 시간복잡도

O(1) : Ideal 케이스. 많은 값들이 있어도 특정위치의 값을 인덱싱해서 출력하는 거

O(logN) : for문에서 16개의 데이터가 있다고 할 때 i가 2씩 증가하며 출력을 한다면 8번 출력연산을 하게되니까 log16 = 8 입력값 N에 대해 logN만큼의 연산을 수행함.

O(N) : for(int i=0; i< 2; i++) 입력한 N만큼 연산 수행

O(NlogN) : 2중 for문에서

for(int i = 0;i <2;i++)  //바깥 for문은 N번만큼

{ for(int j = 1; j <= 16; j*=2) {  //안 for문은 logN만

   System.out.println(" ~~"); }}

O(N^2) : N번만큼 이뤄지는 for문이 2중으로 있을 때

O(2^N) : 피보나치 수열 같이 입력값에 대해서 2의 n제곱만큼 늘어나는 연산

 

- 공간복잡도

O(N) : 팩토리얼같은 경우 시간복잡도도 O(N)인데 재귀함수로 호출하면 N번만큼 메모리에 함수 호출스택이 쌓임

O(1) : 팩토리얼을 for문으로 구현하면 n에 상관없이 4byte int result 메모리 하나만 가지고 풀 수가 있게됨.

           시간복잡도는 O(N)

팩토리얼을 재귀함수 / for문으로 풀면 각각 시간공간복잡도는 O(N) O(N) / O(N) O(1) 이라 for문으로 푸는게 더 좋아보일 수 있지만 이정도 공간복잡도는 유의미한게 아니라 편리한 방법으로 풀면 됨.

 

기초수학 복습은 끝 !