희디비

💡 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) NGF(4) = 2, NGF(5) = 2, NG..

💡 문제 깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다. 만약 도로 데이터가 만약 위의 그림과 같다면,오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 ..

💡 문제 큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다.진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다. ⌨ 입력 첫째 줄 정수 N ( 1 두번째 줄 N개 각 풍선의 높이 ( 1   💻 출력 / 제한 필요한 최소한의 화살의 수를 출력 하시오.  ..

💡 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ⌨ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 💻 출력 / 제한  첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. ( 시간 제한 1초 )  풀이 방법 DP 문제 입니다. dp[i] =  i번째 인덱스 까지 만들수 있는 가장 긴 증가 하는 부분 수열 입니다.dp[i] = 1로 초기화 ( 가장 ..

💡 문제 N × M크기의 배열로 표현되는 미로가 있다.101111101010101011111011 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. ⌨ 입력 첫째 줄 N, M이후 N개의 줄 : M개의 정수로 미로가 주어진다. ( 2  💻 출력 / 제한 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. / 시간 제한 : 1초 / 메모리..

💡 문제  민수에게는 1번부터 N번까지의 번호가 부여된 N(1≤N≤100)개의 물건과 최대 K(1≤K≤1000) 부피만큼을 넣을 수 있는 가방이 있다.1번 물건부터 N번 물건 각각은 부피  Vi와 가치 Ci 를 가지고 있다. (1≤Vi, Ci≤100)민수는 물건들 중 몇 개를 선택하여 가방에 넣어서 그 가치의 합을 최대화하려고 한다.단, 선택한 물건들의 부피 합이 K 이하여야 한다.민수가 가방에 담을 수 있는 최대 가치를 계산하자  ⌨ 입력  첫째 줄 : 테스트 케이스 수(T)각 테스트 별 : 물건의 수(N) 가방의 부피(K) 주어진다.이후 N개의 줄 : 부피(Vi), 가치(Ci) 💻 출력 / 제한 각 테스트 케이스 마다 담을 수 있는 최대 가치를 출력한다. (케이스당 0.2초)  풀이 방법  nap..

💡 영속성 컨텍스트란? '엔티티를 영구 저장 하는 환경' 이라는 의미 입니다.엔티티 매니저로 엔티티를 저장하거나 조회하면 영속성 컨텍스트에 엔티티를 저장하고 관리합니다. 🙄 영속성 컨텍스트 사용 이점1차 캐시 동일성 보장 트랙잭션을 지원 하는 쓰기 지연 변경 감지 지연 로딩 📝 1차 캐시 1차 캐시 등록된 entity 조회 시 :DB에서 가져 오는 것이 아닌 1차 캐시에서 가져 옵니다.-> DB 접근 횟수가 적습니다.  트랜잭션의 flush() 호출 시 :현재 객체의 상태와 비교 하여 다른 부분을 체크 하여 SQL을 작성합니다. -> 객체의 상태가 변경 될때 SQL을 작성 하지 않아도 됩니다. (변경 감지) (1차 캐시는 처음 영속 상태가 된 entity의 스냅샷을 가지고 있습니다.) 📝 동일성 ..

💡 문제  N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다.  ⌨ 입력  첫째 줄 : 테스트 케이스 수 (T)둘째 줄 : 각 테스트 케이스의 N, M ( 1 M개의 줄 : 그래프 간선 정보 x y  ( 1  💻 출력 / 제한  그래프에서의 최장 경로의 길이를 출력한다. / 1개 테스트 케이스 당 0.2초  풀이 방법  최장 경로의 뜻을 몰랐다. 코딩 테스트라 생각하고 입력을 보고 유추 해본 결과,   ..

💡 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.  어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가주어질 때,1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를..

💡 싱글톤 패턴 이란? 객체를 하나만 생성 하여 관리 하는 패턴을 말한다.객체의 생성을 private 생성자를 통해 막고, getInstance()를 통해 객체의 참조를 얻을 수 있다.  🙄 싱글톤 사용 이유 웹 어플리케이션의 경우 사용자의 요청이 매우 많다.사용자가 요청 할때 마다 객체를 생성하게 되면 리소스가 낭비 되기 때문이다. 🤔 자바로 싱글톤을 구현시 문제점 자바만을 사용해 모든 객체를 싱글톤 패턴으로 만들게 되면 문제가 있다. 1. 싱글톤 객체.getInstance()를 통해 DI    ->   구체 클래스에 의존하게 되어 OCP, DIP를 위반한다.2. 객체 마다 싱글톤 코드를 추가 해야한다.3. private 생성자를 이용할 경우 자식 클래스의 생성이 어렵다.   위 설정 클래스를 통..