IT로 세상을 이롭게

1. 시간 복잡도 vs 공간 복잡도

일반적인 용어 정리에 따르면 다음과 같습니다.

- 시간 복잡도(Time Complexity) : 알고리즘의 수행시간

- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량

시간복잡도와 공간복잡도는 소프트웨어를 만드는 사람이라면 빼놓을 수 없는 문제입니다.

위의 그래프는 각 알고리즘 간의 수행속도에 대해서 비교하고 있습니다. 데이터가 적으면 큰 차이가 나지 않지만 (오히려 전후처리 때문에 시간복잡도가 더 좋지만 느려지는 경우도 있습니다.) 많아질 수록 수행시간은 어마어마한 차이가 발생합니다.

수천건의 데이터의 경우 N log N 과 N^2 상에 큰 차이가 발생하지 않지만 수십만 단위로 넘어가게 되면 응답을 받을 수 없게 됩니다.

공간복잡도는 쉽게 메모리의 사용량이며 시간복잡도와는 trade-off 의 관계로 알려져있지만 잘 짜여져 있는 알고리즘에서는 시간복잡도와 공간복잡도를 모두 잡는 경우도 간혹 볼 수 있습니다.

시간복잡도가 높은 연산은 최소화 하는 것이 사용자 응답속도를 빠르게 하는데 도움이 됩니다.

2. 문자열 처리

어떤 문자열의 길이를 체크하는 알고리즘은 시간복잡도가 얼마일까요? 

O(N) 입니다. 끝까지 가보면 압니다.

그렇다면 어떤 문자열이 허용하는 문자로 구성되어 있는지, 예를 들어서 영문소문자 + 특수문자 ('-',',' 등) 로 이루어져있는지 체크하려면 어떻게 해야할까요? 

우리는 일반적으로 정규표현식을 사용해서 문제를 해결합니다. 정규표현식의 시간복잡도는 얼마일까요?

음.. 자세히는 몰라도 O(N)보다는 클 것 같습니다. (정규표현식은 기본적으로 모든 케이스를 시도해보는 백트래킹에 기반하고 있습니다.)

사용자로부터 입력을 받았을때 매번 정규표현식으로 문자열을 판단한다면 시간이 더 걸릴 것 같습니다.

(사실... 문자열은 대부분 길지 않기 때문에 큰 영향은 없습니다.^^;; ) 

3. 알고리즘 문제해결 접근법

알고리즘 문제를 많이 풀어보신 분들은 느껴보셨을 겁니다. 주어진 문제상황을 그대로 구현하면 100% Time Over가 발생하는 것을...

제약조건과 주어진 문제상황을 보다 간결하게 정리하게 크게 분류할 수 있는 기본로직을 세운 뒤, 최적화 알고리즘을 적절히 사용하여 구현하는 것이 일반적인 풀이입니다. 정리해보면 다음과 같습니다.

- 주어진 제약, 조건, 로직 이해

- 시간복잡도 / 공간복잡도 분석

- 새로운 문제로 (재분류, 대전제, 기본로직) 재정의

- 해당 문제에 적합한 알고리즘 사용 및 구현

- 결과에 대한 검증

4. 비지니스 요건에 접근할 때

다음과 같은 상황이 주어진다면?

<요건>

- 사용자가 서비스를 등록한다.

- 서비스는 고유 Id가 존재한다.

- 각 서비스를 구분할 수 있는 서비스명이 존재한다.

- 서비스명은 영문소문자로만 20자이하로 구성된다.

- 각 서비스를 구분할 수 있는 서비스코드가 존재한다.

- 서비스 코드는 영문소문자 + '-'  20자이하로 구성된다.

- 서비스에 대한 설명을 100자 이내로 작성할 수 있다.

<제약사항>

- 서비스명과 서비스코드는 반드시 입력되어야 한다.

- 서비스명과 서비스코드는 공백을 허용하지 않는다.

- 서비스명과 서비스코드는 트림처리가 되어야 한다.

- 서비스설명은 공백을 허용한다.

- 서비스명과 서비스코드는 반드시 영문소문자로 시작한다.

이와 같이 단순하게 요건을 나열된 그대로 구현하게 되면 소스코드는 상당히 지저분하게 됩니다. 그리고 변경이 발생했을 때 유지보수성도 떨어지며 속도에도 영향을 미치게 됩니다.

(번외로 알고리즘 공부하다보면 발견하게 되는 것 중에... 소스가 지저분하고 라인이 점점 길어진다면?  매우 높은 확률로 오답입니다 ㅜㅜ )

5. 접근방법

<예시코드>

