IT LAB

1. Binary Search 란?정렬된 자료구조에서 원하는 값을 효율적으로 찾는 알고리즘 입니다.✅ 탐색 구간을 절반씩 줄여가며 목표 값을 찾음✅ 주로 Binary Search Tree에서 사용됩니다. 과정중간 원소 선택범위 지정찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색찾을때까지 반복 (재귀적) Lower Bound찾고자 하는 값 이상의 원소들 중, 가장 작은 인덱스 값✅ 내부적으로 루프에서 불변식을 유지하면서 범위를 좁혀감➡️ 항상 반개구간을 유지함 [left, right)➡️ left: 거짓인 마지막 구간을 바로 넘어선 위치➡️ right: 항상 참인 최소 위치✅ 배열이 정렬되어 있으므로 판정 함수는 단조적➡️..

1. Selection Sort 리스트에서 가장 작은 원소를 반복적으로 선택하여, 정렬되지 않은 부분의 맨 앞 원소와 교환하는 방식의 알고리즘 과정주어진 리스트 중, 최소값을 찾음pass: 최소값을 맨 앞에 위치한 값과 교체 ➡️ 첫번째 위치가 정렬됨맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 반복 코드더보기public int[] sort(int[] arr) { for (int i = 0; i arr[j]) minIdx = j; } if (minIdx != i) swap(arr, i, minIdx); } return arr;}Time Complexity : O(n^2) 장점교환 횟수 최소화 (최대 n-1번)in-place (추가 메모리 사용 ❌) 단점성능 ..

1. Heap 이란?최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조 입니다.완전 이진트리 기반 입니다.우선순위 큐 구현에 사용됩니다. 완전 이진트리마지막 레벨을 제외한 모든 노드가 채워져 있는 이진트리 자료구조 입니다.마지막 레벨은 왼쪽부터 채워져 있어야 합니다. 인덱스모든 노드를 배열로 표현할 수 있습니다.노드 간 관계를 배열 인덱스를 통해 접근할 수 있습니다.왼쪽 자식 노드 indexindex*2 + 1오른쪽 자식 노드 index index*2 + 2부모 노드 index(index-1) / 2 2. 종류최대 힙부모 노드가 자식 노드보다 크거나 같은 값을 가집니다. 최소 힙부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 3. 연산Heapify전체 배열을 힙 구조로 만드는 연산입니다.리..

