기억하고싶은것들

문자열 탐색 알고리즘

Rabin-Karp는 Hashing을 이용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다.

문자열에서 찾고자 하는 패턴의 길이만큼 hash값으로 변환하여, 패턴과 hash값이 같은지 확인을 하며

일치하지 않는 다면 한 칸씩 뒤로 이동하며 비교를 반복한다.

다만, hash값이 같다고 무조건 같은 패턴일 수는 없다.

그렇기 때문에 hash값이 같은 경우에는 문자열에 값과 패턴의 값을 일대일 매칭 하며 비교하는 과정도 필요하다.

기본적인 아이디어는 간단하다. 다만, 문자열을 이동하며 hash값을 계산해야 하는데 이 또한 효율적으로 찾을 수 있다. 

Rolling Hash

sliding window와 같이 문자열을 훑으면서 hash 값을 구하는데 유용하다.

주어진 문자열을 처음부터 끝까지 패턴과 비교하면서 해시값을 구하는데, 중복되는 부분의 해시값은 그대로 두고 업데이트되는 부분만 해시값을 계산해주어서 중복되는 연산을 줄일 수 있다.

위의 그림같은 경우에는 abec의 hash값 dece의 hash값을 구한다고 해보자

두 문자의 공통 부분인 dec는 그대로 두고 변경된 부분만 적용하면 된다.

우선 adec의 hash값은 

97*2^3 + 100*2^2 + 101*2^1 + 99*2^0 = 1477

다음으로 dece의 hash값은 아래와 같이 계산할 수 있다.

(1477 - 97*2^3) * 2 + 101*2^0 = 1503

adec문자에서 a는 제외되었기 때문에 a에 해당하는 값을 빼고 

한 자리씩 앞으로 이동했기 때문에 곱하기 2를 해주고 

마지막에 추가된 문자를 더해주면 된다.

    public List<Integer> find(String parent, String pattern) {

        int parentHash = 0, patternHash = 0, power = 1;

        int parentLen = parent.length();
        int patternLen = pattern.length();

        List<Integer> idxList = new ArrayList<>();

        for (int i = 0; i < parentLen - patternLen; i++) {

            if (i == 0) {
                for (int j = 0; j < patternLen; j++) {
                    parentHash = parentHash + parent.charAt(patternLen - 1 - j) * power;
                    patternHash = patternHash + pattern.charAt(patternLen - 1 - j) * power;

                    if (j < patternLen - 1) {
                        power *= 2;
                    }
                }
            } else {
                parentHash = (parentHash - parent.charAt(i - 1) * power) * 2 
                    + parent.charAt(i + patternLen - 1);
            }

            if (parentHash == patternHash) {
                boolean found = true;

                for (int j = 0; j < patternLen; j++) {
                    if (parent.charAt(i + j) != pattern.charAt(j)) {
                        found = false;
                        break;
                    }
                }

                if (found) {
                    idxList.add(i + 1);
                }
            }
        }

        return idxList;
    }

기존 설정

# application.yml

# default
spring:
    profiles:
        active: test
---
spring:
    profiles: test
        include:
        - common
# 기타 설정 .. 
---
spring:
    profiles: prod
# 기타 설정 .. 
---
spring:
    profiles: dev
# 기타 설정 ..

spring.profiles 설정을 통해 어떠한 profile인지 표시 

spring.profiles.include 설정을 통해 추가적으로 포함할 profile 표시

2.4 버전 이후 설정

spring.profiles 설정은 duplicated 되었다

# application.yml

# default
spring:
  profiles:
    active: test
  group:
    dev: 
    - dev-t1
    - common
---
spring:
  config:
    activate:
      on-profile: test
# 기타 설정 .. 
---
spring:
  config:
    activate:
      on-profile: prod
# 기타 설정 ..       
---
spring:
  config:
    activate:
      on-profile: dev 
# 기타 설정 ..

spring.config.activate.on-profile 설정을 통해 어떠한 profile인 경우 해당 설정들이 활성화되는지 표시 

spring.profiles.group 설정을 통해 profile들을 그룹핑 

활성 profile 설정 

실제로 application을 실행할 때 spring.profiles.active 설정을 주어 어떠한 profile를 활성화할 것인지 정해주어야 한다.

해당 설정이 없을 시에는 default값으로 "default" profile이 실행된다.

위의 예시들처럼 yaml, properties file에 설정을 해주거나 

실행 시 argument로 넘겨도 된다.

java -jar myApp.jar --spring.profiles.active=dev

또는, 사용하는 개발 tool의 실행 argument에 설정해주면 된다.

