Algorithm
Iterative and Recursive
반복
- 어떤 작업이 완료될 때까지 동일한 작업을 반복하는 방법
- 어떤 특정 반복 조건이 거짓이 될 때까지 반복
- 일반적인 상황에서 재귀보다 효율적으로 작동
재귀
- 큰 문제를 더 작은 문제로 나누어 풀고 그 결과를 결합하는 방법
- 어떤 재귀 조건을 만족할 때까지 재귀
- Call Stack을 활용하기 때문에 상대적으로 성능이 안 좋지만 코드를 간결하게 표현하는 데 도움이 됨
예를 들어 Selection Sort를 살펴볼 때 재귀와 재귀가 아닌 방법으로 모두 구현이 가능하다.
import java.util.Arrays;
public class SelectionSortRecursive {
public void selectionsort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
private void selectionsortRecursive (int[] arr, int start) {
if (start == arr.length) return;
int minIndex = start;
for(int i = start + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) minIndex = i;
}
int temp = arr[start];
arr[start] = arr[minIndex];
arr[minIndex] = temp;
// 남은 영역에 대해서 똑같은 작업을 한다
selectionsortRecursive(arr, start + 1);
}
}Power Set
집합은 어떤 조건을 가진 원소의 모음이다. 집합의 원소 중 일부 또는 전부를 택해 만드는 새로운 집합을 부분 집합이라고 한다. 어떤 집합에 대하여 해당 집합이 가질 수 있는 모든 부분 집합의 집합을 Powerset이라고 한다. 부분 집합을 만들 때는 n개의 원소에 대해 해당 원소를 포함해야 할지 말지를 검사해야 해서 조합과 유사하다. 따라서 파워셋은 총 2^n 개 후보가 있다.
이를 반복문의 형태로 작성하면 다음과 같다.
public class PowerSetIter {
public static void main(String[] args) {
int[] set = new int[] {2, 3, 5};
int[] select = new int[3];
// set의 각 원소를 선택할까 말까를 결정
// 0이면 선택 X 1이면 선택 O
for (int i = 0; i < 2; i++) {
select[0] = i;
for (int j = 0; j < 2; j++) {
select[1] = j;
for (int k = 0; k < 2; k++) {
select[2] = k;
for (int l = 0; l < 3; l++) {
if(select[l] == 1)
System.out.println(set[l] + " ");
}
System.out.println();
}
}
}
}
}같은 작업이지만 재귀적으로도 구현할 수 있다.
public class PowerSetRecursive {
public void powerSet(
int[] set,
int next,
int[] select
) {
// 다 고르면 종료
if (next == set.length) {
for (int i = 0; i < set.length; i++) {
if(select[i] == 1) System.out.println(set[i] + " ");
}
System.out.println();
return;
}
// 안 골랐을 경우
select[next] = 0;
powerSet(set, next + 1, select);
// 골랐을 경우
select[next] = 1;
powerSet(set, next + 1, select);
}
public static void main(String[] args) {
int[] set = new int[] {2, 3, 5};
int[] select = new int[3];
new PowerSetRecursive().powerSet(set, 0, select);
}
}Bit
비트 연산을 통해 부분 집합을 구할 수 있다. 비트 연산은 2진수로 표현한 숫자의 각 자릿수를 기준으로 계산하는 연산이다. 비트 연산의 속도가 더 빠르기 때문에 이를 통해 PowerSet을 빠르게 구할 수 있다.
& AND: 두 수의 2진수가 둘 다 1이어야 1
110 & 011 → 010
| OR: 두 수의 2진수가 각 자릿수 중 하나라도 1이면 1
110 | 011 → 111
<< >> : 자릿수 이동
001 << 2 → 100
import java.util.ArrayList;
import java.util.List;
public class PowerSetBitmask {
public static void main(String[] args) {
int[] set = {2, 3, 5};
new PowerSetBitmask().powerSet(set);
}
public void powerSet(int[] set) {
int n = set.length;
// 집합의 부분 집합의 갯수는 2^n개인데, 1 << n 의 결과도 2^n
int subsetCount = 1 << n;
// i를 이진수로 생각하면
// 각 자릿수가 1일 때 해당 자릿수 번째 원소를 고른다고 가정
for (int i = 0; i < subsetCount; i++) {
List<Integer> subset = new ArrayList<>();
// n 개의 원소를 판단하기 위해 n번 반복
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0)
subset.add(set[j]);
}
System.out.println(subset);
}
}
}Spring Security
UserDetailsManager Custom
지난 게시글에 배운 내용은 테스트 용도의 User 객체이다. 실제로 우리가 만드는 서비스는 내가 정의한 대로 내가 데이터베이스에 설계한 대로 Customize 가능해야 한다.
먼저 데이터베이스 관련 의존성을 추가해 준다.
// sqlite
implementation 'org.xerial:sqlite-jdbc:3.41.2.2'
runtimeOnly 'org.hibernate.orm:hibernate-community-dialects:6.2.4.Final'이후 application.yaml 파일을 만들어 준다.
spring:
datasource:
url: jdbc:sqlite:db.sqlite
driver-class-name: org.sqlite.JDBC
username: sa
password: password
jpa:
hibernate:
ddl-auto: create
database: h2
database-platform: org.hibernate.community.dialect.SQLiteDialect
show-sql: true후에 우리가 설계해서 사용할 UserEntity를 만들어 준다. 이때 아이디는 겹치지 않아야 하고, 아이디랑 비밀번호는 필수로 있어야 한다. 이러한 DB 제약 사항까지 고려해서 테이블을 설계한다.
import jakarta.persistence.*;
import lombok.Data;
@Data
@Entity
@Table(name = "users")
public class UserEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
@Column(nullable = false, unique = true)
private String username;
@Column(nullable = false)
private String password;
private String email;
private String phone;
}이후 해당 엔티티를 관리하기 위한 레포지토리를 만들어 준다.
import org.springframework.data.jpa.repository.JpaRepository;
public interface UserRepository extends JpaRepository<UserEntity, Long> {
}이때 레포지토리에서는 1. 사용자 계정 이름으로 사용자 정보를 회수하는 기능 2. 사용자 계정 이름을 가진 사용자 정보가 존재하는지 판단하는 기능을 구현해야 한다. Spring Security는 Filter chain 방식으로 작동한다. 필터가 막 늘어나서 이를 기반으로 사용자 정보를 판단한다.
public interface UserRepository extends JpaRepository<UserEntity, Long> {
// TODO
// 1. 사용자 계정 이름으로 사용자 정보 회수
Optional<UserEntity> findByUsername(String username);
// 2. 사용자 계정 이름을 가진 사용자 정보 존재하는지 판단
boolean existsByUsername(String username);
}이후에 사용자의 구체적인 정보를 회수하는 JPAUserDetailsManager로 서비스를 구현해 준다. 이때 UserDetailsManager의 구현체로 만들면 Spring Security Filter에서 사용자 정보를 회수해 줄 수 있다. 이후 인터페이스의 메소드를 클래스에서 구현할 수 있는데, 나머지는 옵션이지만, loadUserByUsername 같은 경우는 실제로 Spring Security 내부에서 사용하는 반드시 구현해야 정상 동작을 할 수 있는 메소드이다.
@Service
@Slf4j
@Primary
public class JPAUserDetailsManager implements UserDetailsManager {
private final UserRepository userRepository;
public JPAUserDetailsManager(UserRepository userRepository, PasswordEncoder passwordEncoder) {
this.userRepository = userRepository;
createUser(User.withUsername("user")
.password(passwordEncoder.encode("password"))
.build());
}
@Override
public void createUser(UserDetails user) {
// 이미 있으면
if(this.userExists(user.getUsername()))
throw new ResponseStatusException(HttpStatus.BAD_REQUEST);
UserEntity userEntity = new UserEntity();
userEntity.setUsername(user.getUsername());
userEntity.setPassword(user.getPassword());
this.userRepository.save(userEntity);
}
@Override
public void updateUser(UserDetails user) {
}
@Override
public void deleteUser(String username) {
}
@Override
public void changePassword(String oldPassword, String newPassword) {
}
@Override
public boolean userExists(String username) {
return userRepository.existsByUsername(username);
}
@Override
// 실제로 Spring Security 내부에서 사용하는 반드시 구현해야 정상 동작을 할 수 있는 메소ㅒ
public UserDetails loadUserByUsername(String username) throws UsernameNotFoundException {
Optional<UserEntity> optionalUser =
userRepository.findByUsername(username);
if(optionalUser.isEmpty())
throw new UsernameNotFoundException(username);
UserEntity userEntity = optionalUser.get();
return User.withUsername(userEntity.getUsername())
.password(userEntity.getPassword())
.build();
}
}Spring Security에서 제공하는 UserDetails라는 인터페이스를 만들고 이것을 만족하는 객체만 스프링 시큐리티에 넣을 수 있도록 되어 있다. 그러나 내가 원하는 객체로 만들 수 있도록 UserDetails 자체도 커스텀할 수 있다.
@Builder: 여러 개의 필드를 다루고 있는 복합적인 객체들에 대해 하나하나씩 만들어 가듯 필드를 하나씩 따로 넣고 싶은 것만 취사 선택해서 만들어 줄 수 있는 디자인 패턴을 지원해 준다.
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Getter;
import lombok.NoArgsConstructor;
import org.springframework.security.core.GrantedAuthority;
import org.springframework.security.core.userdetails.UserDetails;
import java.util.Collection;
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class CustomUserDetails implements UserDetails {
@Getter
private Long id;
private String username;
private String password;
@Getter
private String email;
@Getter
private String phone;
@Override
public Collection<? extends GrantedAuthority> getAuthorities() {
return null;
}
@Override
public String getPassword() {
return this.password;
}
@Override
public String getUsername() {
return this.username;
}
@Override
public boolean isAccountNonExpired() {
return false;
}
@Override
public boolean isAccountNonLocked() {
return false;
}
@Override
public boolean isCredentialsNonExpired() {
return false;
}
@Override
public boolean isEnabled() {
return false;
}
public static CustomUserDetails fromEntity(UserEntity userEntity) {
return CustomUserDetails.builder()
.id(userEntity.getId())
.password(userEntity.getPassword())
.email(userEntity.getEmail())
.username(userEntity.getUsername())
.phone(userEntity.getPhone())
.build();
}
public UserEntity newEntity() {
UserEntity entity = new UserEntity();
entity.setUsername(username);
entity.setPassword(password);
entity.setEmail(email);
entity.setPhone(phone);
return entity;
}
@Override
public String toString() {
return "CustomUserDetails{" +
"id=" + id +
", username='" + username + '\'' +
", password='[PROTECTED]'" +
", email='" + email + '\'' +
", phone='" + phone + '\'' +
'}';
}
}커스텀한 유저 디테일을 바탕으로 유저를 추가해 보는 과정을 진행해 보자. 앞서 커스텀한 UserDetailsManager의 코드를 다음과 같이 수정할 수 있다.
@Service
@Slf4j
@Primary
public class JPAUserDetailsManager implements UserDetailsManager {
private final UserRepository userRepository;
public JPAUserDetailsManager(UserRepository userRepository, PasswordEncoder passwordEncoder) {
this.userRepository = userRepository;
**createUser(CustomUserDetails.builder()
.username("user")
.password(passwordEncoder.encode("password"))
.email("user@gamil.com" )
.phone("010-0000-0000")
.build());**
}
@Override
public void createUser(UserDetails user) {
// 이미 있으면
if(this.userExists(user.getUsername()))
throw new ResponseStatusException(HttpStatus.BAD_REQUEST);
try {
**userRepository.save(((CustomUserDetails) user).newEntity());**
} catch (ClassCastException e) {
log.error("failed to cast to {}", CustomUserDetails.class);
throw new ResponseStatusException(HttpStatus.INTERNAL_SERVER_ERROR);
}
}
@Override
public void updateUser(UserDetails user) {
}
@Override
public void deleteUser(String username) {
}
@Override
public void changePassword(String oldPassword, String newPassword) {
}
@Override
public boolean userExists(String username) {
return userRepository.existsByUsername(username);
}
@Override
// 실제로 Spring Security 내부에서 사용하는 반드시 구현해야 정상 동작을 할 수 있는 메소ㅒ
public UserDetails loadUserByUsername(String username) throws UsernameNotFoundException {
Optional<UserEntity> optionalUser =
userRepository.findByUsername(username);
if(optionalUser.isEmpty())
throw new UsernameNotFoundException(username);
UserEntity userEntity = optionalUser.get();
**return CustomUserDetails.fromEntity(optionalUser.get());**
}
}JWT
JWT
**JSON으로 표현된 정보를 안전하게 주고받기 위한 Token의 일종으로 JSON Web Token**이다. 세션 기반 인증을 벗어난 토큰 기반 인증이다. 사용자 확인을 위한 인증 정보를 가져오고 위변조가 어렵기 때문에 위변조가 일어났는지 확인하기 용이하다. 토큰 기반 인증 시스템에서 많이 활용한다. 토큰 기반 인증 시스템에서는 세션을 만들지 않는다.
Token은 통행증이 아닌 신분증에 가깝다. 사용자가 누구고 언제 로그인을 했고 어느 정보까지 접근이 가능한지 명시되어 있기 때문이다. 따라서 이 토큰을 보유했느냐 안 했느냐를 기반으로 로그인 유무를 판별한다. 토큰에는 종류가 많지만 사실상 제일 많이 활용하는 게 JWT일 뿐이지 이 토큰이 만능은 아니다.
JWT는 header.payload.signature로 구성되어 있다.
header: JWT의 부수적인 정보이다. 어떤 암호화 방식을 택했는지 등등이다.payload: 실제로 전달하고자 하는 정보가 담긴 부분이다. subject (누구) iat (issue) exp (expired)signature: JWT의 위변조 유무를 판단하는 부분으로 위변조가 어렵다.
Token Based Authentication은 세션을 저장하지 않고 토큰의 소유를 통해 인증을 판단하는 방식이다. 따라서 상태를 저장하지 않기 때문에 서버의 세션 관리가 불필요하고, 여러 서버에 걸쳐서 인증이 가능하다. 쿠키는 요청을 보낸 클라이언트에 종속되지만 토큰은 쉽게 헤더에 첨부가 가능하다. 그러나 로그인 상태라는 개념이 사라져서 기본적으로는 로그아웃이 불가능하다.
