posted by 귀염둥이채원 2019. 3. 28. 16:05

# DAO(Data Access Object)
- Database의 data에 접근을 위한 객체
- Database에 접근을 하기위한 로직과 비즈니스 로직을 분리하기 위해서 사용
- DB를 사용해 데이터를 조화하거나 조작하는 기능을 전담하도록 만든 오브젝트
- Service와 DB를 연결하는 고리의 역할을 한다
- DAO의 경우는 DB와 연결할 Connection 까지 설정되어 있는 경우가 많음

# DAO 클래스

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.SQLException;

public class TestDao {
    public void add(TestDto dto) throws ClassNotFoundException, SQLException {
        Class.forName("com.mysql.jdbc.Driver");
        Connection connection = DriverManager.getConnection("jdbc:mysql://localhost/test", "root", "root");

        PreparedStatement preparedStatement = connection.prepareStatement("insert into users(id,name,password) value(?,?,?)");

        preparedStatement.setString(1, dto.getName());
        preparedStatement.setInt(2, dto.getValue());
        preparedStatement.setString(3, dto.getData());
        preparedStatement.executeUpdate();
        preparedStatement.close();
        
        connection.close();
    }
}


# DTO((Data Transfer Object)
- DB에서 데이터를 얻어 Service나 Controller 등으터 보낼 때 사용하는 객체
- 로직을 갖고 있지 않는 순수한 데이터 객체이며 속성과 그 속성에 접근하기 위한 getter, setter 메소드만 가진 클래스

# DTO 클래스

public class TestDto {

    private String name;
    private int value;
    private String data;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }
}


# VO(Value Object) vs DTO
- VO는 DTO와 동일한 개념이지만 read only 속성을 갖는다.
- VO는 특정한 비즈니스 값을 담는 객체이고, DTO는 Layer간의 통신 용도로 오고가는 객체를 말한다.

# 참고 사이트
https://jungwoon.github.io/common%20sense/2017/11/16/DAO-VO-DTO/
https://gmlwjd9405.github.io/2018/12/25/difference-dao-dto-entity.html
https://lemontia.tistory.com/591
https://lazymankook.tistory.com/30

'Spring Boot' 카테고리의 다른 글

스프링부트 로그 설정  (0) 2019.03.29
[Spring Boot] MyBatis + Mysql 샘플2  (0) 2019.03.29
[Spring Boot] MyBatis + Mysql 샘플  (0) 2019.03.29
스프링 MVC 패턴이란?  (0) 2019.03.28
WEB MVC HelloWorld  (0) 2019.03.28
posted by 귀염둥이채원 2019. 3. 28. 15:16

# MVC 패턴이란?
- 어플리케이션의 Model, View, Controller의 영역으로 구분해서 결합도를 최소화한 패턴
- 유지보수가 쉽도록 중복 코드의 작성을 최소화 하고 기존 코드의 재사용을 높임
  - 역할을 세분화, 의존성 최소화

Model: 비즈니스 로직 및 데이터 처리 담당
View: 모델이 처리한 결과 데이터를 가지고 화면 생성 (사용자에게 보여주는 인터페이스)
Controller: 요청 처리 및 흐름 제어 담당 (비지니스 로직과 모델의 상호동작을 제어)

Model
* 애플리케이션의 상태(data)를 나타낸다.
* 일반적으로 POJO로 구성된다.
* Java Beans

View
* 디스플레이 데이터 또는 프리젠테이션
* Model data의 렌더링을 담당하며, HTML ouput을 생성한다.
* JSP
* JSP 이외에도 Thymeleaf, Groovy, Freemarker 등 여러 Template Engine이 있다.

Controller
* View와 Model 사이의 인터페이스 역할
* Model/View에 대한 사용자 입력 및 요청을 수신하여 그에 따라 적절한 결과를 Model에 담아 View에 전달한다.
* 즉, Model Object와 이 Model을 화면에 출력할 View Name을 반환한다.
* Controller —> Service —> Dao —> DB
* Servlet

