0411 ~ 0417

# 0411 ~ 0417

# 0411 - DFS, BFS의 설명, 차점

BFS, DFS 두가지 모두 그래프를 탐색하는 방법이다.

그래프란, 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

# DFS 깊이 우선 탐색 (Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.
예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

# BFS 너비 우선 탐색 (Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가장운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택.
ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

# DFS, BFS 비교

DFS(깊이우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 -> 스택 또는 재귀함수로 구현
BFS(너비우선탐색) : 현재 정점에서 연결된 가까운 점들부터 탐색 -> 큐를 이용해서 구현

# DFS, BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

# 깊이 우선 탐색과 너비 우선 탐색 활요한 문제 유형/응용

그래프의 모든 정점을 방문하는 것이 주요한 문제
: 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 두 가지 방법 중 어느 것을 사용해요 상관없다.
경로의 특징을 저장해둬야 하는 문제
: 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 떄는 DFS를 사용한다.(BFS는 경로의 특징을 가지지 못한다)
최단거리를 구해야 하는 문제
: 미로 찾기 등 최단거리를 구해야 하는 경우, BFS가 유리하다. 이유는 깊이 우선 탐색으로 경로를 검색할 경우 처음부터 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.
검색 대상 그래프가 정말 크다면 -> DFS를 고려
검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

# 0412 - PasswordEncoder

Spring Security에서는 비밀번호를 안전하게 저장할 수 있도록 비밀번호의 단방향 암호화를 지원하는 PasswordEncoder 인터페이스와 구현체들을 제공한다. 이 인터페이스는 아래와 같이 심플하게 구성되어 있다.

public interface PasswordEncoder {
	
　　// 비밀번호를 단방향 암호화
　　String encode(CharSequence rawPassword);
	
　　// 암호화되지 않은 비밀번호(raw-)와 암호화된 비밀번호(encoded-)가 일치하는지 비교
　　boolean matches(CharSequence rawPassword, String encodedPassword);
	
　　// 암호화된 비밀번호를 다시 암호화하고자 할 경우 true를 return하게 설정
　　default boolean upgradeEncoding(String encodedPassword) { return false; };
}

Spring Security 5.3.3에서 공식 지원하는 PasswordEncoder 구현 클래스들은 아래와 같다.

BcryptPasswordEncoder : BCrypt 해시 함수를 사용해 비밀번호를 암호화
Argon2PasswordEncoder : Argon2 해시 함수를 사용해 비밀번호를 암호화
Pbkdf2PasswordEncoder : PBKDF2 해시 함수를 사용해 비밀번호를 암호화
SCryptPasswordEncoder : SCrypt 해시 함수를 사용해 비밀번호를 암호화

위 4개의 PasswordEncoder는 Password를 encode할 때, 매번 임의의 salt를 생성해서 encode하게 되어 있다.

예를 들어 BCryptPasswordEncoder Class의 코드를 보면 다음과 같다.

/*
* BCryptPasswordEncoder.encode() : 암호화
*/
public String encode(CharSequence rawPassword) {

　　if (rawPassword == null) {
　　　　throw new IllegalArgumentException("rawPassword cannot be null");
　　}
	
　　String salt;
　　
   if (random != null) {
   　　salt = BCrypt.gensalt(version.getVersion(), strength, random);
   } else {
   　　salt = BCrypt.gensalt(version.getVersion(), strength);
   }
   return BCrypt.hashpw(rawPassword.toString(), salt);
}

/**
* BCrypt.gensalt() : Salt 생성
*/
public static String gensalt(String prefix, int log_rounds, SecureRandom random) throws IllegalArgumentException {

　StringBuilder rs = new StringBuilder();
　byte rnd[] = new byte[BCRYPT_SALT_LEN]; // 16byte(128bit) 크기의 Salt 생성

  if (!prefix.startsWith("$2") || (prefix.charAt(2) != 'a' && prefix.charAt(2) != 'y' && prefix.charAt(2) != 'b')) {
      throw new IllegalArgumentException ("Invalid prefix");
  }
  
  if (log_rounds < 4 || log_rounds > 31) {
      throw new IllegalArgumentException ("Invalid log_rounds");
  }

　random.nextBytes(rnd);

　rs.append("$2");
　rs.append(prefix.charAt(2));
　rs.append("$");
　if (log_rounds < 10)
      rs.append("0");
  
  rs.append(log_rounds);
  rs.append("$");
  encode_base64(rnd, rnd.length, rs);

  return rs.toString();
}

# BCryptPasswordEncoder

BCrypt 해시 함수를 사용해 비밀번호를 해시하는 PasswordEncoder이다. Bruteforce attack이나 Rainbow table attack과 같은 Password Cracking에 대한 저항력을 높이기 위해 의도적으로 느리게 설정되어 있다.

전문 장비를 이용하면 한 계정에 대한 비밀번호 입력을 1초에 수억번 이상으로 시도할 수 있다. 따라서 이런 유형의 공격을 어렵게 만들기 위해 1개의 암호를 확인하는데 약 1초 정도의 시간이 걸리도록 하는 것을 권장한다. 각 시스템별로 성능 차이가 있기 때문에 PasswordEncoder가 암호를 해독하는데 걸리는 시간은 달라질 수 있다. 따라서 시스템에 맞게 테스트하면서 속도를 조정해줘야 한다.

BCryptPasswordEncoder의 속도는 강도(strength)를 조정해서 조절할 수 있다. 강도는 4~31까지 설정할 수 있으며, BcryptPasswordEncoder는 default 강도로 아래와 같이 10을 사용한다.

public BCryptPasswordEncoder(BCryptVersion version, int strength, SecureRandom random) {
  
  if (strength != -1 && (strength < BCrypt.MIN_LOG_ROUNDS || strength > BCrypt.MAX_LOG_ROUNDS)) {
    throw new IllegalArgumentException("Bad strength");
  }
  
  this.version = version;
  this.strength = strength == -1 ? 10 : strength; // 지정하지 않으면 강도를 10으로 설정
  this.random = random;
}

// 강도설정
// Create an encoder with strength 16
BCryptPasswordEncoder encoder = new BCryptPasswordEncoder(16);
String result = encoder.encode("myPassword");
assertTrue(encoder.matches("myPassword", result));

# Argon2PasswordEncoder

Argon2 해시 함수를 사용해 비밀번호를 해시하는 PasswordEncoder이다. Argon2는 Paasword Hasing Competition의 우승자로 Password Craking을 방지하기 위해 다른 PasswordEncoder와 마찬가지로 의도적으로 느리게 실행되도록 설정되어 있다.

// Create an encoder with all the defaults
Argon2PasswordEncoder encoder = new Argon2PasswordEncoder();
String result = encoder.encode("myPassword");
assertTrue(encoder.matches("myPassword", result));

# Pbkdf2PasswordEncoder

PBKDF2 해시 함수를 사용해 비밀번호를 해시하는 PasswordEncoder이다. FIPS 인증(Federal Information Processing Standards, 미 연방 시스템 내에서 중요한 데이터를 보호하기 위한 필요 표준)이 필요한 경우 이 PasswordEncoder를 선택하는것이 좋다.

// Create an encoder with all the defaults
Pbkdf2PasswordEncoder encoder = new Pbkdf2PasswordEncoder();
String result = encoder.encode("myPassword");
assertTrue(encoder.matches("myPassword", result));

# SCryptPasswordEncoder

SCrypt 해시 함수를 사용해 비밀번호를 해시하는 PasswordEncoder이다.

SCryptPasswordEncoder encoder = new SCryptPasswordEncoder();
String result = encoder.encode("myPassword");
assertTrue(encoder.matches("myPassword", result);

# 0414 - StringUtils를 사용하는 이유

.split() .toCharArray() equals() 등 String 메소드를 사용할 때 바로 호출하는 것보다 StringUtils 라이브러리를 활용하는 것을 권장한다.

String arr[], str = "hello-world"; 

arr = "hello-world".split("-"); // (X) warning
arr = str.split("-"); // (X) warning

arr = StringUtils.("hello-world", "-"); // (O) null-safe
arr = StringUtils.(str, "-"); // (O) null-safe

# StringUtils 라이브러리는 Null-Safe하다.

String 클래스의 경우 str1.equals(str2); 에서 str1이 null이면 NullPointerException 예외가 발생하지만, StringUtils 클래스의 경우 StringUtils.equals(str1,str2) 에서 st1이 null 이어도 예외가 발생하지 않고 null을 반환한다.

컬렉션인 경우 CollectionUtils.isEmpty() 또는 CollectionUtils.isNotEmpty()을 사용한다.

# 0415 - @Converter

@Converter를 사용하면 엔티티의 데이터를 변환해서 데이터베이스에 저장할 수 있다.

# Converter 사용법

@Entity
class Member{
    @Id @GeneratedValue
    private Integer id;

    @Convert(converter=BooleanToYNConverter.class)
    private boolean useYn;
}

@Converter
class BooleanToYNConverter implements AttributeConverter<Boolean, String>{
    @Override
    public String convertToDatabaseColumn(Boolean attribute){
        return (attribute != null && attribute) ? "Y" : "N";
    }

    @Override
    public Boolean convertToEntityAttribute(String dbData){
        return "Y".eqauls(dbData);
    }
}

AttributeConverter<엔티티컬럼타입, 데이터베이스 컬럼 타입>

# 클래스 레벨 설정

@Entity
@Converter(converter = BooleanToYNConverter.class, attributeName = "useYn")
class Member{
    // ...
}

# 글로벌 설정

@Converter(autoApply = true)
class BooleanToYNConverter implements AttributeConverter<Boolean, String>{
    // ...
}

모든 Boolean 타입에 설정

# 0417 - ECS, Fagate

# Amazon ECS(Elastic Container Service)fks?

클러스터에서 컨테이너를 쉽게 실행, 중지 및 관리할 수 있게 해주는 컨테이너 관리 서비스.
간단한 API 호출을 사용하여 컨테이너 기반 애플리케이션을 시작하고 중지할 수 있다.

# AWS Fargate란

별도로 인스턴스를 생성 관리하지 않고, 완전한 매니지드 서비스의 형태로 도커 컨테이너를 실행시킬 수 있는 아마존의 서버리스 컨테이너 상품. Docker 이미지가 리포지토리에 푸시되어 있다면, 클라스터 -> 작업 정의 -> 서비스의 순서로 생성하여 완전히 24시간 서비스 가능한 애플리케이션을 기동할 수 있다.
fagate를 사용하려면 상위 개념에서 특정 오케으스레이션 상품을 선택해야한다. 현재 Amazon ECS, Amazon EKS에서 지원, 사용가능하다.

사용법은 추후에 자세이 공부

0404 ~ 0410 0418 ~ 0424