🌟🌟🌟

📌이진 탐색(Binary Search)주어진 배열의 중간값과 찾고자하는 키값의 대소를 비교하여, 배열을 절반으로 나누어가며 값의 유무를 탐색하는 검색 알고리즘. 중간값이 키값보다 크면 반으로 나눈 배열의 오른쪽 부분에서 다시 탐색하고, 중간값이 키값보다 작다면 왼쪽 배열에서 재탐색한다. 한 번 비교할 때마다 배열이 절반으로 줄어들게 되므로 배열의 크기가 커지더라도 검색 효율이 좋다. 시간 복잡도는 `O(logN)`.  단, 키값과 중간값의 대소를 비교하기 때문에 배열이 반드시 오름차순으로 정렬되어 있어야 한다.    📌구현언어: C #include int BinarySearch(int* arrPtr, int lower, int upper, int middle, int key) { // 인덱스 반환 i..

📌힙이란?'부모 노드(값)가 자식 노드(값)보다 항상 같거나 크다'라는 조건을 만족하는 완전 이진트리. 주어진 데이터를 힙으로 표현하면 최댓값은 항상 루트 노드에 위치하게 되며(단, 같은 부모를 공유하는 형제 노드의 대소 관계는 일정하지 않다. -> 왼쪽이 오른쪽보다 클 수도 있음.), 루트 노드에 최댓값을 갖는 힙을 '최대 힙(maximum heap)' 이라고 한다. 반대로 각 노드의 값이 자식 노드의 값보다 작거나 같아야하는 완전 이진 트리를 '최소 힙(minimum heap)'이라고 한다. 이를 이용하여 오름차순 또는 내림차순으로 정렬할 수 있다. 📌힙 정렬이란?자료구조 힙(Heap)의 장점을 활용하여 정렬하는 알고리즘. 주어진 배열을 힙으로 만든 뒤 가장 큰 값인 루트를 꺼내고, 루트 이외의 ..

📌퀵 정렬이란?가장 빠른 정렬 알고리즘 중 하나. 분할 정복 방법이 적용된 알고리즘. 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 알고리즘의 정렬 속도가 매우 빠르다고 해서 붙인 이름이다. 배열 내의 특정 데이터(pivot)를 기준으로 정렬할 데이터들을 왼쪽 부분 배열과 오른쪽 부분 배열로 나누어 각 부분 배열에 대해 퀵 정렬을 순환으로 적용하여 배열 전체를 정렬한다.  📌시간 복잡도최악: O(n^2) 이미 정렬되어 있는 배열을 정렬할 경우최선: O(n log n)평균: O(n log n)  📌흐름1. 입력된 데이터 수가 n인 배열 `arr`가 있을 때 `arr` 내 임의의 데이터 피벗(pivot)을 정한다. 일반적으로 배열의 첫번째 데이터(`arr[0]`)가 된다.2. 피벗을 기준으로 ..

📌알고리즘컴퓨터 과학에서 알고리즘이란 문제를 푸는 절차와 과정을 일컫는다. 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것을 뜻한다. 📌조건1. 입출력: 0개 이상의 외부 입력과 1개 이상의 출력을 생성한다.2. 명확성: 각 명령은 모호하지 않고 명확해야한다.3. 유한성: 한정된 수의 단계를 거친 후에는 반드시 종료해야한다.4. 유효성: 모든 명령은 컴퓨터에서 수행할 수 있어야 한다.5. 효율성: 알고리즘은 효율적이어야 한다.(실용적 관점) 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는 유한 개의 일련의 명령어들을 순서에 따라 구성한 것을 알고리즘이라 한다.  📌설계주어진 문제와 조건은 매우 다양..

상태 패턴이란 행위 패턴 중 하나로, 객체가 특정 상태에 따라 동작을 다르게 하는 상황에서 조건문으로 분기하는 대신 상태 자체를 객체화하여 행동 결정을 위임하는 패턴을 말한다. 상태란 객체가 가질 수 있는 어떤 조건이나 상황을 말한다. 주로 다음과 같은 경우에 사용한다. 1. 객체의 행동이 상태에 따라 달라질 때 2. 객체의 코드가 상태 전환에 따른 조건문으로 복잡해질 때 상태 클래스는 상태에 따라 행동을 구현하고, 객체는 그 상태를 가지며 상태에 따라 적절한 행동을 취한다. 예를 들어, 자판기는 돈이 충분히 들어오지 않으면 버튼이 활성화되지 않는다. 자판기는 돈이 들어온 상태와, 돈이 들어오지 않은 상태에 따라 행위가 달라진다. // 상태 인터페이스 interface VendingMachineState..

