Algorithm In Architecture #3 (시간복잡도, 문제해결, MVC)
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별로 해주면 효과적이다.
- 유지보수성 과 유연성은 반드시 따라오는 덤!
<참고사이트>
http://www.secmem.org/blog/2019/02/10/a-comprehensive-guide-to-regex/