if(StringUtils.isEmpty(serviceDto.getServiceName())){
            // error
}else{
      if(StringUtils.containsWhitespace(serviceDto.getServiceName())){
            serviceDto.setServiceName(StringUtils.replace(serviceDto.getServiceName()," ",""));
            serviceDto.setServiceName(serviceDto.getServiceName().trim());
      }
}

if(StringUtils.isEmpty(serviceDto.getServiceCode())){
            // error
}else {
      if(StringUtils.containsWhitespace(serviceDto.getServiceCode())){
            serviceDto.setServiceCode(StringUtils.replace(serviceDto.getServiceCode()," ",""));
            serviceDto.setServiceCode(serviceDto.getServiceCode().trim());
      }
}

새로운 컬럼이 늘어날때마다 if-else가...;; 계속 추가됩니다..

임시방편으로 trim에 대한 로직을 DTO내의 setter로 옮길 수 있지만, 기본적인 로직이 정리되지 않은 상태라 근원적인 해결이 되지는 않습니다. 결국 해당 로직은 여러 DTO로 각각 흩어져서 유지보수가 어려워 지는 것은 똑같습니다.

요구사항을 바로 구현하는 습관을 버려야 합니다.

오랜 시간동안 요구사항을 읽고 이해한 뒤, 다시 재구성해야 합니다.

또한 로직을 구성할 때에는 반드시 대, 중, 소 로 접근하여 최대한 간결하게 (중복없이, 누락없이) 정리해야 합니다.

위의 상황을 제가 이해한 모양으로 다시 정리해보면 다음과 같습니다.

- 컬럼은 필수 / 선택으로 나누어진다. 필수컬럼의 경우 허용하는 문자에 대해서 패턴이 존재한다.

- 트림은 문자의 패턴에 따라서 처음이나 마지막에 공백이 올수 없음을 의미한다.

- 반드시 입력되어야 하는 값이라면 문자의 패턴은 최소길이는 1로 표현가능하다.

- 서비스명 과 서비스코드는 필수컬럼이다.

- 서비스명의 문자패턴은 영문소문자(1글자) + 영문소문자(1 ~ 19글자)

- 서비스코드의 문자패턴은 영문소문자(1글자) + 영문소문자와 '-' (1~19글자)

- 패턴은 컬럼별로 다를 수 있다.

- 선택컬럼의 경우 허용하는 문자에 대한 패턴은 없다. 그러나 문자의 길이에 대해서는 조건이 존재할 수 있다.

- 서비스설명은 선택컬럼이다.

뭔가 훨씬 깔끔해진 느낌이 듭니다.

이부분이 제가 생각할 때 소프트웨어 구현에서 가장 중요한 단계입니다. 일반적으로 시니어 소프트웨어 개발자, 혹은 아키텍트들이 같이 해야하는 일입니다.

일반인이 이야기한 비지니스 요건을 본인이 이해한바로 잘 정리하여 문제를 재구성하여 소프트웨어로 만들 수 있도록 정의 하는 것이 핵심입니다. 또한 문제해결을 위한 기본적인 알고리즘 (시간복잡도, 공간복잡도) 과 아키텍처가 설계되는 시점입니다.

6. 구현

 각 Layer에서 어떠한 Validation을 할것인지 정의합니다.

Repository에서는 Data의 무결성을 보장합니다. 일반적으로 Data의 무결성은 DBMS에서 담당하며 Network, File 등을 거쳐서 가야하기 때문에 비용이 가장 많이 듭니다.

역으로 Contoller 가 사용자와 가장 가까운 곳에 위치하고 있기 때문에 기본적인 것들은 여기서 걸러주는 것이 많이 도움이 됩니다.

기본적인 Validation 체크는 Controller 에서 수행하고 나머지 비지니스 로직에 대한 처리는 Service에서 합니다.

(이번 글에서는 편의상 Pattern이 비지니스의 의미를 가지고 있다고 가정했습니다만 Controller에서 처리하는 경우도 많습니다.)

 Controller Layer에서는 값의 표면적 형태에 대해서만 검증을 수행합니다.

기본적인 Length 체크만을 수행하며 위에서 언급한 것처럼 정규표현식은 시간복잡도가 높기 때문에 Contoller Layer를 정상적으로 통과한 경우에 대해서만 검증을 수행하는 것이 수행속도에도 유리하다고 판단했습니다.

@RestController
@RequestMapping(path="/api")
public class ServiceController {

    private Logger logger = LoggerFactory.getLogger(ServiceController.class);

    @Autowired
    private ServiceService serviceService;


