/ PT

21 02 27

주제 : 백트레킹, Mvc패턴

백트레킹이란

  • 어떤 노드의 유망성을 판단 후 노드가 유망하지 않다면 부모 노드로 돌아가
    다른 자식 노드를 찾는 방법

BaekJoon N과 M(1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력

3 1

예제 출력

1   
2  
3

예제 입력

4 3

예제 출력

1 2 3  
1 2 4  
1 3 2  
1 3 4  
1 4 2  
1 4 3  
2 1 3  
2 1 4  
2 3 1  
2 3 4  
2 4 1  
2 4 3  
3 1 2  
3 1 4  
3 2 1  
3 2 4  
3 4 1  
3 4 2  
4 1 2  
4 1 3  
4 2 1  
4 2 3  
4 3 1  
4 3 2

문제 분석

  • 중복되는 수를 제외한 모든 경우의수 탐색
  • 재귀사용, 방문한 노드 라면 다음 노드 탐색(유망성 검사)
  • 재귀함수임으로 기저조건(BaseCondition) 명시

코드


import java.io.*
import java.io.*
import java.util.StringTokenizer;

public class Main {

	public static int arr[];
	public static boolean visit[];
	public static StringBuilder sb = new StringBuilder();

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

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		arr = new int[M]; //수열을 담을 배열
		visit = new boolean[N]; // 특정 수가 사용되었는지 
		
		dfs(N, M, 0); 
		System.out.println(sb);
	}

	
	public static void dfs(int N, int M, int depth) {
		// 재귀함수임으로 기저조건(BaseCondition) 명시
		if(depth == M) { // m개까지 탐색을 완료하면 SB에 수열 저장
			for(int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			// 부모 노드로 돌아간다.
			return;
		}
		
		//1부터 n까지 사용되지않은 수를 찾아냄
		for(int i=0; i < N; i++) {
			if(!visit[i]){
				visit[i] = true;
				arr[depth] = i+1;
				dfs(N,M,depth+1);
				visit[i] = false;
			}
		}
	}
}

MVC1, MVC2, Spring Frame에서 MVC2 패턴

Alt text

  • 소프트웨어 디자인 패턴 중하나
  • M(Model) / V(View) / C(Controller)
    • Model : 내부 비지니스 로직을 처리하기 위한 역할을 할 것입니다. (DB 접근)
      • 처리되는 알고리즘, DB 와 상호작용(CRUD Create Read Update Delete), 데이터 등등..
    • View : 화면에 보여주기 위한 역할을 합니다. 컨트롤러 하위에 종속되어, 모델이나 컨트롤러가 보여주려고 하는 모든 필요한 것들을 보여줄 것입니다.
      • 최종 사용자에게 화면(UI)으로 보여줌
    • Controller : 데이터와 비즈니스 로직 사이의 상호 동작을 관리합니다. 즉, 모델과 뷰를 통제합니다. MVC 패턴에서 View와 Model이 직접적인 상호 소통을 하지 않도록 관리합니다.

MVC 패턴은 크게 MVC 1 패턴과, 스프링이 채택한 MVC 2 패턴으로 나눌 수 있습니다.

MVC1

At text

MVC1 패턴의 경우 View와 Controller를 모두 JSP가 담당하는 형태를 가집니다.
즉 JSP 하나로 유저의 요청을 받고 응답을 처리하므로 구현 난이도는 쉽습니다.

단순한 프로젝트에는 괜찮겠지만 내용이 복잡하고 거대해질수록 이 패턴은 힘을 잃습니다. JSP 하나에서 MVC 가 모두 이루어지다보니 재사용성도 매우 떨어지고, 읽기도 힘들어집니다. 즉 유지보수에 있어서 문제가 발생합니다.

MVC2

At text MVC2 패턴은 널리 표준으로 사용되는 패턴, 요청을 하나의 컨트롤러(Servlet)가 먼저 받습니다. 즉 MVC1과는 다르게 Controller, View가 분리되어 있습니다. 따라서 역할이 분리되어 MVC1패턴에서의 단점을 보완할 수 있습니다. 그러므로 개발자는 M, V, C 중에서 수정해야 할 부분이 있다면, 그것만 꺼내어 수정하면 됩니다. 따라서 유지보수에 있어서도 큰 이점을 가집니다.

Spring FramkeWork에서 MVC2 패턴

At text

  1. 요청이 들어오면 DispatcherServlet이 받고 요청내용을 HandlerMapping 에게 보냄
  2. HandlerMapping에서는 가장 적합한 Controller 찾음
  3. Controller 안에 적합한 메서드를 찾아 ModelAndView형식으로 return
  4. ViewResolver는 결과에 해당하는 jsp 리턴 후 클라이언트에게 jsp 응답
  5. http 관계 끊어짐

## References.
https://velog.io/@taesunny/HTTP2HTTP-2.0-%EC%A0%95%EB%A6%AC https://www.acmicpc.net/problem/15649