프록시 방식을 사용해보았다.

 

package hello.core.common;

import org.springframework.context.annotation.Scope;
import org.springframework.context.annotation.ScopedProxyMode;
import org.springframework.stereotype.Component;

import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;
import java.util.UUID;

@Component
@Scope(value = "request", proxyMode = ScopedProxyMode.TARGET_CLASS)
public class MyLogger {

    private String uuid;
    private String requestURL;


    public void setRequestURL(String requestURL) {
        this.requestURL = requestURL;
    }

    public void log(String message){
        System.out.println("["+uuid+"]" +"["+requestURL+"] "+message);
    }

    @PostConstruct
    public void init(){
        uuid  = UUID.randomUUID().toString();
        System.out.println("["+uuid+"] request scope bean create:" + this);
    }

    @PreDestroy
    public void close(){
        System.out.println("["+uuid+"] request scope bean close:" + this);
    }
}

MyLogger에  proxyMode = ScopedProxyMode.TARGET_CLASS를 추가해 주었다.

가짜 MyLogger를 넣어두고 실제 호출하는 시점에 진짜를 찾아서 동작한다.

package hello.core.web;

import hello.core.common.MyLogger;
import lombok.RequiredArgsConstructor;
import org.springframework.beans.factory.ObjectProvider;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.ResponseBody;

import javax.servlet.http.HttpServletRequest;

@Controller
@RequiredArgsConstructor
public class LogDemoController {

    private final LogDemoService logDemoService;
    private final MyLogger myLogger;

    @RequestMapping("log-demo")
    @ResponseBody
    public String logDemo(HttpServletRequest request){
        String requestURL = request.getRequestURL().toString();
        myLogger.setRequestURL(requestURL);

        myLogger.log("controller test");
        logDemoService.logic("testId");
        return "OK";
    }

}
package hello.core.web;

import hello.core.common.MyLogger;
import lombok.RequiredArgsConstructor;
import org.springframework.beans.factory.ObjectProvider;
import org.springframework.stereotype.Service;

@Service
@RequiredArgsConstructor
public class LogDemoService {

    private final MyLogger myLogger;

    public void logic(String id) {
        myLogger.log("service id =" + id);
    }
}

 

CGLIB라는 바이트코드를 조작하는 라이브러리를 사용하여 내 클래스를 상속받은 가짜 프록시 객체를 만들어서 주입한다.

 

스프링 컨테이너에 myLogger라는 이름으로 진짜 대신에 가짜 프록시 객체를 등록한다.

그래서 의존관계 주입도 이 가짜 프록시 객체가 주입된다.

 

가짜 프록시 객체는 요청이 오면 그때 내부에서 진짜 빈을 요청하는 위임 로직이 들어있다.

 

가짜 프록시 객체는 내부에 진짜 myLogger를 찾는 방법을 알고 있다.

 


 

-동작 정리

 

CGLIB라는 라이브러리로 내 클래스를 상속받은 가짜 프록시 객체를 만들어서 주입한다.

 

이 까자 프록시 객체는 실제 요청이 오면 그때 내부에서 실제 빈을 요청하는 위임 로직이 들어 있다.

 

이 가짜 프록시 객체는 실제  request scope와는 관계가 없다 그냥 가짜이고, 내부에 단순한 위임 로직만 있고,

싱글톤 처럼 동작한다.

 

-특징 정리

 

프록시 객체 덕분에 클라이언트는 마치 싱글톤 빈을 사용하듯이 편리하게 request scope를 사용할 수 있다.

 

사실 Provider를 사용하든, 프록시를 사용하든 핵심 아이디어는 진짜 객체 조회를 꼭 필요한 시점까지 지연처리 한다는 점이다.

 

단지 애너테이션 설정 변경만으로 원본 객체를 프록시 객체로 대체할 수 있다. 이것이 바로 다형성과 DI 컨테이너가 가진 큰 강점이다.

 

꼭  웹 스코프가 아니어도 프록시는 사용할 수 있다.

 

-주의점

 

마치 싱글톤을 사용하는 것 같지만 다르게 동작하기 때문에 결국 주의해서 사용해야 한다.

