Dev Diary.

Recursive Thinking 

순환적으로 사고하기!

Recursion은 수학 함수 계산에만 유용할까?

수학함수뿐 아니라 다른 많은 문제들을 

recursion으로 해결할 수 있다.

for문 대신에 recursion을 통해 해결 할 수도 있다.

문자열의 길이 계산

라이브러리 함수를 써도 되지만 

라이브러리 함수는 어떻게 동작할까?

앞에서부터 문자하나하나씩 세면 된다.

이것이 절차적인 프로그램이라고도 이야기할 수 있다.

for문 같은 반복문을 통해 해결 할 수 있지만

문자열의 길이가 0이라면 리턴하고(base case)

그렇지 않다면 

원래 문자열에서 첫번째 문자열을 제거한 그 문자열의 길이를 제거하고

1을 더하면 된다.

public static int length(String str){
	if(str.eqauls(""))
    	return 0;
    else
    	return 1+length(str.substring(1));
}

이렇게 구현할 수 있다.

문자열의 프린트

public static void printChars(String str){
	if(str.length()==0)
    	return;
    else{
    	System.out.print(str.charAt(0));
        printChars(str.substring(1));
       	}
}

위와 같은 방식으로 프린트도 할 수 있다.

문자열의 뒤집어 프린트

public static void printCharsReverse(String str) {
	if(str.length()==0)
    	return;
    else{
    	printCharsReverse(str.substring(1));
        System.out.print(str.charAt(0));
        }
}

else문 안에서 순서만 바꾸어 주면 가능한 문제이다.

2진수로 변환하여 출력

public void printTnBinary(int n){
	if(n<2)
    	System.out.print(n);
    else{
    	printInBinary(n/2);
        System.out.print(n%2);
        }
}

음이 아닌 정수 n을 이진수로 변환하여 인쇄한다.

n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후

n을 2로 나눈 나머지를 인쇄한다.

배열의 합 구하기

public static int sum(int n, int [] data){
	if(n<=0)
    	return 0;
    else
    	return sum(n-1, data) + data[n-1];
}

data[0]에서 data[n-1]까지의 합을 구하여 반환한다.

데이터파일로 부터 n개의 정수 읽어오기

public void readFrom(int n, int [] data, Scanner in){
	if(n==0)
    	return;
    else{
    	readFrom(n-1,data,in);
        data[n-1] = in.nextInt();
        }
}

일반적으로 모든 순환함수는 반복문으로 변경 가능하다.

그 역도 성립한다. 즉 모든 반복문은 recursion으로 표현 가능하다.

순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.

하지만 함수 호출에 따른 오버헤드가 있다.

Recursion은 순환이라고 부르기도하고 재귀함수라고 부르기도 한다.

자기 자신을 호출하는 함수 func()이다.

void func()

{

    func();

}

어떤 함수가 자기 자신을 호출하면 어떻게 될까?

public static void func() {
	System.out.println("Hello")
    func();
 }

무한 루프에 빠지게 되는 것이 당연하다.

public static void func(int k){
	if(k <=0 )
    	return;
    else{
    	System.out.println("Hello");
        func(k-1);
        }
}

if문을 사용하여 탈출할 경우를 만들어주고 

호출할때 k-1을 넘겨주어 감소시켜준다면 멈출 수 있게 만들 수도 있다.

recursion이 항상 무한루프에 빠지는 것은 아니다.

무한 루프에 빠지지 않기 위해선?

적어도 하나의 다시 돌아가지 않아야 하는 경우가 존재해야한다.

이것을 Base case라고 부른다. 위의 코드의 if문이 Base case이다.

그렇다고 해서 종료 될 수 있을까?

단순히 Base case가 존재하므로 인해 종료 되는 것은 아니고

모든 경우들은 반복하다보면 base case로 수렴해야한다는 조건이다.

총 2가지의 조건이 만족되면 무한 루프에 빠지지 않는 recursion을 구현 할 수 있다.

public static int func(int n) {
	if(n==0)
    	return 0;
    else
    	return n + func(n-1);
}

