배열과 연결리스트

이번 글에서는 배열과 연결리스트의 특징을 기재하고 비교해 봅니다. 배열배열은 연속된 공간에 같은 타입에 데이터를 저장하는 자료구조이다.대체적으로 프로그래밍 언어에서 배열을 선언할 때 크기를 같이 선언한다.예외적으로 자바스크립트 배열은 불연속적으로 메모리 할당 하고 연결해서 사용하여, 배열과 조금 다르게 느껴지지만 사용자 입장에서는 동일하게 배열처럼 사용한다.배열의 특징참조 성능이 좋다.O(1)의 성능배열의 시작 주소만 알면 한 번에 참조할 수 있기 때문이다.데이터 삽입, 삭제 시 용이하지 않다.중간에 데이터를 삽입할 시 그 뒤에 있는 데이터들은 모두 뒤로 밀려나서 오버헤드가 많이 발생한다.기존에 선언한 배열의 크기보다 큰 공간에 데이터를 복사해야 할 경우 기존보다 더 큰 공간을 찾아 복사까지 해야 하기 ..

• format_list_bulleted Computer Science/자료구조 & 알고리즘
• · 2025. 3. 18.
• textsms

시간복잡도와 Big-O표기법

시간복잡도: 일반적으로 알고리즘의 속도를 성능의 척도로 사용하며, 이 대목에서 시간복잡도라는 개념이 사용된다.시간복잡도는 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 나타낸다. 여기서 같은 알고리즘이더라도 컴퓨터 사양에 따라 소요되는 시간이 다를 수 있음을 인지해야 한다.따라서 코드에서 성능에 많은 영향을 주는 부분(반복문)을 찾아 실행 시간을 예측한다. 시간복잡도의 3가지 표기법주요 시간복잡도 표기법에는 7가지가 있지만, 그 중에서 가장 흔히 알려진 3가지 시간복잡도 표기법에 대해 작성한다.표기의미적용 경우Big-Ω(O(n))최악의 경우최대 실행 시간 보장Big-Ω(Ω(n))최상의 경우최소 실행 시간 보장Big-Θ (Θ(n))평균적인 경우실제 수행 시간의 경계 Big-O는 최악의 경우인데 많..

• format_list_bulleted Computer Science/자료구조 & 알고리즘
• · 2025. 3. 18.
• textsms

자료구조와 알고리즘의 개념

자료구조와 알고리즘의 개념프로그램은 자료구조와 알고리즘으로 이루어진다.자료구조효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.쉽게 생각해 데이터가 어떤 구조로 저장되어 어떻게 사용되는지를 나타낸다.ex) 배열알고리즘문제를 해결하기 위한 확실한 절차나 방법ex) 세 개의 숫자의 평균을 구하는 문제의 답을 구하기 위해(a+b+c/3)의 방법을 사용할 수도 있고, 배열에 a,b,c를 넣고 순회하며 원소 갯수만큼 나눌 수도 있다.즉, 자료구조에 따라(변수냐 배열이냐 등등) 알고리즘이 달라진다.또한 한 가지 자료구조(ex. 배열)에서도 여러가지 알고리즘이 존재한다. 프로그램을 잘 만들기 위해서는 자료구조 잘 선택해 데이터를 어떻게 저장하고 사용할지 결정하고 이에 이에 맞는 최적의 알고리..

• format_list_bulleted Computer Science/자료구조 & 알고리즘
• · 2025. 2. 20.
• textsms