이런 특별한 scope는 꼭 필요한 곳에서만 최소화해서 사용하자, 무분별하게 사용한다면 유지보수가 어려워진다.

첫번째 해결방안은 Provider를 사용하는 것이다.

 

package hello.core.web;

import hello.core.common.MyLogger;
import lombok.RequiredArgsConstructor;
import org.springframework.beans.factory.ObjectProvider;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.ResponseBody;

import javax.servlet.http.HttpServletRequest;

@Controller
@RequiredArgsConstructor
public class LogDemoController {

    private final LogDemoService logDemoService;
    private final ObjectProvider<MyLogger> myLoggerProvider;

    @RequestMapping("log-demo")
    @ResponseBody
    public String logDemo(HttpServletRequest request){
        MyLogger myLogger = myLoggerProvider.getObject();
        String requestURL = request.getRequestURL().toString();
        myLogger.setRequestURL(requestURL);

        myLogger.log("controller test");
        logDemoService.logic("testId");
        return "OK";
    }

}
package hello.core.web;

import hello.core.common.MyLogger;
import lombok.RequiredArgsConstructor;
import org.springframework.beans.factory.ObjectProvider;
import org.springframework.stereotype.Service;

@Service
@RequiredArgsConstructor
public class LogDemoService {

    private final ObjectProvider<MyLogger> myLoggerProvider;

    public void logic(String id) {
        MyLogger myLogger = myLoggerProvider.getObject();
        myLogger.log("service id =" + id);
    }
}

