본문 바로가기

BOJ15

[Algorithm] 구간 합 (Prefix Sum) 구간 합 (Prefix Sum) ■ 정의 - 수들의 나열에서 특정 구간의 합을 의미 - 보통 1차원 배열에서 인덱스 사이의 값들의 합을 구하는데 사용 ■ 구간 합 알고리즘 - 구간 합 공식: sum[j] - sum[i - 1] // i에서 j까지의 구간 합 - 합 배열(P)을 미리 계산해 두면 구간 합은 한 번에 계산 가능 - 알고리즘의 시간복잡도: O(1) ■ Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class No11659 { public static void main(String[] args) .. 2023. 5. 1.
[Algorithm] 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ■ 정의 - 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조 - 힙(heap)을 사용하여 정렬하는 알고리즘 · 힙(heap)이란?: '부모값이 자식값보다 항상 크다' 조건을 만족하는 완전이진트리 · 최대힙: 부모노드 값(key 값) ≤ 자식노드 값 (key 값) · 최소힙: 부모노드 값(key 값) ≥ 자식노드 값 (key 값) ■ 인덱스 관계 - 부모노드 인덱스: a[(i-1) / 2] - 왼쪽 자식노드 인덱스: a[i * 2 + 1] - 오른쪽 자식노드 인덱스: a[i * 2 + 2] ■ 힙 정렬 과정 Step 1. 최대 힙의 루트 노드를 마지막 배열 값과 교환, 가장 큰 값을 마지막 배열에 저장 후 힙에서 제거 Step 2. 다시 힙을 .. 2023. 4. 8.
[Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 (Greedy Algorithm) ■ 정의 다음 그림에서 최댓값을 구하려면 그림1과 같이 5 + 7 + 9 = 21로 구할 것이다. 하지만 탐욕 알고리즘은 그 순간마다 최적의 선택을 하기 때문에 그림2와 같이 5 + 10 + 4 = 19를 구할 것이다. 이처럼 탐욕 알고리즘은 지금 당장 좋은 것만을 고르며, 현재 선택이 나중에 미칠 영향은 고려하지 않는다. 따라서 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 따라서, 탐욕 알고리즘 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 거스름 돈, 활동 선택, 최.. 2023. 4. 3.
[자료구조] 이진 트리 (Binary Tree) Binary Tree (이진 트리) 각 노드가 최대 2개의 자식을 갖는 트리 ■ 정의 - 루트: 트리의 가장 윗부분에 위치하는 노드 - 리프: 트리의 가장 아랫부분에 위치하는 노드 - 안쪽 노드: 리프를 제외한 나머지 노드(루트 포함) - 자식: 어떤 노드에서 가지로 연결된 아래쪽 노드 - 부모: 어떤 노드에서 가지로 연결된 바로 위쪽 노드 - 형제: 부모가 같은 노드 - 레벨: 루트로부터 얼마나 떨어져 있는지를 나타낸 값 - 차수: 노드가 갖는 자식의 수 - 높이: 루트에서 가장 멀리 떨어진 리프까지의 거리 - 서브트리: 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리 Binary Tree(이진 트리) 순회 방법 ■ 정의 ● preorder (전위 순회) : root Node -.. 2023. 3. 29.
[자료구조] 연결리스트 (LinkedList) / 배열리스트 (ArrayList) LinkedList (연결리스트) ■ 정의 - LinkedList (연결리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 - 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값을 가지고 각 포인터 변수의 주소도 따로 존재 ■ 생성자 - LinkedList list = new LinkedList(); ■ Code 더보기 import java.util.Comparator; public class LinkedList { class Node { private E data; private Node next; Node(E data, Node next) { this.data = data; this.next = next; } } private Node hea.. 2023. 3. 28.
[JAVA] 에라토스테네스의 체 에라토스테네스의 체 ■ 정의 소수를 찾는 방법 중 하나로, '소수가 되는 수의 배수를 지우면 남은 건 소수가 된다' 라는 알고리즘 소수가 무엇인지 찾을 필요가 없으며, 2부터 자기 자신을 제외한 배수가 되는 것을 지움 ​ - 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는데, 이것이 100 이하의 소수이다. - 7까지 찾는 이유는 8, 9, 10은 2와 3의 배수이므로 이미 지워진 상태이고, √100 < 11이기 때문이다. ■ 사용 예 (백준 No.17103) 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이.. 2023. 3. 20.
[JAVA] 유클리드 호제법(GCD / LCD) GCD (최대 공약수) ■ 정의 1. 22 x 8 크기의 직사각형을 짧은 변(8)을 한 변으로 하는 정사각형으로 분할 2. 정사각형을 제외한 8 x 6 직사각형을 짧은 변(6)을 한변으로 하는 정사각형으로 분할 3. 남은 6 x 2 직사각형을 2 x 2 크기의 정사각형 3개로 분할 ☞ 마지막까지 나누어 떨어진 정사각형의 한 변의 길이가 최대 공약수가 됨 ■ Code import java.util.Scanner; public class EuclidGCD { static int gcd(int x, int y){ if(y == 0) return x; else return gcd(y, x % y); } public static void main(String[] args){ Scanner sc = new Scan.. 2023. 3. 15.
[Algorithm] 버블 정렬(Bubble Sort) 버블 정렬 (Bubble Sort) ■ 정의 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)이라고도 함 ■ 사용 예 - 총 3번의 Pass를 통해 [1, 3, 4, 6, 7]로 오름차순 정렬을 만들 수 있음 - 사진에서는 모든 비교과정을 표시하였지만, 이미 정렬된 수와의 비교는 굳이 진행하지 않아도 됨 ■ 장점 - 구현이 매우 간단하고, 소스코드가 직관적 - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 => 제자리 정렬(in-place sorting) - 안정 정렬(Stable Sort) ■ 단점 - 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장.. 2023. 3. 9.
[자료구조] 덱(Dequeue, Double-ended Queue) 덱 (Dequeue, Double-ended Queue) ■ 정의 - Dequeue(덱)은 양쪽에서 넣고 빼고가 가능한 큐 - 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라 스택, 큐 모두 사용 가능 - 스케줄링이 복잡해질수록 큐와 스택보다 효율이 잘 나옴 ■ 메소드 Deque dq = new LinkedList(); 메소드 의미 addFirst(int item) 덱의 앞 쪽에 item 삽입, 용량 초과 시 예외 발생 offerFirst(int item) 덱의 앞 쪽에 item 삽입, 용량 초과 시 false 리턴 addLast(int item) 덱의 뒤 쪽에 item 삽입, 용량 초과 시 예외 발생 offerLast(int item) 덱의 뒤 쪽에 item 삽입, 용량 초과 시 false 리턴 r.. 2023. 2. 24.
[자료구조] 스택(Stack) / 큐(Queue) 스택(Stack) ■ 정의 - 데이터를 일시적으로 쌓아 놓는 자료구조 - 데이터의 입력과 출력 순서는 후입선출 (LIFO: Last In First Out) ■ 메소드 Stack s = new Stack(); Stack s = new Stack(int capacity); // 스택의 capacity 결정 메소드 의미 push(int item) 스택에 데이터를 저장 pop() 스택의 꼭대기에 있는 데이터를 제거하고, 그 값을 반환 isFull() 스택이 empty 상태인지 확인 isEmpty() 스택이 full 상태인지 확인 clear() 스택의 모든 요소를 삭제 peek() 스택의 가장 최상위(마지막)에 위치한 데이터 출력 capacity() 스택의 용량 확인 (스택 전체 크기) size() 스택의 크기.. 2023. 2. 22.

티스토리툴바