# Spring MVC 웹 튜토리얼
https://penthegom.tistory.com/12

# 스프링부트 뷰: JSP, Velocity, JSP 샘플 구현
http://millky.com/@origoni/post/1144

# Spring MVC and Spring Boot Structure 디렉토리 구조
https://gmlwjd9405.github.io/2019/01/05/spring-directory-structure.html

# MVC Architecture
https://gmlwjd9405.github.io/2018/11/05/mvc-architecture.html

# Spring MVC Framework란?
https://gmlwjd9405.github.io/2018/12/20/spring-mvc-framework.html

# 스프링 MVC 관련
https://gmlwjd9405.github.io/2018/11/05/mvc-architecture.html
https://gangzzang.tistory.com/entry/%EC%8A%A4%ED%94%84%EB%A7%81Spring-MVC-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%ACModel-View-Controller-Framework-1
https://hunit.tistory.com/189
https://addio3305.tistory.com/41
https://jeong-pro.tistory.com/96
https://min-it.tistory.com/7

# 유투브
https://www.youtube.com/watch?v=qSQnwjb6TwU
https://www.youtube.com/watch?v=hJhIV6wky8g

'Spring Boot' 카테고리의 다른 글

스프링부트 로그 설정  (0) 2019.03.29
[Spring Boot] MyBatis + Mysql 샘플2  (0) 2019.03.29
[Spring Boot] MyBatis + Mysql 샘플  (0) 2019.03.29
DAO, DTO, VO란?  (0) 2019.03.28
WEB MVC HelloWorld  (0) 2019.03.28
posted by 귀염둥이채원 2019. 3. 28. 14:27

1. 스프링부트 프로젝트 생성

 

2. pom.xml 파일에 jstl, tomcat-embed-jasper dependency 추가

 

3. HelloController.java 파일 생성

@Controller
public class HelloController {

	@RequestMapping("/")
	public String hello(Model model) {
		model.addAttribute("name", "홍길동");
		return "hello";
	}
}

4. application.properties 파일에 view 설정 추가

spring.mvc.view.prefix=/WEB-INF/jsp/
spring.mvc.view.suffix=.jsp

 

5. hello.jsp 파일 생성

- webapp 폴더 밑에 WEB-INF/jsp 폴더 생성 후에 hello.jsp 파일 생성

<%@ page language="java" contentType="text/html; charset=EUC-KR"
    pageEncoding="EUC-KR"%>
<!DOCTYPE html>
<html>
<head>
<meta charset="EUC-KR">
<title>Insert title here</title>
</head>
<body>
	hello world ${name}
</body>
</html>

 

6. 스프링부터 어플리케이션 실행 및 확인

http://localhost:8080/

 

참고: https://www.youtube.com/watch?v=7ZDW5gOIJKs

'Spring Boot' 카테고리의 다른 글

스프링부트 로그 설정  (0) 2019.03.29
[Spring Boot] MyBatis + Mysql 샘플2  (0) 2019.03.29
[Spring Boot] MyBatis + Mysql 샘플  (0) 2019.03.29
DAO, DTO, VO란?  (0) 2019.03.28
스프링 MVC 패턴이란?  (0) 2019.03.28
posted by 귀염둥이채원 2019. 3. 27. 21:30

# Annotation이란?
- @를 이용한 주석, 자바코드에 주석을 달아 특별한 의미를 부여한 것
  (참고로 클래스, 메소드, 변수 등 모든 요소에 선언이 가능)
- 메타데이터(실제데이터가 아닌 Data를 위한 데이터) 라고도 불리고 JDK5부터 등장
컴파일러가 특정 오류를 억제하도록 지시하는 것과 같이 프로그램 코드의 일부가 아닌 
  프로그램에 관한 데이터를 제공, 코드에 정보를 추가하는 정형화된 방법.