[fa840c5d-73c3-41d8-867b-379ad034f824] request scope bean create:hello.core.common.MyLogger@52364add
[fa840c5d-73c3-41d8-867b-379ad034f824][http://localhost:8080/log-demo] controller test
[fa840c5d-73c3-41d8-867b-379ad034f824][http://localhost:8080/log-demo] service id =testId
[fa840c5d-73c3-41d8-867b-379ad034f824] request scope bean close:hello.core.common.MyLogger@52364add

 

잘 동작하는 것을 볼 수있다.

 

ObjectProvider 덕분에 objectProvider.getObject()를 호출하는 시점까지 request scope 빈의 생성을 지연 할 수 있다.

 

objectProvider.getObject()를 호출하는 시점에는 HTTP 요청이 진행중이므로 request 빈의 생성이 정상 처리된다.

 

objectProvider.getObject()를 LogDEmoController, LogDemoService에서 각각 한번씩 따로 호출해도 같은 HTTP 요청이면 같은 스프링 빈이 반환된다.

웹 환경 추가 

 

웹 스코프는 우베 환경에서만 동작하므로 web 환경이 동작하도록 라이브러리를 추가하였다.

 


 

request 스코프 예제 개발

 

만일 동시에 여러개의 요청이오면 정확히 어떤 요청이 남긴 로그인지 구분하기 어렵다.

이럴때 사용하기 좋은 것이 request 스코프이다.

 

package hello.core.common;

import org.springframework.context.annotation.Scope;
import org.springframework.stereotype.Component;

import javax.annotation.PostConstruct;
import javax.annotation.PreDestroy;
import java.util.UUID;

@Component
@Scope(value = "request")
public class MyLogger {
    
    private String uuid;
    private String requestURL;


    public void setRequestURL(String requestURL) {
        this.requestURL = requestURL;
    }
    
    public void log(String message){
        System.out.println("["+uuid+"]" +"["+requestURL+"] "+message);
    }
    
    @PostConstruct
    public void init(){
        uuid  = UUID.randomUUID().toString();
        System.out.println("["+uuid+"] request scope bean create:" + this);
    }
    
    @PreDestroy
    public void close(){
        System.out.println("["+uuid+"] request scope bean close:" + this);
    }
}

로그를 출력하기위한 코드이다.

 

request 스코프로 지정했다. 이 빈은 HTTP 요청 당 하나씩 생성되고, HTTP 요청이 끝나는 시점에 소멸된다.

 

이 빈이 생성되는 시점에 자동으로 @PostContruct 초기화 메서드를 사용하여 uuid를 생성해 저장해둔다 이 빈은 

HTTP요청 당 하나씩 만들어지므로 uuid를 저장해두면 다른 요청과 구분할 수 있다.

 

이 빈이 소멸되는 시점에 @PreDestroy를 사용하여 종료 메시지를 남긴다.

 

requestURL은 이 빈이 생성되는 시점에는 알 수 없기때문에, 외부에서 setter로 입력받는다.

 

package hello.core.web;

import hello.core.common.MyLogger;
import lombok.RequiredArgsConstructor;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.ResponseBody;

import javax.servlet.http.HttpServletRequest;

@Controller
@RequiredArgsConstructor
public class LogDemoController {

    private final LogDemoService logDemoService;
    private final MyLogger myLogger;

    @RequestMapping("log-demo")
    @ResponseBody
    public String logDemo(HttpServletRequest request){
        String requestURL = request.getRequestURL().toString();
        myLogger.setRequestURL(requestURL);

        myLogger.log("controller test");
        logDemoService.logic("testId");
        return "OK";
    }

}

 컨트롤러를 만들었다.

 

 No thread-bound request found: Are you referring to request attributes outside of an actual web request, or processing a request outside of the originally receiving thread? If you are actually operating within a web request and still receive this message, your code is probably running outside of DispatcherServlet: In this case, use RequestContextListener or RequestContextFilter to expose the current request.
at org.springframework.web.context.request.RequestContextHolder.currentRequestAttributes(RequestContextHolder.java:131) ~[spring-web-5.3.8.jar:5.3.8]

 

실행시켜보니 위와 같은 에러가 발생하였다.

 

그 이유는 MyLogger가 repuest 스코프라서 요청이 들어와야 쓸 수 있는데 

컨트롤러에서 의존관계 주입할 것이 없기 때문에 에러가 발생하였다.

 

package hello.core.web;

import hello.core.common.MyLogger;
import lombok.RequiredArgsConstructor;
import org.springframework.stereotype.Service;

@Service
@RequiredArgsConstructor
public class LogDemoService {

    private final MyLogger myLogger;

    public void logic(String id) {
        myLogger.log("service id =" + id);
    }
}

서비스 계층에서도 로그를 출력해보기 위해 만들었다.

중요한 점은 request scope를 사용하지 않고 파라미터로 이 모든 정보를 서비스 계층에 넘긴다면

파라미터가 많아서 지저분해진다 더 문제는 requestURL 같은 웹과 관련된 정보가 웹과 관련없는 서비스 계층까지

넘어가게 된다. 웹과 관련된 부분은 컨트롤러까지만 사용하는 것이 유지보수 차원 에서 좋다.

 

 

웹 스코프에 대하여 알아보았다.

 

싱글톤 : 스프링 컨테이너의 시작과 끝까지 가는 매우 긴 스코프.

프로토타입 : 생성과 의존관계 주입, 초기화까지만 진행하는 특별한 스코프.

 

웹 스코프의 특징

웹 스코프는 웹 환경에서만 동작한다.

프로토타입과는 다르게 스프링이 해당 스코프의 종료시점까지 관린하다. 따라서 종료 메서드가 호출됨.

 

웹 스코프 종류

request : HTTP 요청 하나가 들어오고 나갈 때까지 유지되는 스코프, 각각의  HTTP요청 마다 별도의 빈 인스턴스가 생성되고

관리된다.

session :  HTTP Session과 동일한 생명주기를 가지는 스코프

application : 서블릿 컨택스트와 동일한 생명주기를 가지는 스코프

websocket : 웹 소켓과 동일한 생명주기를 가지는 스코프

 

 

 

 

임의의 집합 data에 대해서 원소들의 모든 가능한 순열을 출력하라

 

data = {a,b,c,d} 

4! = 24개

 

a b c d

a b d c

a c b d

a d b c

. . . . 

 

a를 고정 - b,c,d의 모든 순열에 a를 앞에 추가하여 출력

b를 고정 - a,c,d의 모든 순열에 b를 앞에 추가하여 출력

. . . . 

a,b를 고정 - c,d의 모든 순열에 a,b를 앞에 추가하여 출력

. . . 

a,b,c를 고정 - d에 a,b,c를 앞에 추가하여 출력

 

void printPerm(a prefix string, a set S)
{
	if S is 0
    	print the pre fix string;
    else
    	for each element x in S
        	printPerm(the prefix string + x, S-{x});
}

S의 모든 순열들을 생성한 후 각각에 prefix String을 앞에 붙여서 출력한다.

 

int data[] = {'a','b','c','d'};
int n = 4;

void perm(int k) {
	if(k==n) {
    	print data[0...n-1];
        return;
    }
    
    for(int i=k; i<n; i++) {
    	swap(data, k, i);
        perm(data, k+1; n);
        swap(data, k, i);
        }
    }

perm이라는 함수의 미션은 매개변수 k를 받아서 data[a..k-1]prefix로 정하고 data[k..n]으로 만들수 있는 모든 순열을

프린트하되, 배열 data에 저장된 값들의 순서는 그대로 유지한다.

 


 

멱집합(순서무관)과 순열 나열(순서상관)의 응용

 

배낭문제 

-무게와 가격이 정해진 n개의 아이템과 용량이 w이 배낭이 있다.

배낭의 용량을 초과하지 않으면서 가격의 합이 최대가 되도록 아이템을 배낭에 넣으려면?

 

TSP

- 서울 대전 대구 부산 광주 강릉 속초 등의 n개의 도시들이 있을때

한 도시에서 출발하여 모든 도시들을 지나서 다시 집으로 돌아올때 방문 순서에따라

이동 거리가 달라지는데 길이가 가장 짧은 투어를 고르는 문제.

 

 

'알고리즘 with 자바 > 알고리즘' 카테고리의 다른 글

union-find  (1) 2025.06.12
문자열 자르기 관련 함수  (0) 2022.04.25
멱집합  (0) 2021.09.13
Recursion의 응용 : n queen problem  (0) 2021.09.09
Recursion의 응용 : Counting Cells in a Bob  (0) 2021.09.09

임의의 집합 data의 모든 부분집합을 출력하라

 

data = {a,b,c,d} 

 

공집합

a

b

c

d

a b

a c

a d

b c . . . 

2의 4(원소갯수)승 = 16개

 

{a,b,c,d,e,f}의 모든 부분집합을 나열하려면

a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고

{b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. 

 

powerSet(S)
if s is an empty set
	print nothing;
else
	let t be the first element of s;
    find all subsets of s-[t] by calling powerSet(s-{t});
    print the subsets;
    print thet subsets with adding t;

Pseudo code

 

입력으로 하나의 집합 s가 주어진다.

s의 멱집합을 출력하는 것이 미션이다.

 

base case 

만약 s가 공집합이라면 공집합을 출력한다.

 

그렇지 않다면

 

집합s에서 한 원소t에 대해서 t를 제외한 집합의 부분집합을 구한다.

그 부분집합을 출력하고

제외했던 원소를 추가하여 출력한다

 

s-{t}의 부분집합을 구한 후 그 부분집합을 한번은 그대로 출력하고 한번은 t를 추가해 출력하려면

powerSet함수는 여러개의 집합들을 return 해야한다. 어떻게 해야할까

 

powerSet(P,S)
if S is an empty set
	print p;
else 
	let t be the first element of S;
    powerSet(P, S-{t});
    powerSet(Pu{t}, S-{t});

처음 호출할때 P를 공집합 S가 전체데이터 집합 이라면 

S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하도록 설계해야한다.

 

base case

만약 s가 공집합이라면 집합 P 출력

그렇지 않다면 t에 대해서 s에서 t를 제외하여 호출하고

t를 포함하여 P에 합쳐두어 출력하게 만든다.

 

함수가 두 개의 집합을 매개변수로 받도록 설계해야한다는 의미이다.

두 개의 집합의 모든 부분집합들에 첫접째 집합을 합집합 하여 출력한다.

 

두 개의 집합으로 나뉘게되면 

집합 S : k번째 부터 마지막 원소까지 연속된 원소들이다.

집합 P : 처음부터 k-1째 원소들 중 일부이다.

 

boolean배열을 사용하여 

집합 P를 구현할 수 있다.

 

private static char data[] = {'a','b''c','d','e','f'};
private static int n = data.length;
private static boolean [] include = new boolean[n];

public static void powerSet(int k) {
	if(k==n){
    	for(int i =0; i<n; i++)
        	if(include[i]) System.out.print(data[i] + " ");
        System.out.println();
        retrun;
	}
include[k] = false;
powerSet(k+1);
include[k] = true;
powerSet(k+1);
}

실제 코드는 이렇게 된다.

 

k는 매개변수로 넘겨주고

배열은 전역변수로 어디에서든 읽을 수 있게한다.

 

매개변수 k는 전체집합에서 k번째 원소부터 나머지 원소가 집합s이고

나머지 원소들 중 include가 true 인 원소들만 포함시켜 출력하라는 의미이다.

 

base case는 s가 공집합이라면 p를 출력한다. == 배열 include값이 true인 원소들을 출력한다.

 

일반적인 경우에는 

data[k] 를 포함하지 않는경우와

data[k] 를 포함하는 경우로 나누어서 재귀를 돌린다.

 

https://www.youtube.com/watch?v=nkeMRRIVW9s&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=7

상태공간 트리로 a,b,c의 모든 멱집합을 구하는 과정을 시각화 한 것이다.

 

a를 포함하는 경우와 안하는경우 

b를 포함하는 경우와 안하는 경우 이런식으로 아래로 내려간다.

 

 

 

 

싱글톤 빈과 프로토타입 빈을 함께 사용할때, 어떻게 하면 사용할 때마다 항상 새로운 프로토타입 빈을 생성할 수 있을까?

 

스프링 컨테이너에 요청

 

가장 간단한 방법은 싱글톤 빈이 프로토타입을 사용할 때마다 스프링 컨테이너에 새로 요청하는 것이다.

 

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 = ");
        }

    }
}

