CS

[자료구조] 스택 Stack 활용: 후위 표기식 계산기 (자바/Java)

목차 스택을 활용하여 후위 표기식 계산기를 구현할 수 있다. 먼저 중위표기식을 후위 표기식으로 바꾸고, 이를 다시 계산해야 한다. 1. 중위 표기식 → 후위 표기식 이 과정이 상대적으로 까다롭다. 먼저 연산자 우선순위를 고려해야 한다. 연산자는 사칙 연산(+ - * /)과 괄호만 들어온다고 가정한다. 1. 입력이 연산자가 아닌 경우 바로 출력해준다. StringBuilder를 사용하여 sb에 append하였다. 2. 입력이 연산자인 경우 2-1. 괄호인 경우 괄호는 연산자 중에서도 특수한 경우이다. 먼저 좌괄호 '('인 경우 stack에 그냥 push한다. 그리고 우괄호 ')'가 나오면, 좌괄호가 나올 때까지 stack에 있는 연산자들을 모두 pop하여 출력한다. 그리고 좌괄호는 연산에 포함되지 않으니,..

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[알고리즘] 완전 검색, Baby-Gin (자바/Java)

목차 완전 검색 가능한 모든 경우의 수를 확인하는 기법 Brute-force, Generate-and-Test 기법 경우의 수가 작을 때 유용함 정확성은 높지만, 경우의 수가 커진다면 비효율적일 수 있음 Baby-Gin 임의의 숫자 6개를 뽑아 run과 triplet으로만 구성된 카드 = baby-gin run: 3장의 카드가 연속적인 번호를 갖는 경우 triplet: 3장의 카드가 동일한 번호를 갖는 경우 모든 경우의 수 구하기 (순열) 6개의 숫자는 6!개의 순열이 가능 먼저 6개 숫자에서 가능한 세 자리 순열(6P3)을 구하여 run 또는 triplet에 해당하는지 검사 true를 반환한다면, 다시 남은 3가지 수 중에서 순열을 구하여 run 또는 triplet에 해당하는지 검사 for (int i..

[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java)

목차 검색 자료에서 원하는 항목을 찾는 작업 종류 순차 검색 이진 검색 인덱싱 순차 검색 일렬로 되어 있는 자료를 순서대로 검색 장점: 배열, 연결 리스트 등에서 유용 단점: 자료의 크기가 큰 경우에 비효율적 정렬X 첫 번째 원소부터 마지막 원소까지 키 값이 같은 원소가 있는지 검색 동일한 원소를 찾으면 검색을 중지하고 그 인덱스를 반환 마지막 원소까지 키를 찾지 못하면 실패 시간 복잡도: O(n) 정렬O 첫 번째 원소부터 키 값보다 큰 원소가 나올 때까지 검색 동일한 원소를 찾으면 반환, 키 값보다 큰 원소가 나왔는데 찾지 못하면 검색 실패 시간 복잡도: O(n) 그러나 정렬되지 않았을 때보다 평균 비교 횟수가 절반으로 줄어든다. 이진 검색 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위..

[알고리즘] 정렬 - 선택 정렬(Selection Sort) (자바/Java)

목차 선택 정렬 개념 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식으로 정렬하는 알고리즘 시간 복잡도: O(n^2) 정렬 과정 첫 번째 원소를 두 번째부터 마지막 원소까지 비교하여 가장 작은 값과 자리 교환 2가 가장 작은 원소이고, 그 값의 index는 2이므로 arr[0]과 arr[1] 교환, arr[0]은 가장 작은 값으로 정렬 완료 두 번째, 세 번째 … 끝에서 두 번째 원소까지 같은 과정을 반복함 코드 package sort; import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] arr = { 30, 15, 2, 8, 21, 7 }; ..

[알고리즘] 정렬 - 버블 정렬(Bubble Sort) (자바/Java)

목차 버블 정렬 개념 인접한 두 개의 원소를 비교하며 정렬하는 알고리즘 정렬 과정 배열이 {30, 15, 2, 8, 21, 7}일 때를 가정한다. 원소는 자신의 오른쪽 값과 비교하기 때문에, 첫 사이클에서 비교할 마지막 index는 n-2이다. n-1(마지막 원소)와 비교를 하면 한 사이클이 끝나기 때문이다. 그렇게 한 사이클이 지나면 가장 큰 값이 배열의 오른쪽에 위치하여 다음 사이클에서는 비교 대상에서 제외된다. 두 번째는 30을 제외하고 다섯개의 원소만 비교하며 같은 과정을 반복한다. 이 사이클이 끝나면 두 번째로 큰 원소인 21이 자신의 위치를 찾아간다. 이렇게 반복하다보면 i가 1일때, 두 번째로 작은 원소인 7이 정렬되고, 자동으로 가장 작은 원소인 2는 비교 대상이 없기 때문에 모든 정렬이 ..

[자료구조] B-Tree

목차 B-트리 내장 색인: 메모리에 올려서 사용 (이진 검색 트리) 외장 색인: 메인 메모리 외부에 놓고 사용하는 색인 (B-트리) 색인의 규모가 클 경우 or 메인 메모리가 충분하지 않을 때 디스크에 두고 사용 디스크 접근 시간으로 인한 비효율을 최대한 줄여야 함 B-트리: 디스크 환경에서 사용하기 적합한 외장 다진 검색 트리 최대 M개의 자식을 가질 수 있는 B트리=M차 B트리 $$key_i−1

[자료구조] 힙 Heap

목차 Heap 힙 우선순위 큐 우선순위를 가진 원소를 삽입할 수 있고, 우선순위가 가장 큰 원소를 빼내줄 수 있는 자료구조 힙 대표적인 우선순위 큐, 완전 이진 트리(Complete Binary Tree) 구조 사용 포화 이진 트리(Full Binary Tree): 루트부터 시작해 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리, 노드의 총 수는 2k-1개 완전 이진 트리(Complete Binary Tree) 힙의 조건 완전 이진 트리 힙 특성: 모든 노드는 값을 갖고, 자식 노드(들) 값보다 크거나 같다. (최대 힙) 힙 배열 루트 노드부터 순서대로 배열에 담아 관리 삽입 A[8]에 원소 8 삽입 배열의 맨 끝에 8을 삽입 8을 자신의 부모 3과 비교 → 8이 더 크므로 자리 교환 다..

[자료구조] Array, ArrayList, LinkedList

목차 Array & ArrayList 배열 같은 종류의 데이터를 저장하기 위한 자료구조 index로 배열의 요소 참조 가능 크기가 고정 → overflow 위험 직관적으로 간단함 추가/제거 시 shift 필요 삽입 public void add(int index, E x) { if (this.numItems >= item.length || index this.numItems) { // 에러 처리 } else { for (int i = this.numItems - 1; i >= index; i--) { item[i + 1] = item[i]; // index에 값을 삽입하기 위해 오른쪽으로 한 칸씩 shift } item[index] = x; this.numItems++; } } ..