ex) @Repository, @Service, @Controller, @Autowired, @Resource

# Annotation이 나온 이유
IT가 발전하면서 프로그램의 규모가 방대해지면서 XML이 가지는 설정정보의 양이 많아진다
--> Annotation은 직관적인 메타데이터 설정이 가능. 왜냐하면 소스코드와 같이 쓰기 때문에 
      (소스코드와 메타데이터가 결합되는 형태)
--> 시스템 전반에 영향을 주는 메타데이터는 XML로 설정하여 코드로부터 독립적으로 분리되는 것이 바람직하다. 

그래서 변경사항이 있을 때 유지보수성이 높아진다. 
설계시 확정되는 부분은 Annotation 기반 설정으로 개발의 생산성을 향상 시키는 것이 바람직함

# Annotation 사용시 장점
데이터에 대한 유효성 검사조건을 어노테이션을 사용하여 Model 클래스에 직접 명시함으로써 
해당 데이터들에 대한 유효 조건을 쉽게 파악할수 있게되며, 코드의 양도 줄어든다. 
(코드가 깔끔해지고, 어노테이션의 재사용도 가능해진다. )

########################################
# 주요 Annotation
########################################
@SpringBootApplication
- @Configuration, @EnableAutoConfiguration, @ComponentScan 3가지를 하나의 애노테이션으로 합친 것이다.

# @ComponentScan
- @Component와 @Service, @Repository, @Controller, @Configuration이 붙은 클래스 Bean들을 찾아서 Context에 bean등록을 해주는 Annotation
ApplicationContext.xml에  이런식으로 xml에 bean을 직접등록하는 방법도 있고 위와 같이 애노테이션을 붙여서 하는 방법도 있음

base-package를 넣으면 해당 패키지 아래에 있는 컴포넌트들을 찾고 그 과정을 spring-context-버전(4.3.11.RELEASE).jar에서 처리한다.
@Component로 다 쓰지 왜 굳이 @Repository, @Service, @Controller등을 사용하냐면 예를들어 @Repository는 DAO의 메소드에서 발생할 수 있는 unchecked exception들을 스프링의 DataAccessException으로 처리할 수 있기 때문이다. 또한 가독성에서도 해당 애노테이션을 갖는 클래스가 무엇을 하는지 단 번에 알 수 있다.

xxx 패키지 하위에 @Component로 선언된 클래스를 bean으로 자동등록(bean 이름 : 해당클래스 이름, 첫글자 소문자)

@EnableAutoConfiguration
- 스프링 애플리케이션 컨텍스트를 만들 때 자동으로 설정하는 기능을 켠다.
classpath의 내용에 기반해서 자동 생성해준다. 만약 tomcat-embed-core.jar가 존재하면 톰캣 서버가 setting된다.

@Configuration
- Configuration을 클래스에 적용하고 @Bean을 해당 클래스의 메소드에 적용하면 @Autowired로 빈을 부를 수 있다.

@Required
- setter 메서드에 적용해주면 빈 생성시 필수 프로퍼티 임을 알린다.

@Qualifier("id123")
- @Autowired와 같이 쓰이며, 같은 타입의 빈 객체가 있을 때 해당 아이디를 적어 원하는 빈이 주입될 수 있도록 하는 애노테이션
(같은 타입이 존재하는 경우 ex) 동물, 원숭이, 닭, 개, 돼지)

@Resource
- @Autowired와 마찬가지로 빈 객체를 주입해주는데 차이점은 Autowired는 타입으로, Resource는 이름으로 연결해준다.

@PostConstruct, @PreConstruct
- 의존하는 객체를 생성한 이후 초기화 작업을 위해 객체 생성 전/후에(pre/post) 실행해야 할 메소드 앞에 붙인다.

@PreDestroy
- 객체를 제거하기 전(pre)에 해야할 작업을 수행하기 위해 사용한다.