데코레이터 패턴은 구조 패턴 중 하나로 프록시를 사용하여 부가 기능을 수행하는 패턴이다. // Component 인터페이스 interface Component { String operation(); } // RealComponent 클래스 class RealComponent implements Component { @Override public String operation() { return "String"; } } // Decorator 인터페이스 interface Decorator extends Component { } // RealDecorator 클래스 class RealDecorator implements Decorator { private Component component; public R..

프록시(Proxy)는 영어로 대리자를 뜻한다. 프록시 패턴은 구조 패턴 중 하나로 클라이언트가 직접 서버에 요청하는 것이 아니라 어떤 대리자 객체를 통해 간접적으로 서버에 요청하는 패턴을 말한다. 여기서 클라이언트는 의뢰인을 의미하며 서버는 서비스나 상품을 제공하는 사람 또는 물건을 뜻한다. 즉 웹에서는 클라이언트는 사용자가 접속한 웹 브라우저가 되고, 서버는 클라이언트의 요청을 처리한다. 1. 가상 프록시(Virtual Proxy) - 실제 객체의 크기가 거대해서 생성과 접근에 비용이 많이 드는 경우 필요한 시점에만 객체를 생성하도록 지연된 초기화를 수행할 수 있다. 2. 보호 프록시(Protection Proxy) - 실제 객체에 대한 접근을 통제하여 특정 권한을 가진 사용자(클라이언트)만이 접근하도..

싱글톤 패턴은 생성 패턴 중 하나로, 프로그램 내에서 특정 인스턴스가 단 하나임을 보장하는 패턴이다. 모든 객체가 단 하나의 객체를 공유한다. public class Singleton { private static Singleton instance; // Private constructor to prevent direct instantiation private Singleton() { // Initialization if needed } // Static method to provide access to the instance public static Singleton getInstance() { if (instance == null) { instance = new Singleton(); } return..

팩토리 메서드 패턴은 생성 패턴 중 하나로 객체 생성을 공장 클래스에게 위임하는 패턴을 말한다. 클라이언트가 구체 클래스를 직접 언급하여 `new` 연산자를 호출하는 대신, 만들고자 하는 객체의 생성 책임을 맡은 공장 클래스에게 객체 생성을 맡긴다. 이름 그대로 객체를 만들어내는 공장(Factory)를 만드는 패턴이라고 할 수 있다. 공장 클래스에서 객체를 만드는 인터페이스를 제공하며, (여기서 인터페이스란 객체 생성을 하는 메서드를 뜻한다. `ShapeFactory`에서는 `createShape()` 메서드가 인터페이스라고 할 수 있다.) 해당 메서드를 포함하는 인터페이스, 즉 공장 클래스를 상속 받는 공장 서브 클래스가 만들 객체의 유형을 결정한다. 공장 인터페이스: 객체 생성 메서드를 정의하는 인터..

언어: java | Collection List와 Set의 조상. 컬렉션 클래스에 저장된 테이터를 읽고, 추가하고, 삭제하는 메서드를 가지고 있다. List Set Map은 모두 인터페이스이며 List와 Set은 공통점이 많아 Collection 인터페이스를 정의할 수 있었으나 Map은 전혀 다른 형태로 다루기 때문에 같은 부모에 포함되지 않았다. | List 순서 O, 중복 O 순서가 존재하며 중복도 허용함. ex) 대기자 명단: 순서가 존재하지만 같은 이름이 존재할 수 있음. 컬렉션프레임워크에서 가장 많이 사용되는 컬렉션 클래스. (자바3판 p.584) 구현클래스: ArrayList, LinkedList, Stack, Vector등 ArrayList (배열기반) 가장 많이 사용되는 컬렉션 클래스. 저..