이전 시간의 코드이다.

 

의존관계를 외부에서 주입받는게 아니라 이렇게 직접 필요한 의존관계를 찾는 것을 Dependency Lookup이라고 한다.

 

그런데 이렇게 스프링의 애플리케이션 컨텍스트 전체를 주입받게 되면, 스프링 컨테이너에 종속적인 코드가 되고, 단위 테스트도 어려워진다.

 

지금 필요한 기능은 지정한 프로토타입 빈을 컨테이너에서 대신 찾아주는 DL 정도의 기능만 제공하는 무언가가 있으면 된다.

 


 

ObjectFactory, ObjectProvider

 

지정한 빈을 컨테이너에서 대신 찾아주는 DL 서비스를 제공하는 것이 바로 ObjectProvider 이다.

과거에는 ObjectFactory 가 있었는데, 여기에 편의 기능을 추가하여 ObjectProvider 가 만들어졌다.

 

  @Scope("singleton")
    static class ClientBean{
        @Autowired
        private ObjectProvider<PrototypeBean> prototypeBeanProvider;


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

    }

 

실행해보면 getObject()를 통해서 항상 새로운 프로토타입 빈이 생성되는 것을 확인할 수 있다.

 

getObject()를 호출하면 내부에서는 스프링 컨테이너를 통해 해당 빈을 찾아서 반환한다.

 