1~n까지의 합을 recursion을 이용하여 쉽게 구현할 수 있다.

public static double gcd(int m, int n){
	if(m<n) {
    	int tmp=m;
        m=n;
        n=tmp;
    }
    if(m%n==0)
    	return n;
    else
    	return gcd(n, m%n);
}

정수론 시간에 배웠던 

최대공약수를 구하는 알고리즘인 유클리드 알고리즘이다.

첫번째 if문은 m이 더 큰수가 되도록 바꾸는 로직이고

두번째 if문은 m이 n으로 나누어떨어진다면 n을 리턴하고

그렇지 않다면 인자값을 n, m%n을 주며 재귀호출한다.

public static int gcd(int p, int q){
	if(q==0)
    	return p;
    else
    	return gcd(q,p%q);
}

이 코드는 좀더 단순한 유클리드 알고리즘이다.

개념

 - 모든 경우의수를 확인해야 할때

  - for로는 확인 불가한 경우( 깊이가 달라질때 )

순열 : M개의 숫자 중 N개를 뽑을때 순서에 상관하여 뽑는 방식

3개에서 2개를 뽑는다면 for로 확인하면 된다.

백트래킹은? M, N이 주어졌을 경우!

재귀함수로 구현을 한다. 깊이를 마음대로 설정할 수 있게된다.

중요한 것은 특정 상태를 제외한다는 것이다.

백트래킹은 현재 상태에서 다음 상태로 나아갈 수 있는 모든 경우를 찾되, 그 중

유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태로 돌아가 다음 상태를 검사한다.

더이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기라고 한다.

BFS와 같이 그래프 탐색의 한 종류이다.

DFS : Depth-first search 깊이 우선 탐색 이라고 한다.

DFS는 스택으로 구현이 가능하고 재귀로도 구현이 가능하다.

DFS 동작 방식은

1 - 2 - 3 - 4 - 6 - 5 과 같이 동작한다.

재귀함수 

- 자기 자신을 다시 호출하는 함수

- 주의 할점

 - 재귀 함수가 종료되는 시점이 반드시 명시되어야한다.

 - 재귀함수의 깊이가 너무 깊어지면 스택 오버플로우 현상이 발생한다.

- DFS, 백트래킹에서 주로 사용

아이디어

- 시작점에 연결된 Vertex 찾기

- 연결된 Veertex를 계속해서 찾음

- 더이상 연결된 Vertex 없을경우 다음

시간 복잡도

- 시간복잡도란? : 알고리즘이 얼마나 오래걸리는지 나타내는것

-DFS : O(V+E)

BFS에대해서 공부를 하다가 

BFS는 가중치가 동일한 경우 각 노드까지의 거리가 최단 경로라고 

설명되어있었다. 그렇다면 왜???? 

왜인지는 설명이 안되어있고 단지 최단 경로일 수 밖에 없다는 글만

수두룩 하였다.

내가 이런 궁금증을 가지게 된 이유는

애초에 이해가 덜 되어 있다고 생각한다.

1 0 0 0 0

0 0 1 1 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

빨간 0에서 출발하여 파란 0까지 가는데

1은 벽이라서 지나가질 못한다고 가정을 해보았을때

내가 처음에 한 생각을 너비 우선 탐색이니

시작점에서 오른쪽 과 아랫쪽을 탐색한다. 

결국 오른쪽 끝까지 갔을때 더이상 갈 수 없다는 것을 판단하기때문에

오른쪽 까지 가는 경우도 +3 만큼 카운팅이 된다고 생각하였다.

하지만 각 시점에서 노드가 큐에 들어간다고 했을때 

각각의 노드들은 결국 자신의 부모노드에서의 +1 이라고 생각을하니

이해가 갔다. 어떤 곳을 찍더라도 그곳은 결국 최단 경로 일 수 밖에 없었다.

이번에는 프로토타입 스코프를 싱글톤 빈과 사용했을때의 문제점에 대하여 공부하였다.

