[문제] https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제 : N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 : 만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100..
코드트리 문제 : https://www.codetree.ai/missions/8/problems/number-of-distinct-segments?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이전에 올린 문제와 상당히 유사하며, 코드를 이어서 조금의 변형만 하면 된다. 문제 설명 : 이전 문제와는 다른 것은 선분을 합친다는 것이다. 선분이 겹치는 부분이 있다면 하나의 선분으로 합쳐져서 시작점과 끝점이 변경되게 된다. 그렇게 선분들의 범위를 깡그리 겹치고, 그렇게 합친 후의 선분의 ..
코드트리 문제 : https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 설명 : 먼저 입력으로 선분 몇 개가 주어지는지 받고, 그 다음 줄부터는 선분의 시작점과 끝점에 대한 정보가 주어지게 된다. 선분끼리의 점은 중복으로 주어지지는 않는다고 가정해도 좋다. 그렇게 선분이 제일 많이 겹치는 구간을 찾아 얼마나 겹쳐져 있는지 그 수를 출력하면 된다. 문제 해결..
Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. LR Technique[왼쪽 오른쪽 순회 기술] 값을 도출하기 전에 미리 왼쪽을 순회해서 얻은 값, 오른쪽을 순회해서 얻은 값을 구하고 이를 통해서 결과를 도출하여 시간 복잡도를 줄인다. 필요성 : 중복되는 계산을 줄일 수 있다. 보통 미리 만든 배열을 통해서 값을 구한다면 시간복잡도가 줄어든다. 효용성 : 시간 복잡도가 줄어든다. 물론 여기서도 반복되는 행위에 대한 시간 복잡도는 여전하지만, 반복하는 횟수와 입력된 변수 개수의 곱으로 나타나는 시간복잡도와는 달리 LR 테크닉을 사용하면 더하기로 나타나는 시간복잡도로 변하게 되어 좋다. 이걸 언제 써야할지.. 는.. 아직 와닿지 않는다. 문제를 더 풀어봐야할 것 같다..
Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. Grid Compression[좌표 압축] 입력으로 받거나 이미 주어진 수의 범위를 압축하는 것이다. (빈 공간이 없도록 압축) 쉬운 예시로 총 1~ 20의 범위를 갖게 되는 수열 1, 3, 5 ,7 ,13, 20 이 주어져있다. 이것을 압축 시켜서 [1]-1, [2]-3, [3]-5, [4]-7, [5]-13, [6]-20 으로 변환 하여, 1,2,3,4,5,6 으로 압축시키고, 압축시킨 것에서 5번을 선택하면 13의 값을 반환하도록 한다. 필요성 : 예를 들어 원소가 갖는 범위가 1~1,000,000,000 이라고 하자. 다만, 배열에서 있는 것은 1, 2, 7 , 9 , 102, 10000000 이렇게 있다고 ..
Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. Prefix Sum[누적합] 누적합 배열을 만들어서 시간복잡도를 줄인다. 특정 배열이 주어졌을 때, 그 배열을 통해서 배열의 값들에 대해 누적된 합을 '누적합 배열'에 저장한다. '누적합 배열'의 인덱스가 올라갈 때마다, 원래 주어진 특정 배열에서 접근하는 값의 인덱스도 올라간다. Ex) 특정한 배열이 주어졌을 때, 단순하게 0번부터 현재 인덱스까지의 합을 누적합 배열에 넣는다고 가정하자. 그렇다면, 특정 배열의 값이 1 3 7 11 23 이렇게 주어진다면, 누적합 배열은 1 4 11 22 45 이렇게 배열이 구성된다. 누적합 배열[0]=특정 배열[0],누적합 배열[1]=특정 배열[0]+특정 배열[1], 누적합 배열..
