탁월함은 어떻게 나오는가?

오늘은 LCS 알고리즘을 공부해보겠다.LCS 문제는 두 문자열의 부분 수열을 비교하는 문제로, DP를 활용하여 해결하는 문제이다.  DP를 사용하는 이유LCS 문제에서 DP가 적절한 이유는 중복되는 부분 문제와 최적 부분 구조를 가지기 때문이다.1. 중복되는 문제- 두 문자열을 비교하다 보면, 같은 부분 문자열을 여러 번 계산하게 된다. 예를 들어, DP배열을 사용하지 않는다면 dp[i][j]를 계산할 때 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] 같은 부분을 반복적으로 계산해야 한다.- DP는 이러한 중복 계산을 한 번만 계산하고 저장하여, 다시 계산하지 않도록 하는게 큰 아이디어이다. 이로 인해서 계산량을 크게 줄일 수 있다.2. 최적 부분 구조- 부분 문제들의 ..

Dynamic Programming(DP)의 장점은 중복되는 부분 문제(Overlapping Subproblems)와 최적 부분 구조(Optimal Substructure)를 가지는 문제를 효율적으로 해결할 수 있다. 오늘은 동전 교환 문제에 대해 풀어보고 설명해보자. 동전 교환 문제는 DP의 대표적인 최적화 문제이다. 주어진 금액을 특정 동전 단위로 만들기 위해 필요한 최소 동전의 개수를 구하는 것이 목표이다.   풀이를 먼저 확인해보자.123456789101112131415def coin_change(coins, amount):    dp = [float('inf')] * (amount + 1)    dp[0] = 0      for i in range(1, amount + 1):        for..

문제 설명 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i 만큼 떨어져 있습니다. (1 트럭에는 재활용 택배 상자를 최대 cap개를 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 ..

1) 서론현재 프로젝트를 진행 중이며, 주요 기능들은 어느 정도 완성되었고 실제 운영을 고려해볼 단계에 접어들었다. 이 과정에서 "운영 중 데이터베이스에 문제가 생긴다면 어떻게 대처할 것인가?" 와 "사용자들이 불편함을 느끼지 않도록 서비스를 지속적으로 제공하려면 어떻게 해야 하는가?" 라는 고민이 생겼다. 이 질문들에 대한 답으로 데이터베이스 이중화라는 솔루션에 도달했다. 소프트웨어 아키텍처의 선택은 상황에 따라 다양하게 적용될 수 있으므로, 개념적으로 정리를 잘해두는 것이 중요하다고 생각한다. 이를 기반으로 내가 원하는 아키텍처 조합을 의도한 대로 설계하고 동작하게 만들 수 있기 때문이다.      2) 데이터베이스 이중화를 도입한 이유현재 서비스는 아직 실제 사용자가 없는 초기 단계이다. 하지만 이..

문제 발생프로젝트를 작업하면서 AWS EC2의 CPU 사용률 100% 사용하게 되는 현상이 발생하였다. 100%를 사용하게되니 서버가 동작하지 않는 현상이 생겼고, 터미널로도 접속 불가, 깃 러너도 offline이 되는 등 이상 현상들이 생겼다.  이상 현상이 생기는 이유를 개인적으로 2가지로 나눠질 수 있다고 본다.1. EC2 자체 문제 (스펙, 크레딧, 하드웨어 등등)2. 해킹 일단 나는 1번이라고 생각하고 문제에 접근하였다. 그 이유는 EC2를 삭제했다가 재설치 후 깃을 사용하여 빌드하고 나서 완료되면 또 CPU 100%를 사용하는 현상이 발생하였기 때문이다.해커가 EC2에 접근해서 CPU를 사용하기에는 너무 짧은 텀이라고 판단했기 때문이다. 특히, EC2 중 스펙이 부족해서 라고 생각했으며, 이에..

org.springframework.dao.InvalidDataAccessApiUsageException: For queries with named parameters you need to use provide names for method parameters. Use @Param for query method parameters, or when on Java 8+ use the javac flag -parameters.; nested exception is java.lang.IllegalStateException: For queries with named parameters you need to use provide names for method parameters. Use @Param for quer..

문제 설명0과 1로 이루어진 2^n * 2^n 크기의 2차원 정수 배열 arr 이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다. 1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각혀 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다. arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로는 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 soultion 함수를 완성해주세요.   ..

문제 설명선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 -> 라이트닝 볼트 > 썬더 일때, 썬더를 배우려면 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬 (힐딩 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 -> 힐링 -> 라이트닝 볼트 -> 썬더 와 같은 스킬트리는 가능하지만, 썬더 -> 스파크 나 라이트닝 볼트 -> 스파크 -> 힐링 -> 썬더 와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요..