IT is True

구간 합구간 합(Prefix Sum)은 주어진 배열의 특정 구간, 즉 배열의 연속된 요소들의 합을 의미하다. 예를 들어, 배열이 [1, 2, 3, 4, 5]라 할 때 2번째 요소부터 4번째 요수까지의 구간 합은 2 + 3 + 4로 9가 된다. 자바에서 구간 합을 구하기 위해 일반적으로 다음과 같이 반복문을 사용한다.int[] arr = {1, 2, 3, 4, 5};int sum = 0;for (int i = 1; i  다음과 같이 2차원 배열의 경우에는 2중 반복문을 통해 구한다.1 2 34 5 67 8 9 int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};int sum = 0;for (int i = 0; i   구간 합 알고리즘구간 합 알고리즘은 주어진 배열의 ..

자바의 진법 변환진법 변환은 알고리즘 문제에서 자주 활용된다. 자바에서는 이를 쉽게 활용할 수 있도록 함수를 제공하고 있다.자바에서 제공하는 함수를 통해 진법을 변환하는 방법과 직접 구현하여 변환하는 방법을 알아보고자 한다. 10진수를 N진수로 변환하기자바 내장 함수 사용10진수의 숫자를 N진수로 변환하기 위해 java.lang 패키지에서 Integer와 Long 클래스의 toString() 메서드를 제공한다.첫 번째 인자에는 변환할 수, 두 번째 인자에는 변환할 진법을 넣어 쉽게 변환할 수 있다.이 외에도 java.math 패키지의 BigInteger 클래스의 toString() 메서드를 통해 진법 변환을 할 수도 있다.public class Main { public static void main..

파스칼 삼각형파스칼의 삼각형은 블레즈 파스칼에 의해 제안된 삼각형으로 구성된 배열이다.파스칼의 삼각형은 다음과 같은 규칙이 있다.각 행의 첫 번째와 마지막의 숫자는 1이다.각 행의 중간에 위치한 숫자는 이전 행의 왼쪽 위치에 있는 숫자와 바로 위에 있는 숫자의 합이다. 구현위 두 규칙을 통해 파스칼의 삼각형을 2차원 배열로 구현해 보자.public class Main { public static void main(String[] args) { int n = 7; // 파스칼의 삼각형 만들기 int[][] pascal = new int[n][]; for (int i = 0; i // 출력1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10..

병합 정렬 (Merge Sort) 병합 정렬(Merge Sort)은 효율적이고 안정적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 알고리즘을 따른다. 병합 정렬의 기본 개념은 다음과 같다. 분할(Divide) : 입력받은 배열을 절반으로 분할하고, 길이가 1이 될 때까지 분할을 반복한다. 정복(Conquer) : 각 분할된 배열에 대해 재귀적으로 정렬을 수행한다. 병합(Merge) : 분할한 배열을 병합하면서 정렬한다. 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 과정으로 병합 과정에서 실제 정렬이 이루어진다. 병합 정렬의 시간 복잡도는 O(n log n)으로 길이가 긴 배열을 안정적으로 정렬할 때 적합한 알고리즘이다. 병합 정렬의 장단점 장점 O(n log n)의 ..

힙(heap) 힙은 이진트리로서 우선순위 큐(Priority Queue)를 사용하기 위해 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있고, 이진 탐색 트리와는 달리 중복 값을 허용하는 것이 특징이다. 힙은 완전히 정렬된 것은 아니지만 그렇다고 정렬이 안된 것도 아니다. 이러한 상태를 느슨한 정렬 상태 또는 반정렬 상태라고 한다. 힙(heap)의 종류 최소 힙(Min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 부모 노드의 키 값 ≤ 자식 노드의 키 값 최대 힙(Max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 부모 노드의 키 값 ≥ 자식 노드의 키 값 힙(heap)의 구현 힙은 배열을 이용..

Greedy Algorithm Greedy는 “탐욕스러운, 욕심 많은”이란 뜻을 가진 용어로, Greedy Algorithm은 탐욕 알고리즘이라 부른다. Greedy 알고리즘은 이름 그대로 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 그리디 알고리즘으로 문제를 해결하는 방법 선택 절차(Selection Procedure) : 현재 상태에서 최적의 해답을 선택한다. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사(Solution Check) : 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아간다. 그리디 알고리즘의 예로 거스름돈 계산 문제가 있다. 거스름 돈 n이 있고, 500원, 100원, 50원, 10원으로만 거슬러..