JSR-330 Provider

 

마지막 방법은  javax.inject.Provider 라는 자바 표준을 사용하는 방법이다.

이방법을 사용하려면 라이브러리를 gradle에 추가해야한다.

 

    @Scope("singleton")
    static class ClientBean{
        @Autowired
        private Provider<PrototypeBean> prototypeBeanProvider;


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

    }

실행해보면 provider.get()을 통해 항상 새로운 프로토타입 빈이 생성되는 것을 확인할 수 있다.

provider의 get() 을 호출하면 내부에서는 스프링 컨테이너를 통해 해당 빈을 찾아서 반환한다.

자바 표준이고, 기능이 단순하므로 단위테스트를 만들거나 mock코드를 만들기 훨씬 쉽다.

 

프로토타입 빈을 언제 사용할까? 매번 사용할때 마다 의존 관계 주입이 완료된 새로운 객체가 필요하면 사용하면 된다.

그런데 실무에서 대부분의 문제는 싱글톤 빈으로 해결 할 수 있기에 쓰는 경우가 드물다고 한다.

- 입력으로 n을 받는다.

- n*n 2차월 배열을 생성

- n개의 퀸을 놓을때 어떠한 행,열,대각에 겹치는 퀸이 없게 놓는 방법.

- 퀸은 대각,행,열 한방향으로 끝까지 이동 가능

 

