발자국남기기

서로소 집합 서로소 집합 자료구조 * 동작 과정 초기에는 각각의 노드가 하나의 집합 서로 다른 집합 부모가 자기 자신 더 큰 루트노드가 더 작은 루트노드를 가리키도록 하는 것을 일반적으로 관행처럼 사용 4의 부모를 1로 변경 마찬가지로 3의 부모를 2로 변경 현재 테이블은 부모 노드를 타내고 있지만 3번노드의 부모는 2이고, 2의 부모노드는 1이므로 결과적으로 3번 노드의 루트노드는 1번 노드이다. 따라서 3번 노드와 4번 노드는 연결되어 있음을 알 수 있음 ==> 같은 집합에 속함 {1, 2, 3, 4}와 {5, 6}은 서로소 관계에 있는 집합 * 연결성 * 기본적인 구현 방법 # 간단한 서로소 집합 알고리즘 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 ..

서블릿 종속성 제거 요청 파라미터 정보는 Map으로 넘기도록 하면 현재 구조에서는 Controller가 서블릿 기술을 몰라도 동작할 수 있다. request 객체를 Model로 사용하는 대신 별도의 Model 객체를 만들어서 반환하면 된다. 현재는 request객체 내부 저장소를 Model처럼 사용하고 있음. Controller가 서블릿 기능을 전혀 사용하지 않도록 변경해보자 뷰 이름 중복 제거 Controller 에서 지정하는 뷰 이름에 중복이 있음. Controller는 뷰의 논리 이름을 반환하고, Front Controller에서 이를 실제 위치로 처리하도록 단순화 Front Controller에서 처리하도록 만들면, 뷰의 폴더 위치가 변해도 Front Controller만 변경하면 되므로 훨씬 코..

현재 컨트롤러에서 뷰로 이동하는 부분에 중복이 존재한다. 이 부분을 분리하여 별도로 뷰를 처리하는 객체를 만들 것이다. 렌더링을 통해 view를 호출하는 MyView 클래스 새로운 컨트롤러 인터페이스 반환을 MyView로 반환 위와 같이 각 컨트롤러들을 구현하는데 새로운 MyView객체에 viewPath을 넣어 반환해주면 MyView에서 이를 처리해주는 것이다. 다른 컨트롤러도 위와 마찬가지로 작성 중복을 제거할 수 있다. FrontController 내부 구조만 리팩토링한 것이기 때문에 기능은 전과 똑같이 동작함

프론트 컨트롤러 패턴을 사용하지 않으면 공통 부분이 계속 중복되어 호출된다 프론트 컨트롤러를 도입하게 되면 공통부분을 컨트롤러 앞에서 처리하고 각 컨트롤러로 들어가게 되는 것이다 프론트 컨트롤러 서블릿 하나로 클라이언트의 요청을 받음 프론트 컨트롤러가 요청에 맞는 컨트롤러를 찾아서 호출 공통 처리 기능 프론트 컨트롤러를 제외한 나머지 컨트롤러는 서블릿을 사용하지 않아도 됨 스프링 웹 MVC의 핵심이 바로 FrontController 스프링 웹 MVC의 DispatcherServlet이 FrontController 패턴으로 구현되어 있음 FrontController 도입 컨트롤러 인터페이스를 만들고, 각 컨트롤러들이 이를 구현하도록 만들겠다. 컨트롤러 인터페이스 서블릿과 동일한 구조를 가지고 있음. 이를 ..

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의..

www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 무한 수열 A는 다음과 같다. A0 = 1 Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 3개의 정수 N, P, Q가 주어진다. 출력 첫째 줄에 AN을 출력한다. 제한 0 ≤ N ≤ 1012 2 ≤ P, Q ≤ 109 힌트 ⌊x⌋는 x를 넘지 않는 가장 큰 정수이다. 풀이 문제를 해결하는 점화식은 매우 간단하게 구현할 수 있다. 하지만 초기에 리스트를 통해 dp를 구현하였더니 메모리 초과가 발생하였다. 그래서 dictionary 중에 defaultdict을 사용..

하나의 서블릿이나 JSP만으로 비즈니스 로직과 뷰 렌더링까지 모두 처리하게 되면, 너무 많은 역할을 하게되고, 결과적으로 유지보수가 어려워진다. 비즈니스 로직을 호출하는 부분에 변경이 발생해도 해당 코드를 수정해야하고, UI를 변경할 일이 있어도 비즈니스 로직이 함께 있는 파일을 수정해야한다. 코드의 양이 수백 수천줄이라면 이 작업은 매우 어려워지고 복잡해진다. 변경의 라이프 사이클 둘 사이의 변경 라이프 사이클이 다르다는 점이다. UI를 일부 수정하는 일과 비즈니스 로직을 수정하는 일은 각각 다르게 발생할 가능성이 매우 높고 대부분 서로에게 영향을 주지 않는다. 이렇게 변경의 Life Cycle이 다른 부분을 하나의 코드로 관리하는 것은 유지보수하기에 좋지 않다. 기능 특화 JSP 같은 뷰 템플릿은 화..

먼저 JSP 라이브러리 추가 build.gradle에 아래 코드 추가하고 refresh jsp는 .java파일이 아니라 .jsp파일이므로 java폴더 밖에 만들어야함 jsp 파일에는 저 코드가 꼭 있어야한다. jsp파일이라는 의미 save.jsp에 회원 저장 로직이 들어갈 것이다. 전송을 눌러보면 아직 save.jsp를 만들지 않았기 때문에 Not Found가 뜬 것이지, URL은 제대로 전송된 것을 확인할 수 있음 save.jsp jsp도 결국 서블릿으로 변환되어 사용되는 것이기 때문에 request, response를 사용할 수 있음 위에 로직을 먼저 넣고 그 밑에 html을 배치하는 것이 일반적 다시 전송시켜보면 정상적으로 회원이 저장된 것을 확인할 수 있다. members.jsp (회원 목록 조회..

www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강..

www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 풀이 스택의 성질을 이용 import sys input = sys.stdin.readline n, k = map(int, input().s..