본문 바로가기

Java/백준

 (106)
[JAVA] 백준 11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net - N*N개의 수가 N*N 크기의 표에 채워져 있다. (x1,y1)부터 (x2,y2)까지 합을 구하는 프로그램 - (x,y)는 x행 y열을 의미 - N=4일 때 (2,2)부터 (3,4)까지 합 3+4+5+4+5+6 = 27 문제 풀이 2차원 누적합 [Algorithm] 2차원 배열 부분합, 누적합 구하기 (velog.io) [Algorithm] 2차원 배..
[JAVA] 백준 10986 나머지 합 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net - 수 N개 A1, A2,...,An이 주어진다. - 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램 - Ai+ .... + Aj의 합이 M으로 나누어 떨어지는 (i,j) 쌍의 개수를 구해야 한다. 문제 풀이 [Java / 백준 10986] 나머지 합 (velog.io) [Java / 백준 10986] 나머지 합 백준 10986 ..
[JAVA] 백준 2559 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net - 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰값인지를 알아보고자 한다. - 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 떄, 3,-2, -4, -9, 0, 3, 7, 13, 8, -3 - 모든 연속적인 이틀간의 온도의 합은 아래와 같다. - 이때, 온도의 합이 가장 큰 값은 21이다. 문제 풀이 - 입..
[JAVA] 백준 11659 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net - 수 N개가 주어졌을 떄, i번째 수부터 j번째 수까지 합을 구하는 프로그램 문제 풀이 구간 합(Prefix Sum) 알고리즘 [알고리즘] - 구간 합 (Prefix sum) (tistory.com) [알고리즘] - 구간 합 (Prefix sum) 1. 구간 합(Prefix sum)이란? 수열에서 특정 구간의 합을 구할 때 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목..
[JAVA] 백준 12865 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net - 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. - 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. - 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. - 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 찾는 프로그램 문제 풀이 배낭 문제(K..
[JAVA] 백준 9251 LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net - LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때 , 모두의 부분 수열이 된느 가장 긴 것을 찾는 문제 - 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. - 입력으로 주어진 두 문자열의 LCS의 길이를 출력 풀이 과정 Longest Common Subsequence [..
[JAVA] 백준 2565 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net - 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. - 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. - A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 전깃줄 , A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. -..
[JAVA] 백준 11054 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net - 수열 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가 주어졌..

티스토리툴바