본문 바로가기
[JAVA][백준][실4] 1940번 주몽 https://www.acmicpc.net/problem/1940 📒 문제주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을.. 2025. 11. 6.
[JAVA][백준][S5] 2018번 수들의 합 5 https://www.acmicpc.net/problem/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을 입력받아 가지수를 출력하는 프로그램을 작성하시오. ● 시간 제한 / 메모리 제한 2초 / 32MB입력첫 줄에 정수 N이 주어진다.출력입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 .. 2025. 11. 6.
[JAVA][백준][G3] 10986번 나머지 합 https://www.acmicpc.net/problem/10986📒 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 시간 제한 / 메모리 제한 1초 / 256MB입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 입출력 예# 입력15 31 2 3 1 2# 출력17 알고리즘 분류수.. 2025. 11. 5.
[JAVA][백준][S1] 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 📒 문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1234234534564567여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 시간 제한 / 메모리 제한1 초 / 256MB입력첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 102.. 2025. 10. 24.
[JAVA][알고리즘] 구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 이다. 코딩 테스트에서 사용 빈도가 높기 때문에 알아두면 좋다. 구간 합은 누적합이라고도 하는데, C#으로 누적합을 정리해둔 글이 있으니 참고해도 좋을것 같다.해당 게시글엔 2차원 배열의 누적합도 정리해 두었다. [알고리즘] 누적합 (Prefix Sum)누적합(Prefix Sum)은 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적합을 계산하여 이를 배twd0622.tistory.com구간 합 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다. 배열 arr이 있을 때 합 배열 sumArr은 다음과 같다... 2025. 10. 21.
[JAVA] 이차원 ArrayList로 그래프 표현 코딩 테스트 문제에서 그래프 관련 알고리즘이 자주 등장한다. 이때 그래프 구조를 표현 하는데 많이 사용하는 것이 이차원 ArrayList 이다. 이차원 ArrayList의 선언부터 활용하끼 3단계로 나눠 설명하겠다. 그래프의 대한 내용은 아래 포스팅을 참고하면 된다. [자료구조] 그래프 (Graph)그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래twd0622.tistory.com01. 이차원 ArrayList 선언과 초기화그래프의 에지를 표현하는 클래스를 만들어 두었다.class Edge{ int endNode; int value; public.. 2025. 10. 20.

티스토리툴바