@PropertySource
- 해당 프로퍼티 파일을 Environment로 로딩하게 해준다.
클래스에 @PropertySource("classpath:/settings.properties")라고 적고 클래스 내부에 @Resource를 Environment타입의 멤버변수앞에 적으면 매핑된다.

@ConfigurationProperties
- yaml파일 읽는다. default로 classpath:application.properties 파일이 조회된다.
속성 클래스를 따로 만들어두고 그 위에 (prefix="mail")을 써서 프로퍼티의 접두사를 사용할 수 있음

mail.host = mailserver@mail.com
mail.port = 9000
mail.defaultRecipients[0] = admin@mail.com
mail.defaultRecipients[1] = customer@mail.com

@Value
- properties에서 값을 가져와 적용할 때 사용한다.

@Value("${value.from.file}")
private String valueFromFile; 이라고 구성되어 있으면 value.from.file의 값을 가져와서 해당 변수에 주입해준다.

@RequestMapping
- 요청 URL을 어떤 메서드가 처리할지 mapping해주는 애노테이션이다.

컨트롤러나 컨트롤러의 메서드에 적용한다.
@RequestMapping("/list"), @RequestMapping("/home, /about");
@RequestMapping("/admin", method=RequestMethod.GET)

@GetMapping
- @RequestMapping(Method=RequestMethod.GET)과 같음
@PostMapping, @PutMapping, @PatchMapping, @DeleteMapping은 유추 가능함.

@RequestAttribute
- Request에 설정되어 있는 속성 값을 가져올 수 있다.

@RequestBody
- 요청이 온 데이터(JSON이나 XML형식)를 바로 클래스나 model로 매핑하기 위한 애노테이션

@RequestHeader
- Request의 header값을 가져올 수 있다. 메소드의 파라미터에 사용
@RequestHeader(value="Accept-Language")String acceptLanguage 로 사용 //ko-KR,ko;q=0.8,en-US;q=0.6

@RequestParam
- @PathVariable과 비슷하다. request의 parameter에서 가져오는 것이다. 메소드의 파라미터에 사용됨

@RequestPart
- Request로 온 MultipartFile을 바인딩해준다.
@RequestPart("file")MultipartFile file로 받아올 수 있음.

@ResponseBody
- view가 아닌 JSON 형식의 값을 응답할 때 사용하는 애노테이션으로 문자열을 리턴하면 그 값을 http response header가 아닌 response body에 들어간다.
만약 객체를 return하는 경우 JACKSON 라이브러리에 의해 문자열로 변환되어 전송된다.
context에 설정된 resolver를 무시한다고 보면된다. (viewResolver)

@PathVariable
- 메서드 파라미터 앞에 사용하면서 해당 URL에서 {특정값}을 변수로 받아 올 수 있다.

@ExceptionHandler(ExceptionClassName.class)
- 해당 클래스의 예외를 캐치하여 처리한다.

@ControllerAdvice
- 클래스 위에 ControllerAdvice를 붙이고 어떤 예외를 잡아낼 것인지는 각 메소드 상단에 @ExceptionHandler(에외클래스명.class)를 붙여서 기술한다.

@RestControllerAdvice
- 문법적 설탕으로 @ControllerAdvice + @ResponseBody다.

@ResponseStatus
- 사용자에게 원하는 response code와 reason을 리턴해주는 애노테이션
@ResponseStatus(value = HttpStatus.NOT_FOUND, reason = "my page URL changed..") => 예외처리 함수 앞에 사용한다.

@EnableEurekaServer
- Eureka 서버로 만들어준다.

@EnableDiscoveryClient
- Eureka 서버에서 관리될 수 있는 클라이언트 임을 알려주기위한 애노테이션

