전체 글

이 글은 백엔드 개발 초보가 작성한 글로, 일부 잘못된 내용이 있을 수 있습니다.이상하거나 잘못된 부분은 댓글을 통해 알려주세요! Spring Boot를 처음 배울 때 함께 등장하는 Spring Security.처음 느낀 인상은 "왜 이렇게 뭐가 복잡하지?"였다. Spring Security는 도대체 어떻게 돌아가는 걸까? 1. Java ServletSpring Security를 이해하려면 먼저 Servlet을 알아야 한다.우리가 흔히 짜는 일반 자바 애플리케이션(main() 함수가 있는)은 개발자가 객체의 생성과 실행 흐름을 작성한다.하지만 Servlet은 다르다.일반 App: 내가 직접 new 하고 실행한다.Servlet: 나는 로직(service())만 짜두면, 생성하고 호출하고 지우는 건 Cont..

외판원 순회 문제외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. 외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.브루트포싱으로는 무려 $O(N!)$의 시간이 걸리며, 오늘 소개할 DP를 이용한 방법으로는 $O(N^22^N)$의 시간이 걸린다. 어떻게 해결할까?1. 완전 탐색 - $O(N!)$외판원이 도시를 방문하는 순서를 모두 구한 후, 최소 비용을 찾는 방법이다.이는 $N$개의 도시를 나열하는 모든 경우를 탐색하는 것으로 $O(N!)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^22^N)$완전 탐색에서는 이미 계산한 경로의 최소 비용을 중복 계산하게..

LIS(최장 증가 부분 수열)이란?LIS란 말 그대로 어떤 수열의 부분 수열 중, 가장 긴 증가하는 부분 수열을 의미한다.예를 들어, {10, 20, 10, 30, 20, 50} 인 수열의 LIS는 {10, 20, 30, 50} 이고, 길이는 4이다. 어떻게 구할까?1. 완전 탐색 - $O(2^N)$모든 부분 수열을 구한 후, 증가하는 부분 수열 중 가장 긴 수열을 구하는 방법이다.말 그래도 모든 부분 수열을 구해야 하므로, $O(2^N)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^2)$$A_i$을 마지막으로 가지는 가장 긴 증가하는 부분 수열의 길이를 $DP[i]$라고 해보자.각 원소별로, 해당 원소($i$)보다 앞선 원소들($j$)을 탐색한다.$A_i > A_j$인 원소들 중 $DP[j..

중간에서 만나기(Meet in the Middle)이란?중간에서 만나기란 완전 탐색에 시간이 오래 걸리는 경우 대상을 두 그룹으로 나누어 탐색하여 시간을 단축하는 방법이다. 예를 들어, 크기가 $N$인 집합의 모든 부분 집합을 구하기 위해서는 $O(2^N)$의 시간이 걸린다.하지만 모든 부분 집합 중 특정 조건을 만족하는 경우를 찾기만 하면 된다면, 집합을 반으로 쪼개 각각 탐색하여 $O(2\times2^{N/2})$만에 해결할 수 있다. MITM 적용해보기백준 1208번 부분수열의 합 2 문제를 직접 풀어보자.수열의 부분수열 중 합이 $S$가 되는 경우의 수를 구하는 문제이다. 완전 탐색을 위해서는 앞에서 말했듯이 $2^{40} = 1,099,511,627,776$회의 연산이 필요한데, 이는 제한 시..

포함-배제의 원리란?포함-배제의 원리(Inclusion-Exclusion Principle)란 여러 집합들의 합집합의 크기를 구하는 데 사용하는 공식이다.포함-배제의 원리는 교집합의 크기로 합집합의 크기를 구하거나, 혹은 그 반대의 경우에 적용할 수 있다. 살펴보기두 집합의 합집합의 크기는 아래와 같은 공식으로 쉽게 구할 수 있다.$$ | A \cup B | = | A | + | B | - | A \cap B | $$ 집합의 개수를 하나만 더 늘려보자. 세 집합의 합집합의 크기는 어떻게 구할까?그림에서 볼 수 있듯이, $ | A | + | B | + | C | $를 하면 교집합 부분이 중복으로 더해진다.따라서 $ - | A \cap B | - | B \cap C | - | A \cap C | $를 해주어..