Backtracking

내가 결정을 하며 내려가다가 안된다는 것이 분명해 지면 내가 최근에 내린 결정을 번복하고

다른 결정을 내리는 알고리즘

상태 공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다.

 

상태 공간 트리

 

https://www.youtube.com/watch?v=xKGbWC-DPT4&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=6

 

상태공간트리란 ? 찾는 해를 포함하는 트리

즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함

따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음.

 

상태공간 트리의 모든 노드를 탐색해야 하는 것은 아니다.

 


Design Recursion

 

return type queens(arguments)
{
    if non-promising
    	report failure and return;
    else if sucess
    	report answer and return;
    else
    	visit children recursively;
}

 

내가 어떤 노드에 도착하면 제일먼저 생각해야할 것은

 

이미 더이상 갈 필요가 없는 노드인가 아닌가를 생각해야한다.

아니라면 되돌아가면 그만이다.

 

두번째로 지금 도착한 노드가 내가 찾고있던 그 노드인가를 확인한다.

 

그렇지 않다면 

이 노드의 자식노드들을 방문해보는것이다.

 

int[] cols = new int [N+1];
boolean queens(int level)
{
    if non-promising
    	report failure and return;
    else if sucess
    	report answer and return;
    else
    	visit children recursively;
}

어떤 매개변수를 넘겨줄 것인가?

내가 현재 어떤 노드인지 알아야 하기때문에 깊이 정보를 넘겨준다.

 

2차원 배열을 사용할 필요가 없다.

 

cols[1] : 1번 말이 놓인 열 번호

cols[2] : 2번 말이 놓인 열 번호

cols[level] : level번째 말이 놓인 열 번호

 

int[] cols = new int [N+1];
boolean queens(int level)
{
    if(!promising(level))
        return false;
    else if (level == N)
    	return true;
    for(int i = 1; i<=N; i++){
    	cols[level+1] = i;
        if(queens(level+1))
        	return true;
       }
       return false;
}

level + 1 값을 재호출한다.

'알고리즘 with 자바 > 알고리즘' 카테고리의 다른 글

순열  (0) 2021.09.15
멱집합  (0) 2021.09.13
Recursion의 응용 : Counting Cells in a Bob  (0) 2021.09.09
Recursion의 개념과 기본 예제들 3  (0) 2021.09.08
Recursion의 개념과 기본 예제들 2  (0) 2021.09.08

- 입력으로 하나의 Binary 이미지를 받는다.

- 각 픽셀은 background pixel 이거나 혹은 image pixel

- 서로 연결된 image pixel들의 집합을 blob이라고 부름

- 상하좌우 및 대각방향으로도 연결된 것으로 간주

 

https://www.youtube.com/watch?v=HHJFlVT1tBw&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=5

입력 : n*n 크기의 2차원 그리드 , 하나의 좌표(x,y)

 

출력 : 픽셀 (x,y)가 포함된 blob의 크기, (x,y)가 어떤 blob에도 속하지 않는 경우는 0

 


 

Recursive Thinking

 

현재 픽셀이 이 속한 blob의 크기를 카운트 하려면

    현재 픽셀이 image color가 아니라면

        0을반환

    현재 픽셀이 image color 라면

        먼저 현재 픽셀을 카운트한다.

        현재 픽셀이 중복 체크되는 것을 방지하기 위해 다른 색으로 칠한다.

        현재 픽셀에 이웃한 모든 픽셀들에 대해서 

            그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.

        카운터를 반환한다.

 

	private static void dfs(int x,int y) {
		
		if(x < 0 || x >= n || y < 0 || y >= n) {
			return;
		}
		
		visited[x][y] = true;
		count++;
		
		for(int i=0; i<8; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;
			if(arr[nx][ny]==1&&!visited[nx][ny]) {
				dfs(nx,ny);
			}
		}
	}

직접 짜본 코드이다. 강의 보다 더 보기쉽게 구현하였다.  

순환적 알고리즘 설계

 