@Transactional
- 데이터베이스 트랜잭션을 설정하고 싶은 메서드에 애노테이션을 적용하면 메서드 내부에서 일어나는 데이터베이스 로직이 전부 성공하게되거나 데이터베이스 접근중 하나라도 실패하면 다시 롤백할 수 있게 해주는 애노테이션
@Transaction(readOnly=true, rollbackFor=Exception.class) : readOnly는 읽기전용임을 알리고 rollbackFor는 해당 Exception이 생기면 롤백하라는 뜻
@Transaction(noRollbackFor=Exception.class)는 해당 Exception이 나타나도 롤백하지 말라는 뜻
@Transaction(timeout = 10)은 10초안에 해당 로직을 수행하지 못하면 롤백하라는 뜻.

########################################
# Bean 등록 Annotation
########################################
@Component
컴포넌트를 나타내는 일반적인 스테리오 타입으로  태그와 동일한 역할을 함
@Controller, @Service , @Repository를 다 포함하고 있다.

@Repository
퍼시스턴스 레이어, 영속성을 가지는 속성(파일, 데이터베이스)을 가진 클래스

@Service
서비스 레이어, 비지니스 로직을 가진 클래스

@Controller
프리젠테이션 레이어, 웹 어플리케이션에서 웹 요청과 응답을 처리하는 클래스

-> @Repository, @Service, @Controller는 더 특정한 유즈케이스에 대한 @Component의 구체화된 형태

########################################
# Bean 의존관계 주입 Annotation
########################################
@Autowired, @Resource annotation은 의존하는 객체를 자동으로 주입해주는 annotation이다

@Autowired
정밀한 의존관계 주입이 필요한 경우에 유용.
@Autowired는 프로퍼티, setter 메서드, 생성자, 일반 메서드에 적용 가능.
의존하는 객체를 주입할 때 주로 Type을 이용
@Autowired는 ,  태그와 동일한 역할.

@Resource
어플리케이션에서 필요로 하는 자원을 자동 연결할 때 사용
@Resource는 poperty, setter 메서드에 적용 가능
의존하는 객체를 주입할 때 주로 Name을 이용

@Value
단순한 값을 주입할 때 사용되는 annotation.
@Value("Spring")은 와 동일한 역할

@Qualifier
@Qualifier는 @Autowired annotation과 같이 사용.
@Autowired는 타입으로 찾아서 주입하므로, 동일 타입의 Bean 객체가 여러 개 존재할 때 특정 Bean을 찾기 위해 사용

########################################
# 참고 사이트
########################################
https://zeroturnaround.com/rebellabs/spring-framework-annotations-cheat-sheet/
https://zetawiki.com/wiki/%EC%8A%A4%ED%94%84%EB%A7%81_%EC%95%A0%EB%84%88%ED%85%8C%EC%9D%B4%EC%85%98
http://blog.naver.com/PostView.nhn?blogId=wwwkang8&logNo=220994093310
https://jeong-pro.tistory.com/151
https://cornswrold.tistory.com/8
https://gmlwjd9405.github.io/2018/12/02/spring-annotation-types.html
https://smallgiant.tistory.com/11
https://s262701-id.tistory.com/91
https://lalwr.blogspot.com/2018/04/spring-annotation.html
https://blog.hanumoka.net/2018/07/20/spring-20180720-Spring-MVC-Annotation/

https://kdyang.tistory.com/54

' Spring Framework' 카테고리의 다른 글

Spring Bean이란?  (0) 2019.03.27
롬복(lombok)이란?  (0) 2019.03.27
posted by 귀염둥이채원 2019. 3. 27. 20:18

스프링 컨테이너(Spring Container)에 의해서 자바 객체가 만들어 지게 되면 이 객체를 스프링 빈이라고 한다.
스프링 빈과 자바 일반 객체와의 차이점은 없고, 스프링 컨테이너에서 만들어지는 객체를 스프링 빈이라고 부른다.

Bean이란 인스턴스생성, 관리, 컨테이너에 의해 관리되는 객체이다.
(개발자가 직접 생성하는 객체는 Bean이 아니다) 