    @RequestMapping(value="/services", method= RequestMethod.POST)
    public @ResponseBody
    ServiceDto createService (@AuthenticationPrincipal LoginUserDetails loginUserDetails,
                              @RequestBody @Valid ServiceDto service, HttpServletResponse response) throws DataFormatViolationException, ServiceAlreadyExistsException {

        // serviceCode 중복 체크 수행
        ServiceDto serviceDto = serviceService.findServiceByServiceCode(service.getServiceCode());
        if(serviceDto.checkAvailablePrimaryKey()) {
            throw new ServiceAlreadyExistsException(String.valueOf(service.getServiceCode()));
        }

        ServiceDto ret = serviceService.createService(service);
        response.setStatus(HttpServletResponse.SC_CREATED);
        return ret;
    }

체크로직을 구성할 때에도 컬럼별로 비교로직을 Contoller 내에서 구현하는 것보다는 Spring @Valid를 활용하였습니다.

어노테이션 기반으로 Dto검증을 수행하기 때문에 로직이 훨씬 간결해 집니다.

@Data
@Getter
@Setter
public class ServiceDto extends AbstractCommonTable implements ServiceInformation, UserInformation {

    private Integer serviceId;

    @Size(min=1,max=20)
    private String serviceName;

    @Size(min=1,max=20)
    private String serviceCode;

    @Size(min=0,max=100)
    private String description;

다음은 Service Layer입니다.

공통적인 로직을 Service Layer 에 두면 다른 REST API 나 Controller 활용할 때에도 별도로 검증로직을 추가하지 않아도 됩니다.

또한 값의 의미를 검증하는 부분은 비지니스와 연관성이 있다고 판단하였습니다.

먼저 서비스명과 서비스코드의 문자패턴을 정규표현식으로 나타냅니다.

문자패턴을 정규표현식으로 나타내면서 (시작문자,종료문자,트림,길이 등) 에 대한 처리를 합니다.

public class ValidationPattern {
    public final static Pattern serviceNamePattern = Pattern.compile("(^[a-z][a-z0-9]{1,19}$)");
    public final static Pattern serviceCodePattern = Pattern.compile("(^[a-z][a-z0-9-]{1,19}$)");
}

이후 해당 패턴을 이용하여 검증하는 로직을 구현합니다.

@Service
public class ServiceService {
    @Autowired
    private ServiceRepository serviceRepository;

    @Autowired
    private ModelMapper modelMapper;
    
	 public ServiceDto createService(ServiceDto serviceDto) throws DataFormatViolationException {

        String serviceCode = serviceDto.getServiceCode();
        checkServiceCode(serviceCode);

        ServiceEntity serviceEntity =modelMapper.map(serviceDto, ServiceEntity.class);
        serviceRepository.save(serviceEntity);
        return modelMapper.map(serviceEntity, ServiceDto.class);
    }
    
    private void checkServiceCode(String serviceCode) throws DataFormatViolationException {

        if(serviceCode == null){
            throw new DataFormatViolationException("Code value should be not null");
        }else{
            Pattern codePattern = ValidationPattern.serviceCodePattern;
            Matcher matcher = codePattern.matcher(serviceCode);

            if(!matcher.matches()){
                throw new DataFormatViolationException("Code value should be consist of alphabet lowercase, number and '-', (length is from 2 to 20)");
            }
        }
    }

7. 결론

두서없이 쓰다보니 글의 요점이 모호해진 것 같습니다.

정리해보면...

- 어떠한 문제를 해결하기 위해서 바로 코딩으로 뛰어들어서는 안된다.

- 문제를 재해석하여 나만의 방식으로 표현하고 시간복잡도 / 공간복잡도 를 정리한다.

- 로직은 최대한 간결하게!  대/중/소, 중복없이, 누락없이!

- MVC 의 경우 각 Layer의 하는 일들이 나누어져 있다.

- 만약 시간복잡도가 높은 연산이 있다면 이러한 연산은 최소한으로 해주는 것이 좋고, 이러한 필터링을 각 Layer별로 해주면 효과적이다.

- 유지보수성 과 유연성은 반드시 따라오는 덤! 

<참고사이트>

https://ledgku.tistory.com/33

http://www.secmem.org/blog/2019/02/10/a-comprehensive-guide-to-regex/

<개요>

- 일반적인 Web MVC구조에 따라서 Service 등록/수정/삭제/조회 하는 REST API를 만든다고 가정합니다.

<내용>

가장 단순한 건당 조회를 살펴봅니다.

Controller 클래스 입니다.

@RestController
@RequestMapping(path="/api")
public class ServiceController {

    
    @RequestMapping(value="/services/{serviceId}", method= RequestMethod.GET)
    public @ResponseBody
    ServiceDto findService (@AuthenticationPrincipal LoginUserDetails loginUserDetails,
                            @PathVariable("serviceId") int serviceId) throws ServiceNotFoundException {
        // @ResponseBody means the returned String is the response, not a view name
        // @RequestParam means it is a parameter from the GET or POST request

        ServiceDto serviceDto = getServiceByServiceId(serviceId, loginUserDetails);
        return serviceDto;
    }

