코딩테스트7 [백준 1940번] 주몽 -투 포인터- 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,0.. 코딩테스트 2023. 4. 15. [백준 2018번] 연속된 자연수의 합 구하기 - 투 포인터 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 입력 첫 줄에 정수 N이 주어진다. 출력 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오 1. 나의 풀이 연속된 자연수들의 합이기 때문에 합 배열을 이용해보려고 생각했다. 먼저 주어진 정수 .. 코딩테스트 2023. 4. 14. [백준 11660번] 구간 합 구하기 5 백준 11659번과 다르게 이번에는 이중배열이다. 이중 배열의 구간 합은 조금 더 까다롭다. 위 그림을 코드로 나타내면 다음과 같다. D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][D[j-1] + A[i][j] 이제 구간 합을 구해보자 코드로 작성하면 D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1] 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4).. 코딩테스트 2023. 4. 12. [백준 11659번] 구간 합 구하기 4 구간 합은 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘이다. 합 배열 S 정의 S[i] = A[0] + A[1] + .... A[i] // A[0]부터 A[i]까지의 합 합 배열을 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소하게 된다. 합 배열 S를 만드는 법 S[i] = S[i-1] + A[i] 합 배열을 이용해 구간 합을 구하는 법 S[j] - [S-i] i에서 j까지의 구간 합 /* ex) 2~5 까지의 구간 합 S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5] s[1] = A[0] + A[1] */ 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력.. 코딩테스트 2023. 4. 12. Java를 이용하여 1 ~ N 숫자에서 소수 찾기 2~N까지의 자연수가 주어졌을 때 소수를 찾아 배열에 담으려 할 때 소수를 어떻게 찾아야할까? cf) 소수 : 1보다 큰 자연수 중에서 1과 자신만을 약수로 가지는 수 1. 내가 생각한 소수 찾기 가장 기초적이면서 단순한 방법으로 2~N 숫자를 1부터 해당 숫자까지 나누어 약수의 개수가 2개인 것들만 찾아낸다. Scanner scan = new Scanner(System.in); int N = scan.nextInt(); //2~N까지의 자연수를 담은 배열 생성 0,1은 소수가 아니기 때문에 int[] arr = new int[N]; for(int i = 1; i < N; i++){ arr[i] = i; } //소수를 담을 ArrayList 생성, 몇 개가 나올지 모르므로 List로 생성함 ArrayLi.. 코딩테스트 2023. 4. 11. [프로그래머스] 문자열 정렬하기 (2) 문제 설명 영어 대소문자로 이루어진 문자열 my_string이 매개변수로 주어질 때, my_string을 모두 소문자로 바꾸고 알파벳 순서대로 정렬한 문자열을 return 하도록 solution 함수를 완성해보세요. 제한 사항 0 코딩테스트 2022. 10. 5. [프로그래머스] 약수 구하기 문제 정수 n이 매개변수로 주어질 때, n의 약수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요. 제한사항 1 코딩테스트 2022. 10. 5. 이전 1 다음