즉, new 객체를 사용하는 방식은 스프링 컨테이너에서 관리를 하지 않는다.
MyBean bean1 = new MyBean()

# 스프링 레퍼런스 메뉴얼

In spring, the objects that form the backbone of your application and that are managed by the Spring IoC container are called beans.
스프링 IoC(Inversion of Control) 컨테이너에 의해서 관리되고 애플리케이션의 핵심을 이루는 객체들을 스프링에서는 빈즈(Beans)라고 부른다.

A bean is an object that is instantiated, assembled, and otherwise managed by a Spring Ioc container.
빈은 스프링 Ioc 컨테이너에 의해서 인스턴스화되어 조립되거나 관리되는 객체를 말합니다.

Otherwise, a bean is simply one of many objects in your application. 
이같은 점을 제외하고 빈은 수많은 객체들중의 하나일 뿐입니다.

Beans, and the dependencies among them, are reflected in the configuration metadata used by a container.
빈과 빈 사이의 의존성은 컨테이너가 사용하는 메타데이터 환경설정에 반영됩니다. 

# 참고 사이트
https://gmlwjd9405.github.io/2018/11/10/spring-beans.html
https://endorphin0710.tistory.com/93
https://lalwr.blogspot.com/2018/04/spring-bean-xml.html

' Spring Framework' 카테고리의 다른 글

# Spring Annotation(어노테이션)이란?  (0) 2019.03.27
롬복(lombok)이란?  (0) 2019.03.27
posted by 귀염둥이채원 2019. 3. 27. 18:16

롬복(lombok)이란 Java 기반에서 기계적으로 작성하는 VO, DTO, Entity 관련 작업을 보다 쉽게 하게 해주는 도구이다.
- Getter, Setter, ToString, hashCode 관련 메소드 자동 생성 가능
- Spring(SpringSTS) 프로젝트에서 사용할 경우 JPA 환경과 함께 일관화 되고 가독성이 좋은 애플리케이션을 작성 가능
- 단점은 협업 모든 인원이  lombok을 설치해야 한다는 것,  추가 어노테이션 사용할 경우 소스코드 분석이 난해해지는 것

# 롬복(lombok)이란?
https://countryxide.tistory.com/16
https://taetaetae.github.io/2017/02/22/lombok/
http://www.daleseo.com/lombok-popular-annotations/
http://wonwoo.ml/index.php/post/1607

# Lombok 사용상 주의점
http://kwonnam.pe.kr/wiki/java/lombok/pitfall

' Spring Framework' 카테고리의 다른 글

# Spring Annotation(어노테이션)이란?  (0) 2019.03.27
Spring Bean이란?  (0) 2019.03.27
posted by 귀염둥이채원 2019. 3. 18. 15:10

ansible에서는 split()을 사용하여 문자열을 분할이 가능하다.

split()은 jinja2 필터가 아니고, python 함수입니다.


# example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- hosts: all
  vars:
    test: "This single line should be split based on white space"
  tasks:
  - debug:
      msg: "{{ test.split() }}"
 
output
------
ok: [localhost] => {
    "msg": [
        "This"
        "single"
        "line"
        "should"
        "be"
        "split"
        "based"
        "on"
        "white"
        "space"
    ]
}
cs


# jinja2 filter

http://jinja.pocoo.org/docs/2.10/templates/#filters


# ansible filter

https://docs.ansible.com/ansible/latest/user_guide/playbooks_filters.html#playbooks-filters


# 참고 사이트

http://www.mydailytutorials.com/how-to-split-strings-and-join-them-in-a%E2%80%8Bnsibl%E2%80%8Be/

'Tool > ansible' 카테고리의 다른 글

ansible role template 생성하기  (0) 2019.02.01
ansible handler란?  (0) 2019.02.01
serial keyword를 이용한 rolling update  (0) 2019.01.29
ansible-vault를 이용한 암호화  (0) 2019.01.29
ansible source build  (0) 2019.01.29
posted by 귀염둥이채원 2019. 3. 14. 19:50

