줭 Blog 66

[알고리즘+] 최대공약수, 최소공배수

1. 최대공약수 최대공약수(GCD, Greatest Common Divisor) : 두 수의 공통된 약수 중 가장 큰 약수 '유클리드 호제법(Euclidean algorithm)'을 사용하면 효율적으로 구할 수 있음 [x와 y의 최대공약수를 구하는 법] 1) 자연수 x와 y에 대하여 x를 y로 나누어 r을 얻는다. (단, x > y일 때) 2) 다시 y를 r로 나누어 r2를 얻는다. 3) 이를 반복하다가 나머지 rn이 0이 되면 y가 최대공약수가 된다. public static void main(String[] args) { int x = 72; int y = 30; int result = gcd(x, y); } public static int gcd(int x, int y) { if(y == 0) re..

공부/알고리즘 2021.04.27

[알고리즘-04] 정렬(Sorting) - 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬

1. 정렬(Sorting) 1) 정렬이란? - 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업 - 데이터를 정렬하면 검색을 더 쉽게 할 수 있음 - 오름차순(ascending order) 정렬 : 키 값이 작은 데이터를 앞쪽에 놓는 정렬 - 내림차순(descending order) 정렬 : 키 값이 큰 데이터를 앞쪽에 놓는 정렬 - 안정된(stable) 정렬 : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것 2) 내부 정렬과 외부 정렬 - 내부 정렬(internal sorting) : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용 - 외부 정렬(external sorting) : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우..

공부/알고리즘 2021.04.22

[알고리즘-03] 재귀 알고리즘

1. 재귀란? - 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 함 - 재귀를 효과적으로 사용하면 정의뿐만이 아니라 프로그램도 간결하게 할 수 있음 2. 재귀의 사용 예 - 팩토리얼 구하기 1) 재귀적 정의 - 음이 아닌 정수 n의 팩토리얼(n!)은 재귀적으로 정의할 수 있음 ① 0! = 1 ② n > 0이면 n! = n × (n-1)! static int factorial(int n) { if (n > 0) return n * factorial(n-1); else return 1; } 2) 재귀 호출(recursive call) - 위의 코드와 같이 자기 자신과 똑같은 메서드를 호출하는 것 - factorial 메서드 안에서 factorial 메..

공부/알고리즘 2021.04.20

[자료구조-04] 큐(Queue)

1. 큐(Queue)란? - 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조 - 선입선출 구조를 가짐 - 선입선출(FIFO, First In First Out) : 가장 먼저 넣은 데이터를 가장 먼저 꺼냄 - 인큐(enqueue) : 큐에 데이터를 넣는 작업 디큐(dequeue) : 큐에서 데이터를 꺼내는 작업 프런트(front) : 데이터를 꺼내는 쪽 리어(rear) : 데이터를 넣는 쪽 - 예) 은행 창구에서 차례를 기다리는 대기열, 마트에서 계산을 기다리는 대기열 2. 배열로 큐 구현 - 스택과 마찬가지로 배열로 큐를 구현할 수 있음 - 하지만 효율성이 떨어짐 (1) 인큐(enqueue) - 32를 인큐 - 데이터를 넣기만 하면 되기 때문에 복잡도는 O(1) - 적은 비용으로 구현 가..

공부/자료구조 2021.04.20

[자료구조-03] 스택(Stack)

1. 스택(Stack)이란? - 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 - 후입선출 구조를 가짐 - 후입선출(LIFO, Last In First Out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼냄 - 푸시(push) : 스택에 데이터를 넣는 작업 팝(pop) : 스택에서 데이터를 꺼내는 작업 꼭대기(top) : 푸시와 팝을 하는 위치 바닥(bottom) : 스택의 가장 아랫부분 ※ Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용함 void x() {...} void z() { x(); } int main() { z(); } main 실행 - z 실행 - x 실행(아래 그림) - x 종료 - z 종료 - main 종료 2. 스택 구현 1) 필드 - int형..

공부/자료구조 2021.04.18

[알고리즘-02] 검색 - 선형 검색, 이진 검색