( 이클립스의 경우 실행 프로젝트의 오른쪽 클릭 -> Run as.. -> Run Configurations ) 

추가적으로, 참고할만한 링크

spring-projects github에 2.4 관련 release note와 config data migration guide 

https://github.com/spring-projects/spring-boot/wiki/Spring-Boot-2.4-Release-Notes

https://github.com/spring-projects/spring-boot/wiki/Spring-Boot-Config-Data-Migration-Guide

설정 파일 분리 

application.yml을 사용하는 경우에는 "---"를 사용하여 설정을 분리할 수 있다.

server:
  port: 8089
spring:
  profiles:
    active:
    - test
  application:
    name: pj2
---
server:
  port: 8089
spring:
  profiles:
    active:
    - dev
  application:
    name: devPj2

또한, profile 단위로 설정 파일 자체를 분리할 수도 있다.

• application-dev.yml
• application-test.yml
• application-{profile}.yml

각각의 파일은 spring application을 실행 시 args 등으로 넘기는 spring.profiles.active로 결정되어진다. 

java -jar myApp.jar --spring.profiles.active=dev

여러 개의 설정파일 

하나의 profile에서 사용되는데 여러개의 설정 파일을 로드하고 싶은 경우가 존재할 수 있다.

이러한 경우에는 어떻게 설정하는지 알아보자.

spring.config.location

이 설정은 spring config의 기본 설정을 재정의하여 여러 가지의 설정 파일을 로드할 수 있다.

spring config에서 default로 제공하는 값은 아래와 같다.

사용자가 spring.config.location을 정의하면 default값은 덮어써지게 된다.

spring.config.additional-location

이 설정은 추가적인 위치를 설정하는 것이다.

location 설정에 플러스로 더 설정하고 싶은 경우 

spring.config.location, spring.config.additional-location 설정은 application.yml 파일을 로드하기 전에 사용되는 설정으로 해당 파일에 설정하면 동작하지 않는다.

SystemProperties나 CommandLine Argument로 전달해야 정삭적으로 사용될 수 있다.

java -jar myApp.jar --spring.config.additional-location=optional:classpath:test.yml

spring.config.import

해당 설정은 spring boot 2.4 이후부터 추가된 설정으로 위에 설명한 설정들과 달리 application.yml를 통해서 추가적인 설정 파일의 위치를 설정할 수 있다. 

spring:
  config:
    import:
    - optional:classpath:/test.yml

위의 내용들에 아래 spring문서를 확인하면 더욱 자세하게 확인 할 수있다.

https://docs.spring.io/spring-boot/docs/current/reference/html/features.html#features.external-config

Given an integer array nums, 

you need to find one continuous subarray that if you only sort this subarray in ascending order, 

then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

integer 배열인 nums가 주어진다.

하나의 연속적인 sub배열을 구해라,

그 sub배열의 조건은 오직 그 sub배열을 정렬했을 때 전체 배열이 오름차순으로 정렬되는 것이다.

가장 짧은 sub 배열의 길이를 반환해라.

배열에 해당하는 문제이다.

풀이 방식으로는 두개의 포인터를 맨 앞 맨뒤에 두고,

하나씩 순회하면서 정렬기준에 맞지 않는 인덱스를 찾으면 된다.

맨 처음 포인터의 경우, 뒤에 값이 앞에 값보다 작아지는 순간부터의 최솟값의 인덱스를 찾으면 된다.

후에 해당 인덱스의 값이 배열에 어느 위치로 정렬되어야 하는지 찾아야 한다.

맨 뒤의 포인터도 위의 방식과 유사하게 진행하면 된다.

    public int findUnsortedSubarray(int[] nums) {
        boolean found = false;
        int min = Integer.MIN_VALUE;
        for (int i = 1; i <= nums.length - 1; i++) { // find minimum

            if (!found) {
                if (nums[i] < nums[i - 1]) {
                    found = true;
                    min = nums[i];
                }
            } else { // find minimum
                if (min >= nums[i]) {
                    min = nums[i];
                }
            }
        }

        int l = 0;
        if (!found) {
            return 0;
        } else { // find start index
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > min) {
                    break;
                }
                l++;
            }
        }

        found = false;
        int max = Integer.MAX_VALUE;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (!found) {
                if (nums[i] > nums[i + 1]) {
                    found = true;
                    max = nums[i];
                }
            } else {
                if (max <= nums[i]) {
                    max = nums[i];
                }
            }
        }
        int h = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < max) {
                break;
            }
            h--;
        }

        return h - l + 1;
    }

해당 풀이로는 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.