# 문제링크

https://www.acmicpc.net/problem/2357


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

https://palyoung.tistory.com/64


# 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class BOJ2357 {
    static int N, M;
    static int a, b;
    static int arr[], segMinArr[], segMaxArr[];
 
    static void init(int N) {
        segMinArr = new int[N*4];
        segMaxArr = new int[N*4];
        Arrays.fill(segMinArr, Integer.MAX_VALUE);
        Arrays.fill(segMaxArr, Integer.MIN_VALUE);
    }
    
    static int createMinTree(int arr[], int left, int right, int node) {
        if (left == right) return segMinArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMinArr[node] = Math.min(createMinTree(arr, left, mid, node*2), createMinTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMinQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MAX_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMinArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.min(getMinQuery(left, right, node*2, nodeLeft, mid), getMinQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    static int createMaxTree(int arr[], int left, int right, int node) {
        if (left == right) return segMaxArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMaxArr[node] = Math.max(createMaxTree(arr, left, mid, node*2), createMaxTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMaxQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MIN_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMaxArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.max(getMaxQuery(left, right, node*2, nodeLeft, mid), getMaxQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        init(N);
        createMinTree(arr, 0, N-11);
        createMaxTree(arr, 0, N-11);
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;
            
            sb.append(getMinQuery(a, b, 10, N-1+ " " +getMaxQuery(a, b, 10, N-1+ "\n");
        }
        System.out.println(sb.toString());
    }
}
cs


'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

[BOJ]10868. 최솟값  (0) 2019.03.13
[BOJ]2042. 구간 합 구하기  (0) 2019.03.13
posted by 귀염둥이채원 2019. 3. 13. 21:28

# 문제링크

https://www.acmicpc.net/problem/10868


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

https://palyoung.tistory.com/64


# 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ10868 {
    static int arr[];
    static int N, M;
    static int a, b;
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder("");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree segObj = new SegmentTree(arr, N);
        //segObj.print();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            sb.append(segObj.query(a-1, b-110, N-1+ "\n");
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long segmentArr[];
    
    SegmentTree(int arr[], int N){
        segmentArr = new long[N*4];
        Arrays.fill(segmentArr, Integer.MAX_VALUE);
        init(arr, 0, N-11);
    }
    
    long init(int arr[], int left, int right, int node) {
        if (left == right) return segmentArr[node] = arr[left];
        int mid = (left+right)/2;
        return segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));
    }
 
    long query(int sIdx, int eIdx, int node, int nodeLeft, int nodeRight) {
        if (sIdx > nodeRight || eIdx < nodeLeft) return Integer.MAX_VALUE;
        if (sIdx <= nodeLeft && eIdx >= nodeRight) return segmentArr[node];
        int mid = (nodeLeft + nodeRight)/2;
        return Math.min(query(sIdx, eIdx, node*2, nodeLeft, mid), query(sIdx, eIdx, node*2+1, mid+1, nodeRight)); 
    }
    
    void print() {
        for (int i=0; i<segmentArr.length; i++) {
            System.out.printf("%d, ", segmentArr[i]);
        }
        System.out.println();
    }
}
cs


# 회고

- segment tree 생성시 segmentArr에 초기값을 MAX로 설정해야한다.

  - Arrays.fill(segmentArr, Integer.MAX_VALUE);


자식이 있는 "부모노드"는 자식 노드들의 최솟값을 가지고 있어야 한다.

  - segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));

'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

최솟값과 최댓값  (0) 2019.03.14
[BOJ]2042. 구간 합 구하기  (0) 2019.03.13
posted by 귀염둥이채원 2019. 3. 13. 18:32

Segment Tree (구간 트리)는 일차원 배열에서 각각의 구간을 특정 기준으로 질의를 던지고 빠르게 답을 구할 수 있는 알고리즘이다.