스프링 컨테이너에 프로토타입 스코프의 빈을 요청하면 항상 새로운 객체 인스턴스를 생성하여 반환한다.

하지만 싱글톤 빈과 함께 사용할 때는 의도한 대로 동작하지 않으므로 주의해야 한다.

package hello.core.scope;

import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;
import org.springframework.context.annotation.Scope;

import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;

public class SingletonWithPrototypeTest1 {

    @Test
    void prototypeFind(){
        AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(PrototypeBean.class);
        PrototypeBean prototypeBean1 = ac.getBean(PrototypeBean.class);
        prototypeBean1.addCount();
        Assertions.assertThat(prototypeBean1.getCount()).isEqualTo(1);

        PrototypeBean prototypeBean2 = ac.getBean(PrototypeBean.class);
        prototypeBean2.addCount();
        Assertions.assertThat(prototypeBean2.getCount()).isEqualTo(1);
    }

    @Scope("prototype")
    static class PrototypeBean{
        private int count = 0;

        public void addCount(){
            count++;
        }

        public int getCount(){
            return count;
        }

        @PostConstruct
        public void init() {
            System.out.println("PrototypeBean.init" +this);
        }

        @PreDestroy
        public void destroy(){
            System.out.println("PrototypeBean.destroy = ");
        }

    }
}

코드로 보면 가상의 사용자 1 ,2 가 count라는 데이터를 증가시키는 메서드를 호출했을 때 

다른 객체를 생성하기 때문에 count값이 1이 된다는 것을 테스트 하는 코드이다.

싱글톤 빈에서 프로토타입 빈 사용

package hello.core.scope;

import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;
import org.springframework.context.annotation.Scope;

import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;

public class SingletonWithPrototypeTest1 {

    @Test
    void prototypeFind(){
        AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(PrototypeBean.class);
        PrototypeBean prototypeBean1 = ac.getBean(PrototypeBean.class);
        prototypeBean1.addCount();
        Assertions.assertThat(prototypeBean1.getCount()).isEqualTo(1);

        PrototypeBean prototypeBean2 = ac.getBean(PrototypeBean.class);
        prototypeBean2.addCount();
        Assertions.assertThat(prototypeBean2.getCount()).isEqualTo(1);
    }

    @Test
    void singletonClientUsePrototype(){
        AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(ClientBean.class, PrototypeBean.class);
        ClientBean clientBean1 = ac.getBean(ClientBean.class);
        int count1 = clientBean1.logic();
        Assertions.assertThat(count1).isEqualTo(1);

        ClientBean clientBean2 = ac.getBean(ClientBean.class);
        int count2 = clientBean2.logic();
        Assertions.assertThat(count2).isEqualTo(2);

    }

    @Scope("singleton")
    static class ClientBean{
        private final PrototypeBean prototypeBean;

        public ClientBean(PrototypeBean prototypeBean){
            this.prototypeBean = prototypeBean;
        }

        public int logic(){
            prototypeBean.addCount();;
            int count = prototypeBean.getCount();
            return count;
        }

    }

    @Scope("prototype")
    static class PrototypeBean{
        private int count = 0;

        public void addCount(){
            count++;
        }

        public int getCount(){
            return count;
        }

        @PostConstruct
        public void init() {
            System.out.println("PrototypeBean.init" +this);
        }

        @PreDestroy
        public void destroy(){
            System.out.println("PrototypeBean.destroy = ");
        }

    }
}

새로운 클래스 ClientBean을 만들고 PrototypeBean을 의존한다.

먼저 ClientBean은 싱글톤이다. 

스프링 빈에 등록되면서 생성자에 있는 PrototypeBean을 요청하는데 

그때 스프링 컨테이너가 PrototypeBean을 만들어서 던져준다.

그때 만들어진 객체가 생성시점에 주입된다. 

PrototypeBean의 메서드를 호출하면 이미 생성된 객체에서 

같이 쓰게된다. 

한마디로 스프링 컨테이너에서 새로운 요청을 받을 때마다 생성해주는 기능인데

