CS 공부/자료구조22 연결 리스트의 개념 최종 수정 : 24.12.27연결 리스트의 개념1. 연결 리스트의 필요성배열은 순서 리스트로 기억공간에 연속적으로 저장되므로 논리적인 순서와 물리적인 순서가 같아서 원소들을 찾아 접근하기 쉬우나 삽입과 삭제 연산에서 속도와 성능이 떨어지는 문제가 있다. 이런 문제들을 해결하기 위해 연결 리스트(linked list)라는 구조가 있다. 연결리스트는 연속적인 기억공간을 필요하지 않은 리스트로, 기본단위인 노드(Node)라는 것을 포인트(point)를 이용하여 체인과 같이 연결된 구조이다. 이 구조를 통해 순서 리스트와 단점인 삽입과 삭제의 문제를 해결할 수 있다. 기억공간의 여러 곳에 흩어져 존재할 수 있어 물리적으로 연속된 기억공간을 요구하지 않는다.2. 연결 리스트의 개념노드는 데이터와 링크로 구성되어 .. 2024. 12. 27. 배열의 표현과 응용 최종 수정 : 24.12.27배열의 표현과 응용1. 다차원 배열의 행우선과 열우선배열은 행의 순서대로 연속 저장되는 방법은 행우선 방식과 열의 순서대로 연속저장되는 열우선 방식이 있다. 1) 1차원 배열논리적 표현은 왼쪽에서 오른쪽으로으로 순서대로 나열되며, 물리적으로 기억공간에서 연속적인 공간에 저장된다.배열원소의 위치 = 배열의 시작주소(배열명) + 인덱스 * 한 개의 원소(데이터 타입)크기 2) 2차원 배열2차월 배열은 행 우선과 열 우선으로 표현할 수 있다. 배열 a[m][n]에 대해 원소 a[i][j]의 위치는 다음과 같다. 행우선 방식위치 : (i * n) + j + 1저장된 주소 : a + ((i * n) + j) * l열우선 방식위치 : (j * m) + i + 1저장된 주소 : a + (.. 2024. 12. 27. 순서 리스트 최종 수정 : 24.12.26순서 리스트1. 정의리스트는 자료를 나열한 목록 또는 자료의 집합이며, 순서 리스트는 자료 간에 순서를 갖는 리스트를 의미한다. 1) 순서 리스트(dense list, linear list, sequence list)기억공간에 연속적으로 저장된 자료의 구조로, 대표적으로 배열과 같다. 장점저장구조가 단순하다.기억공간에 연속으로 저장되므로 기억효율이 좋다.순차 접근에 빠른 속도를 제공한다. 단점삽입, 삭제, 갱신의 작업에서 전체를 복사해야 하므로 작업속도가 느리다.특정 자료에 접근할 때 처음부터 순서대로 접근하면서 찾아야 하므로 접근 시간이 O(n) 시간이 걸리고, 자료가 많을수록 검색속도는 떨어진다. 2) 연결 리스트(linked list)기억공간에 불연속적으로 저장된 구조로.. 2024. 12. 27. 자료구조 - 배열 최종 수정 : 24.12.27배열1. 배열의 정의배열은 동일한 자료형을 가진 자료들을 기억공간(메모리)에 연속으로 저장된 자료구조로, 대표적인 순서리스트이다. 정수형 자료 5개를 저장하려면 5개의 변수가 필요한데, 이때 서로 다른 변수를 만들기 때문에 기억공간의 서로 다른 위치에 저장된다.연접 리스트 = 순서 리스트 = 순차 리스트 1) 변수 특징접근이 느림☞ 각 변수는 불연속 주소로 되어있어 연속적인 접근이 필요할 경우 변수마다 주소계산이 필요하다. 기억 효율 감소☞ 사용공간과 사용하지 않은 공간 사이의 갭(gap)에 의해 사용되지 못하는 공간이 발생하여 기억공간의 효율이 낮아진다. 2) 배열 특징빠른 접근 속도☞ 배열로 표기된 경우는 연속적인 기억공간을 사용한다. 기억 효율 좋음☞ 연속적인 공간 사용.. 2024. 12. 27. 성능분석 최종 수정 : 24.12.26성능분석알고리즘의 성능을 평가하는 기준은 정확성, 명확성, 간결성, 시간복잡도, 공간복잡도 등이 있다. 그러나 알고리즘을 구현한 프로그램을 실행시켜 측정된 시간을 성능 평가의 객관적 기준이 되기는 어렵다. 사용된 컴퓨터의 성능, 사용된 프로그래밍 언어에 따라 수행시간은 달라질 수 있기 때문이다. 주로 공간 복잡도와 시간 복잡도에 대한 분석으로 알고리즘의 성능을 평가한다.1. 공간 복잡도(space complexity)프로그램을 실행시켜 완료하는 데까지 소요되는 총 저장 공간을 의미한다.공간 복잡도 = 고정 공간 + 가변 공간고정 공간은 소스 코드를 저장하기 위한 공간, 사용되는 변수와 상수의 저장 공간이다.가변 공간은 실행 중에 할당되는 자료구조, 변수, 함수의 호출 등에 사.. 2024. 12. 27. 이전 1 2 3 4 5 다음