1. 검색(Searching) - 키(key)를 이용하여 원하는 데이터를 찾는 것 - 배열 검색을 위한 알고리즘 1) 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행 2) 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행 3) 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행 (1) 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법 (2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법 - 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등 다른 작업까지 고려해야 함 - 용도, 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택하기 2. 선형 검색(Linear search) 1) 선형 검..

공부/알고리즘 2021.04.18

[Java-11] 컬렉션 프레임웍 - Arrays, Comparator, Comparable, HashSet, TreeSet

1. Arrays - 배열을 다루는데 유용한 메서드가 정의되어 있음 1) 배열의 복사 copyOf(), copyOfRange() - copyOf() : 배열 전체를 복사하여 새로운 배열을 반환 - copyOfRange() : 배열의 일부를 복사하여 새로운 배열을 반환 (지정된 범위의 끝은 포함 X) int[] arr = {0,1,2,3,4}; int[] arr2 = Arrays.copyOf(arr, arr.length);// 0,1,2,3,4 int[] arr3 = Arrays.copyOf(arr, 3);// 0,1,2 int[] arr4 = Arrays.copyOf(arr, 7);// 0,1,2,3,4,0,0 int[] arr5 = Arrays.copyOfRange(arr, 2, 4);// 2,3 2)..

공부/Java 2021.04.15

[Java-11] 컬렉션 프레임웍 - Stack, Queue, Iterator, ListIterator, Enumeration

1. 스택(Stack), 큐(Queue) 1) 스택과 큐의 차이 - 스택은 'LIFO', 큐는 'FIFO'임 - LIFO(Last In First Out) : 마지막에 저장한 데이터를 가장 먼저 꺼내는 구조 - FIFO(First In First Out) : 처음에 저장한 데이터를 가장 먼저 꺼내는 구조 - 스택(LIFO)는 0, 1, 2 순으로 저장(push)한 뒤, 2, 1, 0 순으로 추출(pop) - 큐(FIFO)는 0, 1, 2 순으로 저장(push)한 뒤, 0, 1, 2 순으로 추출(pop) Q. 스택과 큐를 구현하기 위해서는 어떤 컬렉션 클래스를 사용하는 것이 좋을까? A1. 스택은 순차적으로 데이터를 추가 및 삭제하므로 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합함 A2. 큐는..

공부/Java 2021.04.14

[자료구조-02] 배열의 활용

1. 배열(Array) - 가장 기본적이고 간단한 자료구조 - 같은 자료형의 변수로 이루어진 구성 요소(component)가 모인 것 배열 ju-zero.tistory.com/22?category=900872 [Java-05] 배열(Array) - 1차원 배열 1. 배열(array)이란? 같은 타입의 여러 변수를 하나의 묶음으로 다루는 것 ex) int[] score = new int[5]; -> 5개의 int값을 저장할 수 있는 배열을 생성함 2. 배열의 선언과 생성 1) 배열 선언 - 생성된 배열을. ju-zero.tistory.com - Java를 공부하면서 배열의 개념에 대해서 익혔기 때문에, 배열을 다루는 여러 방법을 공부해보려고 한다. 2. 배열의 복제(클론) 배열이름.clone() int[]..

공부/자료구조 2021.04.13

[Java-11] 컬렉션 프레임웍 - ArrayList, LinkedList

1. 컬렉션 프레임웍(Collections Framework) 1) 컬렉션 프레임웍이란? - 데이터 군(群)을 저장하는 클래스들을 표준화한 설계 - 컬렉션(Collection) : 다수(多數)의 데이터 - 프레임웍(Framework) : 표준화된 프로그래밍 방식 - 컬렉션 클래스 : 다수의 데이터를 저장할 수 있는 클래스 2) 컬렉션 프레임웍의 장점 (1) 컬렉션, 다수의 데이터를 다루는 데 필요한 다양하고 풍부한 클래스들을 제공 -> 프로그래머의 짐을 덜어줌 (2) 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화 -> 사용법이 편리하고 재사용성이 높음 3) 핵심 인터페이스 - 컬렉션데이터 그룹을 크게 3가지 타입이 존재한다고 인식하여 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스..

공부/Java 2021.04.13