ComputerScience (72) 썸네일형 리스트형 [CS] 시간 복잡도란 시간 복잡도(Time Complexity)란 시간 복잡도(Time Complexity)란 알고리즘을 실행하는데 걸리는 시간을 입력 길이의 함수로 정의한 것입니다. 알고리즘의 각 문장을 실행하는데 걸리는 시간을 측정하는 것이 아니라 알고리즘에서 연산의 수가 증가하거나 감소할 때 실행 시간의 변화(증가 또는 감소)에 대한 정보를 제공하는 것입니다. Big O 표기법으로 시간복잡도 계산하기 시간 복잡도는 입력 길이의 함수로 나타나는 시간입니다. 여기에는 입력 데이터 크기(n)와 시간에 대한 연산 수(N) 사이에 관계가 존재합니다. 이 관계는 시간 복잡도의 성장 속도(Order of growth)로 표기되며, O(n) 형태와 같은 표기법을 사용합니다. 여기서 O는 성장 속도를 나타내고 n은 입력 길이입니다. B.. [DataStructure] Map과 Hash Table Map key-value pair들을 저장하는 ADT(Abstract Data Type)이다. key는 중복되지 않고 value는 중복될 수 있다. associative array, dictionary라고 불리기도 한다. Hash Table Hash Table(해시 테이블)은 Hash function(해시 함수)과 Array을 활용한 Map 자료 구조이며, 모든 데이터에 상수 시간 접근이 가능하다. 해시 함수의 역할은 데이터를 고정된 크기의 데이터로 변환하는 것으로, 해시 테이블에서는 데이터를 정수 값으로 변환하는 함수다. 해시 함수를 통해 값이 할당된 인덱스에 데이터를 저장하며, 배열의 크기로 모듈러 연산을 통해 인덱스 위치 지정한다. Hash Collision Hash Collision(해시 충돌)은.. [DataStructure] Array, List와 Array List, Linked List 배열(Array) 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조 이다. 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 배열은 동적으로 값을 삽입하거나 삭제하려면 본래의 값들을 이동시켜야 하는 과정이 필요해서 시간이 소요된다. 리스트(List) 리스트는 값과 포인터를 묶은 로드라는 것을 포인터로 연결한 자료구조이다. 리스트는 인덱스가 없으므로, 값에 접근하기 위해 Head 포인터에서 순서대로 접근해야 한다. 접근 시간은 느리지만, 데이터 삽입과 삭제 연산 속도는 빠르다. ADT(Abstract Data Type)에서 List는 순서가 있고 중복을 허용하는, 값들을 저장하는 추상 자료형으로 사용된다. Set이나 Map을 사용하는게 더 적절한 상황이 아니라면 .. [DataStructure] Array, Dynamic Array, Associative Array Array(배열) 배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료 구조이다. 각 데이터는 인덱스로 접근 가능하며, 인덱스는 배열에서 오프셋 개념으로 이해된다. 인덱스는 0부터 시작하여 각 원소에 대한 위치를 가리킨다. 데이터는 연속된 메모리 공간에 할당되며, 인덱스는 해당 위치를 가리킨다. 이러한 동작 원리로 배열은 같은 타입의 데이터를 메모리에 연속적으로 저장한다. 2차원 배열은 메모리상 1차원으로 표현되며, 각 행은 메모리 주소로 구성됨. 연속적인 메모리 공간으로 데이터를 저장하면 CPU 캐시를 통해 데이터 접근 시간을 단축할 수 있음. 객체를 배열에 저장하는 경우 객체 배열은 각 객체의 레퍼런스를 연속적인 메모리 공간에 저장하고, 실제 객체들은 메모리에 띄엄띄엄 저장됨. Dynami.. [Java] Java에서 예외 처리 예외와 에러 프로그래밍에서 예외(Exception)란 입력 값의 처리가 불가능하거나 참조된 값이 잘못된 경우 등 애플리케이션이 정상적으로 동작하지 못하는 상황을 의미합니다. 예외는 개발자가 직접 처리할 수 있으므로 미리 코드 설계를 통해 처리할 수 있습니다. 에러(Error)란 예외와 비슷한 의미지만 엄연히 다른 용어로, 에러는 주로 자바의 가상머신(JVM)에서 발생시킵니다. 따라서 예외와 달리 애플리케이션에서 처리할 수 있는 것이 없습니다. 대표적인 예로 메모리 부족(OutOfMemory), 스택 오버플로(StackOverFlow)가 있습니다. 이러한 에러는 발생 시점에 처리하는 것이 아니라 미리 애플리케이션의 코드를 살펴보면서 문제가 발생하지 않도록 예방해서 원천적으로 차단해야 합니다. 예외 클래스 .. [Java] Compile Time과 Runtime의 차이 자바에서는 컴파일 타임과 런타임은 각각 프로그램의 실행의 두 단계를 나타냅니다. 컴파일 타임(Compile Time) 컴파일 타임은 사람이 작성한 소스 코드가 컴퓨터가 이해할 수 있는 기계어로 번역되는 단계입니다. 자바의 컴파일러는 이 단계에서 문법적 에러를 확인합니다. (e.g., missing semicolons, typos, incorrect syntax) 만약 어떤 문제도 발생하지 않으면, 자바 컴파일러(e.g., javac)는 bytecode를 생성합니다. bytecode는 기계어는 아니지만, JVM(Java Virtual Machine)에 의해 해석될 수 있습니다. 또한 아래와 같은 일들이 수행됩니다. 데이터 유형 호환성 확인 클래스 및 방법이 올바르게 선언되었는지 확인 런타임(Runtime).. [DataStructure] 우선순위 큐(Priority Queue)와 힙(Heap)의 차이 Queue Java의 Queue 인터페이스는 FIFO(First In First Out) 방식의 순차적 자료 구조를 구현 즉, 먼저 추가된 요소가 먼저 제거됨. Queue 인터페이스는 LinkedList, PriorityQueue, ArrayBlockingQueue 등 다양한 클래스에서 구현 Queue 인터페이스는 큐에 요소를 추가, 제거, 검사하는 여러 메서드를 제공하며, 다음은 가장 일반적으로 사용되는 메서드들이다. add(element): 요소를 큐의 맨 뒤에 추가, 큐가 가득 차 있으면 예외를 발생 offer(element): 요소를 큐의 맨 뒤에 추가, 큐가 가득 차 있으면 false를 반환 remove(): 큐의 앞에서 요소를 제거하고 반환, 큐가 비어 있으면 예외를 발생 poll(): 큐의 .. [DataStructure] Stack과 Queue ADT(Abstract Data Type) vs DS(Data structure) 'ADT'는 추상 자료형을 의미하며 개념적으로 어떤 동작이 있는지만 정의하고, 구현에 대해서는 다루지 않는다. 'DS'는 자료구조로, 'ADT'에서 정의된 동작을 실제로 구현한 것 Stack과 Queue는 'ADT'를 실제로 구현한 자료 구조이다. 스택(Stack)과 큐(Queue) 스택은 'Last-In-First-Out' 형태로 데이터를 저장하는 구조 데이터를 삽입하는 'push', 데이터를 뽑아내고 삭제하는 'pop', 가장 마지막에 들어온 요소를 추출하는 'peek'과 같은 동작이 있다. Queue는 'First-In-First-Out' 형태로 데이터를 저장하는 구조이며, 데이터를 삽입하는 'enqueue', 추출하.. 이전 1 2 3 4 5 ··· 9 다음
