새발블로그

그래프 (Graph)그래프란?그래프는 객체(노드 또는 정점) 간의 연결 관계(간선)를 표현하는 자료구조그래프는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 표현된다.정점: A, B, C, D, E, F간선: A-B, B-C, B-E, C-D, E-D, E-F그래프의 활용 예시분야정점 (Vertex)간선 (Edge)교통/지도도시, 정류장도로, 철도 등 이동 경로네트워크컴퓨터, 라우터통신 회선소셜 미디어사용자친구/팔로우 관계 그래프의 분류1. 방향 여부무방향 그래프 (Undirected)간선에 방향이 없음. A↔B 양방향 연결방향 그래프 (Directed)간선에 방향 있음. A→B는 가능하지만 B→A는 불가indegree: 들어오는 간선 수outdegree: 나가는 간선 수2. 간선 중복 여..

재귀 (Recursion)재귀는 복잡한 문제를 동일한 형태의 더 작은 문제로 나눠서 해결하는 기법함수 내부에서 자기 자신을 호출하여 점진적으로 문제를 해결해 나간다.재귀의 기본 구조기저 조건 (Base Case)재귀 호출을 중단하기 위한 종료 조건없을 경우 무한 호출로 이어질 수 있음재귀 호출 (Recursive Call)문제를 더 작은 형태로 분할하고 자신을 다시 호출예제 1: 팩토리얼public static int factorial(int n) { if (n == 1) return 1; // Base Case return n * factorial(n - 1); // Recursive Call}실행 흐름 (factorial(4))factorial(4)→ 4 * factor..

레퍼런스 타입 매개변수 (Reference Type Parameter)Java에서 함수에 값을 넘길 때, 기본형(Primitive Type)과 참조형(Reference Type)은 작동 방식이 다르다.1. 기본형(Primitive Type)과 참조형(Reference Type)구분예시전달 방식원본 변화기본형int, double, boolean 등값 자체를 복사❌ 변화 없음참조형List, int[], Map 등참조(주소)를 복사✅ 원본이 함께 수정됨2. 참조형 매개변수의 특징참조형 데이터는 객체의 주소값이 함수로 전달된다.함수 내에서 이 객체를 수정하면, 호출한 곳의 원본 객체도 함께 수정된다.예제: 리스트 요소 증가시키기import java.util.*;public class IncrementElemen..

변수의 유효 범위 (Variable Scope)Java에서 변수는 선언된 위치에 따라 유효 범위(Scope)가 달라진다.변수의 범위는 크게 지역 변수(Local Variable), 전역 변수(Global Variable)로 나눌 수 있습니다.1. 지역 변수 (Local Variable)메서드 내부에서 선언된 변수메서드가 실행될 때 생성되고, 종료되면 사라짐해당 메서드 내에서만 사용할 수 있음public void greet() { String name = "홍길동"; // 지역 변수 System.out.println(name);} 2. 전역 변수 (Global Variable)전역 변수는 클래스 전체에서 사용할 수 있는 변수Java에서는 전역 변수를 인스턴스 변수와 클래스 변수(static)로 ..

Set (집합)중복을 허용하지 않음요소 간 순서가 없음요소의 추가, 삭제가 가능한 mutable 컬렉션HashSet 사용법자바에서 HashSet은 Set 인터페이스를 구현한 클래스내부적으로 Hash Table을 사용하여 데이터를 저장선언Set hashset = new HashSet();초기화와 값 추가Set hashset = new HashSet() {{ add("사과"); add("배");}};주요 연산hashset.add("사과"); // 요소 추가hashset.remove("배"); // 요소 제거hashset.contains("포도"); // 존재 여부 확인 → trueSet은 같은 값을 여러 번 추가해도 한 번만 저장된다.삽입 순서나 정렬을 보장하지 않는다.커..

Direct-Address Table (직접 주소화 테이블)Direct-Address Table은 키(key)를 배열의 인덱스로 그대로 사용하는 방식데이터를 (key, value) 형태로 저장할 때, key가 배열의 인덱스로 사용된다.예시:key: 출석번호, value: 이름(3, 홍길동)특징O(1)의 시간 복잡도로 검색 가능구현이 간단하고 빠름한계점공간 낭비key가 드물게 존재하거나 크기가 크면 테이블 크기도 매우 커져야 함예) 학번을 key로 쓸 경우 → 200만 개 크기의 배열 필요key는 정수만 가능문자열 등은 배열 인덱스로 사용 불가 → 해시 함수로 변환해야 함이러한 단점을 해결한 구조가 Hash Table입니다.Hash Table (해시 테이블)Hash Table은 key를 해시 함수를 통해 ..

스택 (Stack)스택(Stack)은 데이터를 저장하는 선형 자료구조로, 후입선출(LIFO: Last-In, First-Out) 방식으로 작동기본 연산연산설명push()데이터를 스택에 추가pop()스택의 최상단 데이터 제거 및 반환peek()최상단 데이터 조회 (제거 X)isEmpty()스택이 비어 있는지 확인Java에서 Stack 사용1. Stack 클래스java.util.Stack 클래스를 사용할 수 있지만, 성능 및 설계상 이유로 권장되지 않음.2. ArrayDeque 사용 (권장)가장 효율적이고 빠른 스택 구현 방식배열 기반이므로 공간과 속도에서 유리함import java.util.*;Deque stack = new ArrayDeque();3. LinkedList 사용연결 리스트 기반 스택Dequ..

큐 (Queue)Queue(큐)는 데이터를 저장하는 선형 자료구조로, 선입선출(FIFO, First In First Out) 방식으로 동작 큐의 기본 연산연산설명enqueue()큐의 뒤(rear)에 데이터를 추가dequeue()큐의 앞(front)에서 데이터를 꺼냄Java에서 큐 사용하기1. LinkedList 기반 큐java.util.LinkedList는 큐 인터페이스를 구현한 대표적인 클래스내부적으로 이중 연결 리스트(Doubly Linked List) 구조로 구현되어 있음.import java.util.*;Queue queue = new LinkedList();2. ArrayDeque 기반 큐java.util.ArrayDeque는 동적 배열로 구현된 큐일반적으로 LinkedList보다 더 나은 성능..