누적합(Prefix Sum)과 구간합 누적합 누적합이란 나열 된 수들의 누적된 합을 뜻합니다. 즉, 이 배열의 누적합을 구하면 1 + 3 + 4 + 2 + 5 = 15가 됩니다. 누적합의 배열의 크기가 원본 배열보다 1더 큰데 이는 밑에서 설명하겠습니다. 구간합 말 그대로 나열 된 수 중에서 합을 구하고 싶은 구간의 합입니다. 만약 1번째 인덱스부터 ~ 3번째 인덱스까지의 구간합을 구한다면, 3 + 4 + 2 = 11이 됩니다. 구간합을 빠르게 구할 수 있는 공식이 있는데, 이 공식이 만들어지는 과정을 봅시다. 누적합 배열 prefixSum의 크기가 arr보다 1 더 큰 이유는 0번 인덱스 부터 n번 인덱스의 구간합을 구할 수 있게 하기 위함입니다. 이제 1번째 인덱스부터 ~ 3번째 인덱스까지의 구간합을..
문제 설명 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다. 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오. 입력 형식 캐시 크..
이 내용을 다루기 앞서 이전에 포스팅했던 캐시에 대해 읽어보시는 것을 추천드립니다. 쿠키, 캐시, 세션 이란 ? 각 개념들과 차이점에 대해 쉽게 알아보자. 쿠키, 캐시, 세션에 대해 설명하기 전에 먼저 HTTP의 특징에 대해 짚고 넘어가야합니다. HTTP에 대한 설명은 아래 포스팅 참고하시면 좋습니다. HTTP와 HTTPS의 개념 및 차이점에 대해 알아보자. HTTP ( hstory0208.tistory.com CS면접의 단골 질문인 쿠키, 캐시, 세션에 대해 각 특징과 차이점들에 대해 설명해놓았으므로 도움이 되실 겁니다. 캐시가 사용하는 리소스의 양은 무한대가 아니라 제한적이기 때문에, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야합니다. 그래서 "캐시 교체 알고리즘"으로 어떤..
문제 풀이 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요. 제한 조건 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 입출력 예 arr1 arr2 return [[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]] [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] Solutio..
문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 입출력 예 citations ret..
문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 제한 사항 n은 1 이상, 2000 이하인 정수입니다. 입출력 예 n result 4 5 3 3 Solution.java 이 문제는 DP 알고리즘을 활용하여 풀 수..