처음 주입받을때만 들어와버린것이다.

프로토타입을 쓰는 이유가 전혀 없는 코드가 되어버린것이다. 

그래프 탐색 : 어떤 것들이 연속해서 이어질때, 모두 확인하는 방법

그래프 :  Vertex(어떤 것) + Edge(이어지는 것)

그래프 탐색 종류

- BFS : Breadth-first search(너비 우선 탐색)

- DFS : Depth-first search(깊이 우선 탐색)   

BFS : 1 2 5 3 4 6 

DFS : 1 2 3 4 6 5

BFS 

아이디어

- 시작점에 연결된 Vertex를 찾기

- 찾은 Vertex를 Queue에 저장

- Queue의 가장 먼저 것 뽑아서 반복

시간 복잡도

-BFS : O(V+E)

자료구조

- 검색할 그래프

- 방문여부 확인(재방문 금지)

- Queue : BFS  실행

프로토타입 스코프에 대해서 공부해보았다.

먼저 기본으로 만들면 싱글톤 스코프가 적용된다.

싱글톤 스코프의 빈을 조회하면 스프링 컨테이너는 항상 같은 인스턴스의 스프링 빈을 반환하는 것이 보장된다.

반면에 프로토타입 스코프를 조회하면 스프링 컨테이너는 항상 새로운 인스턴스를 생성하여 반환한다.

싱글톤 빈 요청

1. 싱글톤 스코프의 빈을 스프링 컨테이너에 요청

2. 스프링 컨테이너는 본인이 관리하는 스프링 빈을 반환

3. 이후에 스프링 컨테이너에 같은 요청이 와도 같은 객체 인스턴스의 스프링 빈을 반환.

프로토타입 빈 요청

1. 프로토타입 스코프의 빈을 스프링 컨테이너에 요청.

2. 스프링 컨테이너는 이 시점에 프로토타입 빈을 생성하고 필요한 의존관계를 주입.

3. 스프링 컨테이너는 생성한 프로토 타입 빈을 클라이언트에 반환.

4. 스프링 컨테이너에 같은 요청이 오면 항상 새로운 프로토타입 빈을 생성해서 반환.

핵심은 스프링 컨테이너는 프로토타입 빈을 생성하고 의존관계 주입, 초기화 까지만 처리함.

클라리언트에 빈을 반환하고 이후 스프링 컨테이너는 생성된 프로토 타입 빈을 관리를 하지 않음

클라이언트가 종료 메서드를 호출해야함. 관리할 책임은 클라이언트가 가지는 것.

package hello.core.scope;

import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;
import org.springframework.context.annotation.Scope;

import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;

public class SingletonTest {

    @Test
    void singletonBeanFind(){
        AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(SingletonBean.class);

        SingletonBean bean1 = ac.getBean(SingletonBean.class);
        SingletonBean bean2 = ac.getBean(SingletonBean.class);
        System.out.println("bean1 = " + bean1);
        System.out.println("bean2 = " + bean2);
        Assertions.assertThat(bean1).isSameAs(bean2);
        ac.close();
    }

    @Scope("singleton")
    static class SingletonBean{

        @PostConstruct
        public void init(){
            System.out.println("SingletonBean.init");
        }

        @PreDestroy
        public void destroy(){
            System.out.println("SingletonBean.destroy");
        }
    }

}

기존에 방식 그대로 싱글톤으로 적용하고 테스트 코드를 작성해보았다.

예상했던 결과를 얻을 수 있었다.

package hello.core.scope;

import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;
import org.springframework.context.annotation.Scope;

import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;

public class PrototypeTest {

    @Test
    void prototypeBeanFind(){
        AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(PrototypeBean.class);
        System.out.println("find prototypeBean1");
        PrototypeBean prototypeBean1 = ac.getBean(PrototypeBean.class);
        System.out.println("find prototypeBean2");
        PrototypeBean prototypeBean2 = ac.getBean(PrototypeBean.class);
        System.out.println("prototypeBean1 = " + prototypeBean1);
        System.out.println("prototypeBean2 = " + prototypeBean2);
        Assertions.assertThat(prototypeBean1).isNotSameAs(prototypeBean2);
        ac.close();
    }