    private ServiceDto getServiceByServiceId(int serviceId, LoginUserDetails loginUserDetails) throws ServiceNotFoundException {
        ServiceDto serviceDto =  serviceService.findServiceById(serviceId);
        if(     (serviceDto == null) ||
                loginUserDetails.checkNotAvailableService( serviceDto.getServiceId()) ||
                StringUtils.isEmpty(serviceDto.getServiceId())){
            throw new ServiceNotFoundException(String.valueOf(serviceId));
        }
        return serviceDto;
    }

- LoginUserDetails 의 경우 로그인한 사용자의 정보를 저장합니다.
- serviceId를 이용하여 데이터를 조회하고 결과값을 간단하게 검증하는 로직입니다.

- 결과값이 다음 중 하나와 같으면 현재 Service가 존재하지 않는 것으로 판단합니다.

 1. 객체가 null 인 경우

 2. ID필드의 값이 없는 경우

 3. 값이 존재하나 로그인한 사용자의 정보에 해당하지 않는(본인의 서비스가 아닌 경우) 경우

이와 같이 Service 를 조회하고 값을 검증하는 로직은 조회 이외에 등록/수정에서도 필요하기 때문에 별도 메소드를 작성하여 재사용하였습니다.

그리고 현재 ServiceId와 로그인 사용자의 ServiceId를 비교하는 로직의 경우 Controller에서 구현하는 것보다는 정보은닉화와 설계원칙에 적합해 보여서 LoginUserDetails 내부에 구현하였습니다.

좀더 자세히 살펴보겠습니다.

public class LoginUserDetails extends User {

    private static String ROLE_ADMIN = "ROLE_ADMIN";

    private Integer userId;

    private Collection<Integer> services;

    public LoginUserDetails(Integer userId,
                            String password,
                            String userName,
                            Collection<? extends GrantedAuthority> authorities,
                            Collection<Integer> services){
        super(userName, password, authorities);
        this.services = services;
        this.userId = userId;
    
    
    public boolean checkNotAvailableService(Integer serviceId){

        if(this.getAuthorities().contains(new SimpleGrantedAuthority(ROLE_ADMIN)) ){
            return false;
        }

        for(Integer eachService : this.services){
            if(eachService.equals(serviceId)){
                return false;
            }
        }
        return true;
    }

이와 같이 구현하면 현재 사용자의 serviceId등은 외부로 노출시키지 않아도 되며 (getter를 작성하지 않아도 됩니다.)

값의 검증이 필요한 모듈은 LoginUserDetails 객체에 요청하기만 하면 됩니다.

Controller layer의 경우 web과 바로 연결되어 있는 부분들을 담당하기 때문에 login관련정보나 인자값을 주로 처리하며 비지니스 로직은 Service Layer에 존재하게 됩니다.

다음으로 Service Layer를 살펴보겠습니다.

@Service
public class ServiceService {
    @Autowired
    private ServiceRepository serviceRepository;

    @Autowired
    private ModelMapper modelMapper;

    public ServiceDto findServiceById(int id){
        ServiceEntity serviceEntity = serviceRepository.findById(id);
        return modelMapper.map(serviceEntity, ServiceDto.class);
    }

지금은 아무 로직이 없기 때문에 단순히 Repository 로부터 값을 조회하여 객체의 값을 매핑만 합니다.

 현재 프로젝트에서는 Spring JPA를 사용하여 시스템을 구축중인데, Entity클래스의 변경은 되도록 줄이는 것이 좋습니다. 만약 Entity 클래스 하나의 유형으로 화면 - 서비스 - 데이터를 모두 처리하게 될 경우 객체지향에서 말하는 대표적인 anti pattern이 될 수 있기 때문에 별도 DTO 클래스를 사용합니다.

@Data
@Getter
@Setter
public class ServiceDto {

    private Integer serviceId;

    private String serviceName;

    private String serviceCode;

    private ServiceType serviceType;

    private String description;

    private LocalDateTime creationDateTime;

    private LocalDateTime modificationDateTime;

    private Integer userId;

    private UserEntity user;

}

<정리>

- Layer는 일반적으로 자신과 연결되어 있는 부분에 대해서만 인터페이스 하는 것이 원칙입니다.

- Controller Layer에서는 실제 데이터 베이스 저장에 대해서 알 필요가 없으며

- Service Layer에서는 Web기술에 대해서 알 필요가 없고

- Repository Layer는 온전히 데이터의 저장만을 담당합니다.

다음시간에는 조금 더 자세한 케이스를 다뤄보겠습니다.