본문 바로가기

DEV Heart/Algorithm9

[백준 1940] 주몽의 명령 (투포인터)- JAVA 문제주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다.야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다.갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다.야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다.이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다... 2026. 1. 4.
[백준 2018] 투 포인터 - JAVA 문제어떠한 자연수 N은 하나 이상의 연속된 자연수의 합으로 나타낼 수 있다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5이다.반면, 10을 나타내는 방법은 10, 1+2+3+4+이다. 자연수 N(1 1번째 줄에 자연수 N이 주어진다. 문제 분석1. 시간복잡도 분석으로 사용할 알고리즘의 범위 줄이기 -> 2초 내에 N은 최대 10,000,000이다. O(nlogn)은 초과. O(n) 적합2. 연속된 자연수를 구하는 알고리즘에 적합3. 시작 인덱스, 종료 인덱스를 지정 공식1. 투 포인터 이동 원칙startIndex가 오른쪽으로 이동하면 연속된 자연수 중 왼쪽 값 삭제 (sum 줄어듦)sum > N :sum - startIndex; startIndex++; endIndex.. 2026. 1. 3.
[백준 11986] 나머지합 구하기 - JAVA 문제N개의 수 A1, A2, ..., An이 주어졌을 떄 연속된 부분의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... +Aj(i첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10M(10⁶), 2 ≤ M ≤ 10k(10³)). 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10G(10⁹) 문제 분석1. N의 최대값은 10^6, 모든 구간의 합을 구하면 자료형의 범위를 넘어설 수 있고, 0.5초 컷 하기엔 너무 오래걸린다.2. (A+B)%C == ((A%C) + (B%C))%C 3. 구간합 배열 공식을 이용해 (i+1, j) 구간합 구하기. S[j] - S[i]4. S[j] % M 과 S[i] % M의 값이 같다면 (S[j].. 2025. 12. 31.
[백준 11660] 구간합 구하기 2 (표) - JAVA 문제NxN개의 수가 NxN 크기의 표에 채워져 있다. 표 안의 수 중 (X1, Y1)에서 (X2, Y2)까지의 합을 구한다. X는 행, Y는 열이다. 예를 들어 N=4이고, 표가 아래와 같을 때 (2,2)에서 (3,4)까지의 합은 3+4+5+4+5+6)= 27이다.1번째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다(12번째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 4개의 정수 X1,Y1,X2,Y2가 주어지며 (X1,Y1)에서 (X2,Y2)의 합을 구해 출력한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수다(X11234234534564567 문제 분석1. 수의 개수와 합을 구해야하는 횟수는 최대 100,000 -> 구간마다 합.. 2025. 12. 29.
[백준 11659] 구간합 구하기 1 (배열) - JAVA 문제수 N개가 주어졌을때 i번째 수에서 j번째 수까지의 합을 구해라.1번째 줄에 수의 개수 N(1 문제 분석1. 수의 개수와 합을 구해야하는 횟수는 최대 100,000 -> 구간마다 합을 계산하면 0.5초 안에 불가 (최악 1억회)2. 구간합을 이용하는 문제 공식배열 A = 5 4 3 2 1합배열 S 1. N의 개수를 입력받으면서 합 배열 생성 합배열 공식S[i] = S[i-1] +A[i] 2. 구간 합 구하기S[j] - S[i-1] Q. (2,4) 구간합은?-> S[4] - S[2-1] = 14 - 5 = 9pseudo code 작성하기N(숫자 개수), M(질의 개수) 저장하기for(N만큼 반복) { 합 배열 생성하기 S[i] = S[i-1] + A[i]}for(M만큼 반복) { 질의 범.. 2025. 12. 28.
[백준 1546] 평균구하기 - JAVA 문제우팡이는 기말고사를 망쳤다. 우팡이는 점수를 조작해서 집에 가져가기로 했다.일단 우팡이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다.예를 들어, 우팡이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다.우팡이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오.첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 우팡이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다. 문제 분석1. 최고 점수를 기준으로 계산해야 하므로 모든 점수를 입력 받은 후 .. 2025. 12. 27.
[백준 11720] 숫자의 합 구하기 - JAVA 문제N개의 숫자가 공백 없이 쓰여 있다. 이 숫자를 모두 합해 출력하라.1번째 줄에 숫자의 개수 N(1 문제 분석1. 범위가 100까지이므로 자료형 크기 상 int, long은 불가능. 문자열로 받아 문자 배열을 숫자형으로 변환해야함.2. 문자열로 빠르게 읽어오는 BufferReader 사용3. 문자열을 숫자형으로 변환할 때는 아스키코드에서 같은 값 차이인 48을 차감한다. (숫자 1의 아스키=1 / 문자 1의 아스키= 49) 공식1. 문자형 -> 숫자형으로 변환sum += str.charAt(i) -'0'char(문자형)을 반환 받아 숫자로 변환을 위한 아스키 코드 계산. -48 또는 -'0'pseudo code 작성하기N(숫자 개수), strNum(문자형 숫자들) 입력받기for(N만큼 반복) {.. 2025. 12. 22.
[코테연습] 점찍기 문제좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다.진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...),y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.입출력.. 2025. 7. 7.
[코테연습] 올바른 괄호 () 만들기 문제괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어"()()" 또는 "(())()" 는 올바른 괄호입니다.")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.제한사항문자열 s의 길이 : 100,000 이하의 자연수문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.입출력 예s answer"()()" true"(())()" true")()(" false"(()(" false 나의 첫 풀이- '(' 와 ')' 의 .. 2025. 7. 3.

티스토리툴바