적어도 하나의 base case가 있어야한다.

모든 case는 결국 base case로 수렴해야 한다.

 


 

암시적 매겨변수를 

명시적 매개변수로 바꾸어라 

이 말이 무슨 뜻일까?

 

순차 탐색을 예로 들어보자.

int search(int [] data, int n, int target) {
	for(int i=0; i<n; i++)
    	if(data[i] == target)
        	return i;
    return -1;
}

 

이 함수의 미션은 data[0] ~ data[n-1] 사이에서 target을 검색하는 것이다.

하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.

 

일반적으로 recursion을 사용하지 않는 함수에서는 이렇게 암시적으로 생략할 수 있다면 

생략하는 것이 코드의 간결성 관점에서 좋다.

하지만 recursion 프로그래밍을 할때는 일반적으로 저렇게 하지 않는 것이 좋다.

 

int search(int [] data, int begin, int end, int target){
	if(begin>end)
    	return -1;
    else if(target==items[begin])
    	return begin;
    else
    	return search(data, begin+1, end, target);
}

이 코드는 위의 코드를 recursive하게 변경한 코드이다.

 

배열 데이터가 있고 target의 인덱스를 찾고 싶다면 

이전 코드에는 순서대로 검사 후 찾아내는 절차적 프로그래밍 이라면

 

첫번째 값이 타겟이라면 찾은것이고 그 경우는 첫번째 값의 인덱스를 리턴하고

아니라면 나머지 구간을 검색하면 된다.

 

두 코드의 차이는 검색할 구간의 명시이다.

두번째 코드는 시작위치 마저 명시되어있다. 이게 더좋은 이유는

다시 자기자신을 호출할때 다른 일을 하게 만들어야 하기때문에 

그렇게 설계해야만 한다. 맨처음의 일만 생각하여 매개변수를 넣으면

안된다.

 

거꾸로 검색해도 같은 결과를 얻을 수 있다.

그때는 begin을 고정으로 두고 end값을 줄여가며 검색할 수 있다.

 


int search(int [] data, int begin, int end, int target){
	if(begin>end)
    	return -1;
    else{
    	int middle = (begin+end)/2;
        if(data[middle]==target)
        	return middle;
        int index = search(data, begin, middle-1, target);
        if(index != -1)
        	return index;
        else
        	return search(data, middle+1, end, target);
        }
}

순차 탐색의 다른 버전이다.

이진 탐색과는 다르다.

시작점과 끝점의 가운데 위치가 타겟이라면 리턴하고

아니라면 시작점과 중간점-1로 두고 검사한다.

 


매개변수의 명시화 : 최대값 찾기

int findMax(int [] data, int begin, int end){
	if(begin==end)
    	return data[begin];
    else
    	return Math.max(data[begin], findMax(data,begin+1, end);
}

일반적으로 우리가 데이터들이 어떤 배열에 저장되어있을때

최대값을 찾을때의 함수의 매개변수는 일반적으로

findMax(int[] data, int n) 이렇게 설계한다.

recursion을 이용한다면 배열 데이터에 관심있는 데이터의 시작위치와 끝 위치의 매개변수가 필요하다.

 


Binary Search

 

public static int binarySearch(String[] items, String target, int begin, int  end){
	if(begin>end)
    	return -1;
    else{
    	int middle = (begin+end)/2;
        int compResult = target.compareTo(items[middle]);
        if(comResult == 0)
        	return middle;
        else if(compResult<0)
        	return binarySerach(items, target, begin, middle-1);
        else
        	return binarySearch(items, target, middle+1 end);
        }
}

이진 탐색이란 데이터들이 크기순으로 정렬되어있을때 적용할 수 있는 검색방법이다.

먼저 가운데 데이터를 비교하여 동일하다면 리턴하고

그보다 크다면 시작점을 중간점 이후로 이동한다.

그보다 작다면 종료점을 중간점 이전으로 이동한다.

 

이과정을 recursive하게 동작하면 된다.

 

이진 탐색은 그 자체로 recursive하다.

 


 

순환알고리즘을 설계하는데에 있어서 암시적 매개변수를 명시적 매개변수로 바꾸는 것이 중요하다.

+ Recent posts