📌 추상 자료형(ADT)이란 무엇인가?자료구조를 공부하다 보면 “추상 자료형(Abstract Data Type, ADT)”이라는 용어를 자주 만나게 된다.처음 보면 이런 생각이 든다.이게 문법인가?abstract 클래스처럼 뭔가 키워드가 있는 건가? 하지만 ADT는 특정 문법이나 키워드가 있는 개념이 아니다.이는 자료구조를 설계할 때 사용하는 개념적인 단계이다. 📌 추상화란 무엇인가?추상화는 내부 구현을 몰라도 사용 방법만 알면 사용할 수 있도록 만드는 것이다.예를 들어 자동차 운전을 생각해보자.엑셀을 밟으면 앞으로 간다.브레이크를 밟으면 멈춘다.차마다 엔진 구조나 기술은 다르다.밟는 정도에 따라 반응도 조금씩 다를 수 있다.하지만 우리는 내부 엔진 구조를 몰라도 운전할 수 있다.이것이 바로 사용 관..
Algorithm
스택에 할당되는 배열int main(){ // 크기가 5인 int 형 배열 (스택 메모리에 할당됨). int array[5];} 스택에 할당되는 배열은 컴파일 시점에 크기를 알아야 한다.반면 힙에 할당되는 배열은 컴파일 시점에 크기를 정할 필요가 없다. → delete[]로 메모리 직접 해제 필요int main(){ // 크기가 5인 int 형 배열 (힙 메모리에 할당됨). int* heapArray = new int[5]; delete[] heapArray; // 크기가 10인 int 형 배열 (힙 메모리에 할당됨). // 일반 size 변수에 값을 할당하고, 그 크기로 배열의 크기를 지정할 수 있다. int size = 10; int* heapArray2 = new int[size]; delete[..
자료구조는 데이터를 어떻게 저장하고, 어떻게 접근하고, 어떻게 변경할 것인가에 대한 설계이다.같은 문제라도 어떤 자료구조를 선택하느냐에 따라 성능, 코드 복잡도, 확장성이 크게 달라진다.특히 알고리즘에서는 떼어낼 수 없는 관계이다. 본 글에서는 자료구조를 크게 선형 자료구조와 비선형 자료구조로 나누어 개요를 정리한다.1. 선형 자료구조 (Linear Data Structure)선형 자료구조는 데이터가 일렬로 나열되어 있고,각 요소가 이전/다음 요소와 논리적으로 연결되어 있다.1.1 배열 (Array)연속된 메모리 공간에 데이터를 저장인덱스를 통해 O(1) 접근 가능크기가 고정됨특징빠른 접근 속도삽입/삭제 비용이 큼 (O(n))사용 예고정 크기 데이터테이블, 버퍼1.2 동적 배열 (Vector) - 🌟배..
자료구조와 알고리즘의 역할자료구조:메모리 영역에 데이터를 잘 정리하고 저장하는 방식.데이터를 효율적으로 저장, 관리, 검색하기 위해 사용되는 논리적 구조.예를 들어, 배열, 연결 리스트, 트리, 스택, 큐 등은 메모리의 데이터를 체계적으로 관리하기 위한 자료구조이다.자료구조의 목적은 데이터 접근의 효율성을 극대화하여 프로그램이 메모리에서 데이터를 쉽게 가져오고, 수정하거나 삭제할 수 있도록 하는 것이다.알고리즘:자료구조에 저장된 데이터에 효율적으로 접근하고, 자원을 관리하여 프로그램의 성능을 올리는 방법.특정 문제를 해결하기 위해 어떤 순서로, 어떤 방식으로 데이터를 처리할지 결정하는 논리적인 절차.예를 들어, 정렬 알고리즘(버블 정렬, 퀵 정렬), 탐색 알고리즘(이진 탐색, 해시 탐색), 그래프 알고리..
※ 나동빈 저자의 '이것이 취업을 위한 코딩 테스트다 with 파이썬 '를 참고하여 정리한 글입니다. 사실 직접 시간 복잡도와 공간 복잡도를 실제로 측정하는 것은 처음 글에서 때에 따라 유용하게 쓰이지만 대부분은 빅오 표기법(Big-O Notation)을 사용하여 다루지 않겠다고 하였지만 잠깐 소개하고 넘어 가겠다. 실제로 측정하는 방법은 주로 검증을 위해 쓰이는데 우리가 처음 알고리즘을 공부한다면 너무 빅오 표기법에만 의존하지 말고 정말 내가 계산한 빅오 표기법의 성능과 일치 하는지 검증을 위해 테스트 해 보면 좋다.아마 이 과정을 통해서 더 알고리즘 성능 측정을 능숙하게 할 수 있게 될 것이며, 자신의 필요에 따라 구현하고 측정하는 개발자의 능력 또한 성장할 수 있을 것이다. 보통 어떤 알고리즘을 설..
※ 나동빈 저자의 '이것이 취업을 위한 코딩 테스트다 with 파이썬 '를 참고하여 정리한 글입니다.시간 복잡도 - 빅오 표기법에 따른 명칭빅오 표기법명칭O(1)상수 시간(Constant time)O(logn)로그 시간(Log time)O(n)선형 시간O(nlogn)로그 선형 시간O(n^2)이차 시간O(n^3)삼차 시간 O(2^n) 지수 시간O(n!)팩토리얼 시간시간 복잡도에서 연산?프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다.예를 들어, 두 정수 a, b를 더하는 '+' 연산뿐만 아니라, 두 정수 a, b의 값을 비교하는 비교 연산 또한 한 번의 연산으로 취급한다.코딩 테스트와 시간복잡도코딩 테스트에선 시간 복잡도 '시간 제한'이 있다.이 의미는 작성한 프로그램이..
알고리즘을 설계할 때, 시간 복잡도와 공간 복잡도를 고려하여 가장 효율적인 코드를 짜야 한다는 것을 알았으니이제는 어떻게 시간 복잡도와 공간 복잡도를 측정할 수 있는지 알아보자. 알고리즘 성능 정확한 측정 방법우선 시간 복잡도와 공간 복잡도를 측정하는 방법은 몇가지가 있다.시간 복잡도: 알고리즘이 얼마나 오래 걸리는지를 직접 측정하는 방식으로 실제 알고리즘 코드에서 시작 시간과 끝 시간을 측정하는 코드를 짜거나 시스템 프로파일링 도구를 사용하는 방법으로 직접 측정이 가능하다.공간 복잡도: 알고리즘이 얼마나 많은 메모리를 사용하는지 확인하기 위해서 메모리 프로파일링 도구를 사용하거나 메모리 크기를 확인하는 함수나 혹은 직접 구현하는 방법으로 직접 측정이 가능하다.수학적 계산 분석: 알고리즘의 시간 복잡도를..
※ 나동빈 저자의 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 내용을 읽고 정리한 글입니다. 복잡도(Complexity)알고리즘의 성능을 나타내는 척도이다.복잡도는 시간 복잡도와 공간 복잡도 2가지로 나눌 수 있다. 시간 복잡도(Time Complexity)특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.즉, 프로그래밍 한 코드(알고리즘)을 돌렸을때, 처리되기까지 얼마나 오랜 시간이 걸리는지를 판별하고 최대한 빠르고 원하는 성능을 뽑아낼 수 있는 효율적인 알고리즘을 설계하기 위해 필요하다. 공간 복잡도(Space Complexity)특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.즉, 프로그래밍 한 코드(알고리즘)가 컴퓨터 자원(메모리)을..