# Segment Tree

- 이진 트리를 통해 표현 (대부분 full binary tree)

- 각 노드에는 구간에 대한 정보가 저장이 되어있는 트리

  - 자식이 있는 "부모노드"는 구간에 대한 정보를 가지고 있다.

  - 자식이 없는 "리프노드"는 하나의 정보만 가지고 있다.


# Segment Tree 유형 문제

- 하나의 (또는 연속된 구간) 값이 매번 변경되는 데이터의 구간합

- 하나의 값이 매번 변경되는 데이터의 최소값

- 하나의 값이 매번 변경되는 데이터의 최대값

- 하나의 값이 빈번히 변경되는 데이터의, 구간 정렬 값


# Segment Tree를 사용하는 이유?

배열 arr에 1,2,3,4,5가 있다고 하자.

arr[1]+arr[2]+arr[3]=9를 구하려면 O(N)이 걸린다.


arr[2]를 10으로 바꾸고 다시 arr[1]+arr[2]+arr[3]를 구해야한다면,

값을 바꾸는데 O(1), 구간의 합을 구하는데 O(N)이 걸린다.

M번 실행하게 되면 O(MN+M)의 시간이 걸린다.


Segment Tree를 사용하면,

값을 바꾸는 과정: O(lgN)

구간의 합을 구하는 과정: O(lgN)

M번 실행 O(MlgN + MlgN) -> O(MlgN)의 시간이 걸린다.


M = 100, N = 2^20이라고 가정하면

O(MN)에서는 100*2^20 = 10,000,000(대략)

O(MlgN)에서는 100*20 = 2,000으로 데이터와 반복수행이 잦아질수록 시간 복잡도 차이가 기하급수적으로 커진다.



※ 그림 추가 (세그먼트 트리 모양)



# Segment Tree의 전체 크기 구하기

N = 12일 때의 세그먼트 트리의 전체 크기(배열 사이즈 정하기)를 구하기 위해서는 

2^k로 12보다 바로 큰 값을 만들 수 있는 k를 찾아야한다. 

즉, k는 4이다.


그리고 난 뒤 2^k를 하면 16이 되고 16에 *2를 하면 우리가 원하는 세그먼트 트리의 크기를 구할 수 있다. 

이 과정이 귀찮다면 그냥 N * 4를하면(여기서는 48이 세그먼트 트리 크기가 될 것이다.)

메모리는 조금 더 먹지만, 편리하게 이용할 수 있다.


포인터로 동적할당을 통한 트리가 아닌 배열로 트리를 만들고 있다.

그 이유는 세그먼트 트리는 full binary tree에 가깝기에 배열에 모든 값들이 꽉꽉차서 올 가능성이 매우 높기때문에 포인터보다는 배열을 이용하게 된다.


# 초기화

구간의 합 또는 최대 그리고 최소값이든 특정 기준에 따라 구간의 값을 지정해주기 위해 트리를 만드는 과정이다.


# 질의처리

주어진 구간 트리에서 원하는 구간의 값을 물어볼때 답을 얻는 과정이다.


# 업데이트

일차원 배열의 값이 변경되는 경우이다.

배열의 특정 index의 값이 변경되면 구간 트리의 값도 변경된다.

하지만 변화의 차이 값을 가지고 루트부터 탐색하면 O(logN)으로 갱신이 가능하다.


# 관련 문제

[BOJ]2042번 구간 합 구하기

[BOJ]2357번 최대값,최소값


# 유투브 영상

https://www.youtube.com/watch?v=e6xnetirNN0&list=PLQ9c2GXvqNKyqrihVgiDJ0upU0pGyqUJy&index=5


# 참고 사이트

https://www.acmicpc.net/blog/view/9

https://www.crocus.co.kr/648

https://meylady.tistory.com/38

https://wondy1128.tistory.com/150

https://jin1ib.tistory.com/116