📌 문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 📌 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 📌 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 📌 문제 풀이 👨🏫 접근 구간합 문제의 변형 문제이다. 대체적으로 풀이 저변으로 구간합 알고리즘으로 구간 합 테이블을 응용해야 한다. 구간합을 빠르고 쉽게 구하기 ..
Algorithm
📌 문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A..
병합정렬 우리의 앞에 두 개의 정렬된 리스트 혹은 배열이 존재한다고 생각해봅시다. 이때, 두 리스트를 합쳐서 새롭게 정렬된 리스트를 만들고자 할 때 어떻게 해야 할까요? 오름차순으로 정렬된 상태이기 때문에 가장 앞에 있는 원소를 서로 비교해서 더 작은 원소를 새로운 리스트에 넣어주면 됩니다. 예를 들자면, 현 상황에서 1과 2를 비교해서 1이 더 작기 때문에 1을 새로운 리스트에 넣어줍니다. 그 다음은 3과 2를 비교해주면 되고 2가 3보다 작기 때문에 리스트에 넣어줍니다. 이 과정을 반복해서 최종적으로 1부터 10까지 오름차순으로 정렬된 리스트로 병합할 수 있게 됩니다. 이렇게 병합하면서 서로의 수를 비교하고 새롭게 리스트에 넣어주는 알고리즘이 병합 정렬입니다. 하지만, 우리가 원하는 것은 한 리스트를..
📌 문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다. 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다. 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다. 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다. 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다. 인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들..