    @Scope("prototype")
    static class PrototypeBean{
        @PostConstruct
        public void init(){
            System.out.println("PrototypeBean.init");
        }

        @PreDestroy
        public void destroy(){
            System.out.println("PrototypeBean.destroy");
        }
    }
}

프로토타입을 이용한 테스트코드를 작성해보았다.

bean1 , bean2 조회시 다르다는 것을 검증하기 위한 코드이다.

콘솔을보면

- 싱글톤 빈은 스프링 컨테이너 생성 시점에 초기화 메서드가 실행 되지만, 프로토타입 스코프의 빈은

   스프링 컨테이너에서 빈을 조회할 때 생성되고, 초기화 메서드도 실행된다. 

- 프로토 타입 빈을 2번 조회하였으므로 다른 빈이 생성되고, 초기화도 2번 실행 된 것을 알 수 있다.

- 프로토 타입 빈은 스프링 컨테이너가 생성, 의존관계 주입, 초기화 까지만 관여하고 더는 관리하지 않는다. 따라서

   종료될때 @PreDestroy 같은 종료 메서드가 전혀 실행되지 않는다.

빈 스코프에 대하여 공부해보았다.

빈 스코프란?

지금까지는 스프링 빈이 스프링 컨테이너가 만들어질때 빈들도 함께 생성 후 관리되며

스프링 빈이 종료될때 까지 유지된다고 학습했다. 이것은 빈이 기본적으로 싱글톤 스코프로 생성되기 때문이다.

스코프는 빈이 존재할 수 있는 범위를 말한다.

스프링의 다양한 스코프

싱글톤 : 기본 스코프로, 스프링 컨테이너의 시작과 종료까지 유지되는 가장 넓은 범위의 스코프이다.

프로토타입 : 스프링 컨테이너는 프로토타입 빈의 생성과 의존관계 주입까지만 관여하는 짧은 범위 스코프이다.

웹 관련 스코프

request : 웹 요청이 들어오고 나갈때 까지 유지되는 스코프이다.

session : 웹 세션이 생성되고 종료될 때 까지 유지되는 스코프이다.

application : 웹의 서블릿 컨텍스와 같은 범위로 유지되는 스코프이다.

컴포넌트 스캔 방식의 경우

@Scope("prototype")
@Component
public class ScopeExample{}

수동 등록의 경우

@Scope("prototype")
@Bean
PrototypeBean ScopeExample(){
	return new ScopeExample();
    }

지금까지는 싱글톤 스코프를 계속 사용해왔던 것이다.

스프링 빈 생명주기 콜백 쪽을 공부하면서 이해가 잘 가지 않는 부분에 대해서 궁금증이 생겨 알아보았다.

먼저 라이브러리는 이렇게 분류된다.

표준 라이브러리

외부 라이브러리 

표준 라이브러리는

프로그래밍 언어와 함께 제작사에서 제공되는 라이브러리를 의미한다.

별도의 설치없이 다양한 기능을 이용할 수 있게 제공한다.

외부 라이브러리?

표준 라이브러리와 달리 별도의 파일을 설치하여야 사용할 수 가 있다.

외부라이브러리는 누구나 개발하여 사용하고 공유할 수 있으며 인터넷 등을

이용하여 공유된 라이브러리를 사용 할 수 있다.

왜 애너테이션을 사용하면 외부라이브러리에 사용을 하지 못하는 것일까?

gradle을 예로들면 수정할 수 없는 외부라이브러리 이다.

테스트를 한다고 하면 테스트 코드를 짜면서 직접 @Bean으로 등록할 때 해당,

라이브러리에 있는 클래스 안에 있는 메서드를 파악하고 빈으로 직접 등록하여 초기화, 종료 할 수 있다.

그러나 애너테이션은 코드에 @을 붙여야하는데 코드를 수정할 수 없기 때문에 사용할 수 가없는 것이다.