HeapSort
📕 힙의 개념
Heap이란 부모노드가 자식보다 항상 크거나 항상 작은 이진트리이다.
❓ 힙(Heap) 자료구조를 사용하는 이유-
힙은 최대/최소를 구하는데 특화되어 있는 자료구조
-
루트의 값만 바로 가져오면 되기 때문에
O(1)의 시간복잡도로 최대값 혹은 최소값 구하기 가능 -
새로운 값을 추가(add)하거나 삭제(poll)하는 경우,
Olog(n)의 시간복잡도를 가진다
Heap은 구현방식에 따라 여러가지 형태를 가질 수 있는데 대표적으로 Max-Heap(최대힙), Min-Heap(최소힙) 이 있다.
최대힙, 최소힙 
Max-Heap(최대힙)
- 루트 노드의 key는 항상 해당 노드의 자식노드들의 key보다 크거나 같다
- 같은 속성이 모든 sub-tree들에도 재귀적으로 적용
Min-Heap(최소힙)
- Max-Heap과는 반대로 루트 노드의 key가 항상 해당 노드의 자식 노드들의 key보다 작거나 같다
- 마찬가지로 모든 sub-tree들에 재귀적으로 적용
- 왼쪽 자식 idx = 부모 idx × 2 + 1
- 오른쪽 자식 idx = 부모 idx × 2 + 2
- 부모 idx = (자식 idx - 1) / 2
💻 구현 과정
첫번째 )
[6, 5, 7, 8]을 배열에 담아보고 root가 가장 큰 heap으로 만든다.
순서는 자식이 있는 가장 마지막 부모부터 시작하여,
그리고 부모노드의 값이 자식노드의 값보다 커야한다는 Heap 형태로 만들어준다.
💡 여기서 유의할 점은 자식노드는 바로 근처의 자식뿐만 아니라, 모든 자손을 뜻한다는 것이다. - 세번째 단계에서 해결
public static void main(String[] args) {
int [] arr = new int[] {6,5,7,8};
int temp = arr[1];
arr[1] = arr[3];
arr[3] = temp;
temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
System.out.println(Arrays.toString(arr));
} 결과 - { 8,6,7,5 }두번째 ) 부모의 index를 입력하면 왼쪽, 오른쪽 index를 return하는 함수
형제끼리는 규칙이 없지만 부모와 자식간에는 규칙이 있다.
// 부모의 index 입력하면 자식 index 반환하는 함수
public int [] findChild(int index) {
int [] answer = {index*2+1, index*2+2};
return answer;
}세번째 ) greaterIdx 변수 추가하여 자손까지 정렬해준다.
// 최대힙
public static int[] makeHeap(int[] arr, int parentIdx, int arrSize) {
int leftIdx = 2 * parentIdx + 1;
int rightIdx = 2 * parentIdx + 2;
int greaterIdx = parentIdx;
// 왼쪽이 parent보다 크면 greateridx=leftIdx 6 7 5 -> 7 6 5
if(leftIdx < arrSize && arr[leftIdx] > arr[greaterIdx]){
greaterIdx = leftIdx;
}
//오른쪽 자식이 greater 보다 크면
if(rightIdx < arrSize && arr[rightIdx] > arr[greaterIdx]){
greaterIdx = rightIdx;
}
// swap
if(parentIdx != greaterIdx){
int temp = arr[parentIdx];
arr[parentIdx] = arr[greaterIdx];
arr[greaterIdx] = temp;
makeHeap(arr, greaterIdx, arrSize);
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[]{6, 5, 7, 8};
arr = new int[]{10, 9, 5, 8, 3, 2, 4, 6, 7, 1};
for (int j = (arr.length-2) / 2; j >= 0 ; j--) {
arr = makeHeap(arr, j, arr.length);
System.out.println(Arrays.toString(arr));
}
// 정렬
for (int i = arr.length - 1; i > 0 ; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
arr = makeHeap(arr, 0, i);
System.out.println(Arrays.toString(arr));
}
}
Spring Security ( Token)
목표
이때까지 만들어 온
"/api/v1/users/join"url은 User에게 전달 받은 userName, password, email 등을 DB에 그대로 저장했다. password와 같은 민감정보는 암호화를 해야하므로 Spring Security 를 사용하여 암호화한다.
Spring Security 개념
애플리케이션의 인증, 인가 등의 보안 기능을 제공하는 스프링 하위 프레임워크
🟦 용어정리
인증(authentication)
: 사용자가 누구인지 확인하는 단계
ex) 로그인
DB에 등록된 id,pw를 사용자가 입력한 id,pw와 비교하여 일치 여부를 확인한다.
로그인에 서버는 사용자에게 토큰을 전달한다.인가(authorization)
: 애플리케이션 내부의 리소스에 접근 권한 확인.
보통 인증 단계에서 발급 받은 토큰에 인가 내용이 포함되어 있다.
ex) 회원별 접근 가능 게시판 상이
JWT(JSON Web Token)
: 당사자 간에 정보를 JSON 형태로 안전하게 전송하기 위한 토큰
구성요소 - 헤더.내용.서명
헤더: 검증과 관련된 내용 ( 해싱 알고리즘 지정, 토큰 타입 지정)
내용: 토큰에 담는 정보, 클레임,
서명: 인코딩된 헤더, 인코딩된 내용, 비밀키, 헤더의 알고리즘 속성값을 가져와 생성
// HMAC SHA256 알고리즘을 사용해서 서명을 생성한다면?
HMACSHA256 (
base64UrlEncode(header) + "."+
base64UrlEncode(payload),
secret
)
Security 관련 용어들을 카타르 월드컵에 비유해서 설명해보자면,
인증 - 월드컵 구장 안에 들여 보내 주는것
인가 - 그 기능에 권한이 있는지 확인 : VIP석, R석, S석, 일반석
JWT - Claim 좌석번호, 승객이름 🟨 스프링 시큐리티 동작구조
- 서블릿 필터 기반으로 동작한다. ➡ DispatcherServlet 앞에 필터 배치
- 필터 체인에서 인증, 인가를 한다.
🟦 기능 정리
💻 SecurityConfig.class
@EnableWebSecurity가 선언된 클래스가 있다면 Spring Security 동작- 기존의 Spring Boot에서는 보안 필터체인 설정 시 WebSecurityConfigurerAdapter를 상속받아 설정하였지만, 지금은
Bean으로 등록하여 사용하도록 변경됨
@Bean
public SecurityFilterChain securityFilterChain(HttpSecurity httpSecurity) throws Exception {.httpBasic().disable(): 기본 설정은 비인증 시 로그인 폼 화면으로 리다이렉트 되며, Rest API이므로 기본설정을 사용하지 않기 위해 disable() 설정.csrf().disable(): 정상적인 사용자가 의도치 않은 위조요청을 보내는 것(Cross site Request forgery; csrf)로부터 보호하는 것을 사용하지 않음 👉 Rest API 서버는 Stateless 상태이므로 서버에 인증정보를 보관하지 않기 때문에.cors(): 교차 출처를 공유할 수 있는 권한을 부여하도록 브라우저에 알려주는 정책(Cross-Origin Resource Sharing; CORS) 으로, 서로 다른 출처를 가진 Application이 서로의 Resource에 접근할 수 있도록 해줌.authorizeRequests(): HttpServletRequest를 이용
