Nanarin🙃

일반적으로 A와 B의 최대공약수를 구하는 가장 쉬운 방법은 A와 B를 2부터 A와 B중 더 작은 수 까지 모든 자연수로 나누는 것이다. 이 방법은 수가 커질수록 시간이 오래걸려 비효율적이며, 모든 수로 나눠야 하므로 시간복잡도는 O(n)이 된다. 이때 유클리드 호제법을 사용한다. 유클리드 호제법 (Euclidean Algorithm) : 두 정수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘 A > B 일 때1. A % B = C2. B % C = D3. 위 과정을 계속 반복4. X % Y = 0, Y가 A와 B의 최대공약수 그림으로 표현해 보자 두 정수 A, B를 직사각형의 두 변의 길이라고 생각하면 직사각형을 정사각형으로 완전히 채우려고 할 때 정사각형의 가장 긴 변의 길..

0. 원형 큐 Circular Queue 란? 원형 큐란 선형 큐의 단점을 보완한 자료구조 => 선형 큐란? 데이터의 입력과 출력 순서는 선입선출 (FIFO : Fisrt In First Out) 인큐 (enqueue) : 큐에 데이터를 넣는 작업 디큐 (dequeue) : 큐에서 데이터를 꺼내는 작업 프런트 (front) : 데이터를 꺼내는 쪽 리어 (rear) : 데이터를 넣는 쪽 모두 선형 큐랑 같지만, 공간을 낭비하거나 배열 요소를 앞쪽으로 옮기지 않아도 되도록 링 버퍼를 사용하여 구현 링 버퍼(ring buffer) : 배열의 처음과 끝이 연결되었다고 보는 자료구조. 실제로 연결되어 있지는 않음 1. 원형 큐 구현 int[] cque : 원형 큐 본체용 배열 int max : 원형 큐 용량. 원..

0. 큐 Queue 란? 큐란 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 ( 큐 Queue == 선형 큐 Linear Queue ) 데이터의 입력과 출력 순서는 선입선출 (FIFO : Fisrt In First Out) ex ) 은행 창구에서 차례를 기다리는 대기열, 마트에서 계산을 기다리는 대기열 등 인큐 (enqueue) : 큐에 데이터를 넣는 작업 디큐 (dequeue) : 큐에서 데이터를 꺼내는 작업 프런트 (front) : 데이터를 꺼내는 쪽 리어 (rear) : 데이터를 넣는 쪽 1. 큐 구현 int[] que : 큐 본체용 배열 int max : 큐 용량. 큐에 저장할 수 있는 최대 데이터 수 int front : 큐에 저장된 데이터의 가장 처음 위치. 다음 dequeue()를 실행..

이진 탐색(Binary Search) 알고리즘 : 요소가 오름차순 또는 내림차순으로 정렬(sort)된 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 탐색. 선형 탐색보다 좀 더 빠르게 탐색 가능 값 53을 탐색 1. 배열의 중앙 Binary[5] 와 비교, 53 > Binary[5] => Binary[5] 이전 배열 탐색 대상에서 제외 2. Binary[6] ~ Binary[10]의 중앙 Binary[8] 과 비교, 53 Binary[8] 이후 배열 탐색 대상에서 제외 3. Binary[6] ~ Binary[7]의 중앙 Binary[6] 과 비교, 53 == Binary[6] => 탐색 성공 맨 앞의 인덱스를 pl, 맨 끝의 인덱스를 pr, 중앙 인덱스를 pc라고 할 때 ..

0. 스택 Stack 이란 ? 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 데이터의 입력과 출력 순서는 후입선출 (LIFO : Last In First Out) ex ) 자바 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서 스택 사용 푸시 (push) : 스택에 데이터를 넣는 작업 팝 (pop) : 스택에서 데이터를 꺼내는 작업 꼭대기 (top) : 푸시와 팝을 하는 위치 바닥 (bottom) : 스택의 가장 아랫부분 1. 스택 구현 int[] stk : 스택 본체용 배열. index 0인 요소가 스택의 bottom int max : 스택 용량. 스택에 저장할 수 있는 최대 데이터 수 int ptr : 스택 포인터. 다음 push()를 실행할 위치. 현재 스택에 저장되어 있는 데..

선형 탐색(Linear Search) 알고리즘 or 순차 탐색(Sequential Search) 알고리즘 : 요소가 직선 모양으로 늘어진 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 탐색 위 배열에서 요소를 탐색하면 값 5를 탐색하면 Linear[2] 에서 탐색에 성공하지만 값 3을 탐색하면 Linear에 값 3이 존재하지 않기 때문에 탐색에 실패한다. 위 예시를 보면 배열 탐색의 종료 조건이 다음 2개임을 알 수 있다. 조건 1 : 탐색할 값과 같은 요소를 발견한 경우 (탐색 성공) 조건 2 : 탐색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (탐색 실패) 배열의 요소 수가 n개 일 때 조건 1,2를 판단하는 횟수는 평균 n/2회 이다. => O(n) 메서드 seqSea..

0. 배열 Array 란 ? 배열은 같은 자료형의 변수로 이루어진 구성요소가 모인 것. 1. 배열 선언 배열을 선언하면 배열 본체와 함꼐 배열의 구성 요소의 개수를 나타내는 length라는 변수가 만들어진다. 배열 a의 각 요소의 자료형은 int이고 배열 a의 자료형은 int[5] 이다. int[] a; // 자료형이 int인 배열 a 선언 : 형식A // => int형 배열임을 명확히 알려주기 때문에 훨씬 많이 사용됨 int a[]; // 자료형이 int인 배열 a 선언 : 형식B a = new int[5] // a는 길이가 5인 배열을 참조 int[] a = new int[5]; // 선언과 참조를 한번에 int[] a = {1, 2, 3, 4, 5} // 배열 초기화, 순서대로 대입됨 int[] a..