해싱을 통한 부분수열(음수포함)의 합이 m이는 경우 이론 - java
nums = {1, 2, 3, -3, 1, 2, 2, -3} m=5정수 m과 수열 nums 배열이 주어졌을때, 연속부분수열의 합이 m(5)가 되는 경우를 구하라는 문제가 주어진다. 결론부터 말하면 정답은 5이다. 아래는 연속부분수열의 합이 m(5) 가 되는 경우들이다.[1,2,3,-3,1,2,2,-3][2,3] [2,3,-3,1,2][3,-3,1,2,2][3,-3,1,2,2][1,2,2] 어떻게 이 문제를 푸는지가 중요하다. 사실 중첩 반복문으로 풀면 누구나 풀 수 있는 문제일 것이다. 하지만 보통 이런 문제는 nums의 길이가 100,000 이상으로 나와 효율성을 고려해야 한다.나는 이 문제를 보자마자 투포인터 방식을 생각했지만 연속부분수열이기 때문에 정렬을 하지못해 규칙성이 없어 투포..
시간에 따른 시뮬레이션 문제 이론 및 풀이 (회의실 만남문제) - java
문제 :회의실에 출입할때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.오늘 회의실에는 총 n명이 입실 후 퇴실했습니다. 편의상 사람들은 1부터 n까지의 번호가 하 나씩 붙어있으며, 두 번 이상 회의실에 들어온 사람은 없습니다. 현수는 각 사람별로 회의실에 서 반드시 만난 사람은 몇 명인지 구하려 합니다. 예를 들어 입실 명부에 기재된 순서가 [2, 1, 3], 퇴실명부에 기재된 순서가 [1, 3, 2]인 경 우,‣ 1번과 2번은 반드시 만납니다.‣ 1번과 3번은 반드시 만났는지 알 수 없습니다. ‣ 2번과 3번은 반드시 만납니다. 출입명부에 [1, 2, 5, 3, 4] 퇴실명부에 [2, 3, 1, 4, 5]일때 각 번호의 사..
결정 알고리즘(Decision Algorithm) 이란?
결정 알고리즘 이란 기본적으로 이분 탐색을 이용해서 해를 구하는 알고리즘 이다. 그렇다면 이분 탐색은 무엇이냐? 이분 탐색은 기본적으로 오름차순 정렬 되어 있는 배열에서 사용가능하며, 찾고자 하는 수가 몇번째 인덱스에 있는지에 대한 해를 구할때 사용된다. int [] arr = {1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 } 이러한 배열이 있을때 , 4 가 이 배열의 몇번째 인덱스에 있는지 알고싶다. 이분탐색의 규칙은 다음과 같다. 1. lt, rt , mid 값 설정 2. target > mid 이면 , lt = mid+1 3. target 9 1-3. mid..