1. Trie 란?문자열 탐색에 최적화된 트리 자료구조 입니다.1959년 Edward Frendkin에 의해 처음 소개되었습니다. 2. 기능사전 검색완전한 단어나 문구를 입력하여 해당 단어를 찾아냅니다. 접두사 검색뿌리부터 시작해서 각각의 가지가 알파벳 문자를 표현합니다.표시된 노드까지 문자열을 이루고 있음을 마크해둡니다. (각 단어가 끝나는 지점에 표시)자동완성 기능을 구현할 수 있습니다. 3. 구현더보기public class MyTrie { class Node { Map children; boolean endOfWord; Node() { this.children = new HashMap(); this...

1. Graph 란?비선형: 여러 방향으로 연결될 수 있음 (한 줄로 순서 있게 나열되는 선형 자료구조와 다름) 다대다: 한 노드가 여러 노드와 연결될 수 있음 (1:n or n:n)✅ edge로 정점간의 관계를 표현합니다.✅ 계층적 형식 or 네트워크 형식. (명확한 부모-자식 관계가 존재 X)➡️ 현실세계의 다양한 문제를 효과적으로 모델링하기에 적합합니다. 예시) 현실세계 모델링더보기 정점간선SNS사람친구 관계도로망도시도로인터넷웹페이지링크추천 시스템사용자상품 관계 용어용어설명Vertex(정점)정점Edge(간선)정점과 정점을 연결하는 간선을 의미합니다.Adjacent(인접)두 정점이 간선으로 연결되어 있을 경우, 두 정점은 "인접하다" 표현합니다.Incident(부속)정점간의 연결을 담당하는 간선을 "..

1. Tree 란?그래프의 일종: 노드들과 노드들을 연결하는 엣지들로 구성된 일종의 그래프순환이 없는 연결 그래프: 모든 노드가 연결되어 있는 구조. 어떤 두 노드를 선택해도 경로는 항상 단 하나만 존재계층형 구조루트노드부터 시작해서 여러 개의 하위 노드로 분기됩니다.각 노드는 0개 이상의 자식 노드를 가질 수 있습니다. 용어 A (Root, Depth: 0, Height: 2, Level: 1) / \ / \ B C (Node, Depth: 1, Height: 1, Level: 2) / \ / \ D E F G (Leaf, Depth: 2, Height: 0, Level: 3)Node트리를 구성하는 기본단위 입니..

0. Hash Function임의의 크기의 입력을 고정된 크기의 출력으로 변환하는 함수 특징 (자료구조)특징설명 빠른 계산해시값을 매우 빠르게 계산해야 함.➡️ 테이블 크기를 2의 거듭제곱으로 두면 mod 연산 빠름균등 분산데이터가 가능한 한 모든 버킷에 고르게 분포해야 함.✅ 군집 방지: 특정 버킷에 데이터가 몰리지 않도록 함.➡️ 2의 멱수에 가깝지 않은 소수를 기반으로 한 해시가 균등성이 높음. 특징 (보안/암호학)특징설명Diffusion (확산)비슷한 입력이어도 완전히 다른 출력이 생성되어야 함. (Avalanche 효과)✅ 차분 공격 방지: 입력 구조를 출력에서 추론 불가하게 함Confusion (혼돈)입력과 출력 사이에 패턴이 없어야 하며, 관계를 예측할 수 없어야 함.✅ 선형 관계 방지: ..

1. Stack 이란?LIFO 방식으로 데이터를 저장하는 자료구조 입니다. LIFOLast-In, First Out가장 나중에 들어온 데이터가 가장 먼저 나가는 방식을 의미합니다. 2. 연산push맨 위에 항목을 추가합니다.O(1)pop맨 위에 항목을 반환하고 제거합니다.O(1)peek맨 위에 항목을 반환합니다.O(1)  3. 사용 사례Undo / Redo애플리케이션 사용중, 최근 수행한 명령을 취소 / 취소한 명령을 다시 실행 하는 기능으로 사용합니다.call stack운영체제에서 프로그램의 함수 호출을 관리하기 위해 사용합니다.괄호 짝 맞추기수식의 괄호가 문법에 맞게 작성되었는지 확인하는데 사용합니다.문자열 역순으로 변환하기문자열을 역순으로 바꾸는데 사용합니다.후위 표기법으로 변환하기수식을 후위 표..

1. Queue 란?FIFO 방식으로 데이터를 저장하는 자료구조 입니다. FIFOFirst-In, First-Out먼저 추가된 요소가 먼저 제거되는 방식을 의미합니다. 2. 주요 연산enqueue항목을 추가합니다.O(1)dequeue항목을 반환하고 제거합니다.O(1)peek항목을 반환합니다.O(1) 3. 종류Linear Queue막대 모양 형태의 큐입니다.단점- dequeue 시, 앞 공간이 비어있게 됩니다. (이 공간의 재사용이 불가합니다) Circular Queue환형 형태의 큐 입니다.  - 순환적으로 요소를 관리합니다. (시작과 끝이 연결되어 있음)장점 (Linear Queue 단점 보완) - 앞에 빈 공간이 있을 경우, 해당 공간 재사용 가능 - enqueue 시, 첫번째 요소로 포인터를 옮김P..

1. Stream집계연산을 지원하는 일련의 데이터 소스 객체입니다.데이터를 저장하는 용도가 아닌 계산하는 용도로 사용됩니다.데이터의 변환과 계산을 위한 중간 연산과 최종 연산을 제공합니다.컬렉션과 다르게 내부적으로 연산이 수행됩니다.병렬화하여 다중 코어 아키텍처를 활용하는데 유용합니다. 2. 선언형 프로그래밍과 StreamStream 객체를 사용하여 데이터 처리를 섬세하게 표현할 수 있습니다.데이터 처리 패턴이 선언적인 연산인 SQL과 유사합니다.함수형 프로그래밍과 선언형 연산을 지원하여 구현을 감추고 기능을 명시적으로 표현할 수 있습니다. 3. 파이프라인 및 연산 체이닝Stream은 더 큰 파이프라인 체이닝을 형성하기 위해 자기 자신을 리턴합니다.연산의 효율성을 위한 게으른 연산을 수행하며, 최종 연산..