전체 글

[python3] 백준 1099 (알 수 없는 문장, DP)

접근 단어를 조합해서 비용을 최소로 만들어야 하는데 문제는 매번 다른 단어를 어떻게 조합할지가 문제다. 예를 들어 neotowheret 라는 단어가 존재할때 ne를 선택하면(문제에는 없지만 가능하다 가정하면) 비용이 0이지만, one을 선택한다면 비용이 3이다. 따라서 ne를 선택하는게 합리적으로 보이지만 ne이 이후에 가능한 단어의 조합이 없기 때문에 ne가 아닌 one을 선택해야한다. 즉, 어떤 단어를 선택해서 조합할지 + 단어를 선택하는 경우 최소비용을 적용하는등의 다양한 조합이 필요하다. 처음에는 각 단어가 가질 수 있는 모든 조합을 만들어서 대입하여 풀까도 생각했다. 예를들어 one이라면 noe,eno,oen,eon,neo 등등 모든 케이스를 뽑아서 적용하는 것이다. 그러나 50개의 단어에 대해..

[Redis] 조회수를 캐시를 적용했지만 속도가 느린 문제 해결

문제 https://github.com/sendOwlOrganization/SendOwl/issues/17 을 통해 Redis로 조회수를 갱신하도록 개선함 그러나 실제 스트레스 테스트를 진행하면 sql을 2번 날리는 경우가 더 빠르다. sql update쿼리를 통해 hit를 매번 갱신하는 경우 redis를 통해 hit를 갱신하는 경우 해결방법 1. 해당 문제를 개선하기 위해 @Async를 통해 비동기로 Redis의 함수 동작을 바꾸었다. Redis + Async처리한 경우 결과적으로 비동기 처리를 추가하면 조금 더 빨라지는것을 확인가능하다. 그러나 mysql 쿼리를 2번 날리는 것보다는 빠르지 않다. 2. Redis 시간복잡도 줄이기 https://www.notion.so/dayparallax/Redis..

[python3] 백준 7579 (앱 , DP)

우선 A,B,C,D,E 프로세스가 존재할때 메모리크기와 코스트가 존재하기 때문에 언제 최소한의 코스트를 사용하며 60이상의 메모리가 확보되는지 확인하기 위해서는 모든 경우의 수를 확인해야한다. A 활성화 비활성화 B 활성화 비활성화 C 활성화 비활성화 D 활성화 비활성화 E 활성화 비활성화 그럼 결과적으로 2**5의 경우의 수가 존재한다. 그런데 N값이 100이므로 2**100의 경우가 존재하는데 이걸 전부 확인하는 것은 말이 안된다. 따라서 백트래킹이나, DP 처럼 쳐낼수 있는 경우를 쳐내는 방식으로 진행해야한다. 그런데 이 문제는 냅색문제처럼 무게와 가중치가 존재하는 문제이다. 따라서 냅색의 알고리즘을 활용하면 되겠다는 생각이 들었다. 냅색의 경우는 무게 제한이 있었기 때문에 dp[i][w]로 2차원..

[python3] 백준 1039 (교환, BFS)

N값으로 값이 주어지는 경우 i 번째와 j 번째를 바꾸어 새로운 수를 만든다. 이때 K번 연산을 하여 나올 수 있는 최댓값을 구하면 된다. N값은 1,000,000으로 값이 커보이지만 문자열 연산을 하기 때문에 긴 값은 아니다. K값 또한 10으로 시간 복잡도상으로 큰 값이 아니다. 만약 2133이 존재할때 i=0, j=2로 하는 경우 3123이 된다. i=0,j=3로 하는 경우 3132이 된다. 그렇다면 2133을 1번 변환하여 만들수 있는 최댓값은 3132이다. 그러나 2133을 2번 변환하여 만들수 있는 값이 3321인데 3132로는 3321을 만들수 없다. 즉 K-1번의 결과값이 K번의 결과 값과는 상관이 없다. 따라서 모든 경우의 수를 탐색해야 K번 연산 했을때의 최댓값을 구할 수 있다. 그렇다..

[python3] 백준 11000 (강의실 배정, 최소힙, 그리디)

1~3시, 2~4시, 3~5시의 강의가 존재할때 최소 몇개의 강의실이 필요한지 구해야한다. 보통 강의실 문제는 그리디로 하나의 강의실이 존재할때 몇개의 수업이 가능한지는 물어보는 문제가 많았던거 같은데 이번에는 강의가 존재할때 몇개의 강의실이 필요한지 구해야한다. 처음에는 갈피를 못잡았다. 그리디 같은 느낌이 들어서 정렬을 해보고 구하려고 했는데 잘 구해지지 않았다. 그래서 알고리즘 분류를 보니 예상도 못한 우선순위 큐가 존재했다. 우선순위 큐를 사용해야한다는 힌트를 보자 바로 풀이가 떠올랐다. 우선 우선순위 큐에 들어가야하는것은 강의실이 될 수 있다. 즉, 해당 강의실을 몇시부터 몇시까지 쓰는 큐가 된다. 처음에는 1-3시에 강의실을 사용할 것이기 때문에 큐에 A(1-3)으로 넣는다. 2-4강의는 A(..

[스프링] spring MVC life cycle

Spring MVC life cycle Filter Web Application의 전역적인 로직을 담당한다. 전체적인 필터링 설정을 하는 곳이다. DispatchServlet에 들어가기 전인 Web Application단에서 실행된다. DispatchServlet (Controller 매핑) *Dispatcher==”배치 담당자” ⇒ Request에 대해서 어느 컨트롤러로 매핑시킬것인지 배치하는 역할 *요청되는 모든 Request를 받아 처리해주는 서블릿HandlerMapping에게 Request에 대해 매핑할 Controller 검색을 요청한다. HandlerMapping으로부터 Controller 정보를 반환받아 해당 Controller와 매핑시킨다. HandlerMapping(알맞은 Controll..

[스프링] DI (Dependency Injection)

스프링 DI 스프링 DI 방식 생성자 주입 말 그대로 생성자를 이용하여 의존 관계를 주입하는 방법 생성자를 통해 주입하기 때문에 해당 객체 생성시 한번의 호출이 보장된다. @Service public class UserImpl implements UserService{ private UserRepository userRepository; @Autowired public UserImpl(UserRepository userRepository){ this.userRepository = userRepository; } } 수정자 주입 메소드를 통해 객체를 주입하는 방식을 사용한다. 생성자 주입과는 달리 주입받는 객체가 변결될 가능성이 있는 경우 사용한다. (실제로 변경하는 경우는 드믈다.) @Service pu..

JWT (Json Web Token)

인증 vs 인가 인증 : 로그인, 내가 서비스의 권한을 가지고 있다는 것을 확인받는다. 인가 : 이미 인증을 받은 사용자가 서비스의 여러 기능을 사용하기 위해 자신의 권한을 사용하는 일. 로그인 후 일어나는 일 그럼 매번 요청을 보낼때마다 아이디와 패스워드를 같이 보내서 인증과 인가를 한번에 해결할 수는 없는가? ⇒ 보안상 위험하기도 하고 로그인에 필요한 암호화, 데이터베이스 통신 등등 다양한 검증 과정이 꽤 비용이 크기 때문에 이러한 방식은 비효율적이다. 따라서 쿠키, 세션, jwt 등의 다양한 방식을 활용하여 인증과 인가를 분리한다. 우선 JWT를 알아보기 전에 서버에서 자주 사용되는 세션을 간단히 이해하면 좋다. Session 세션은 서버에서 인증을 관리하는 것을 의미한다. 세션이랑 표를 끊어서 반..