1. 연결 리스트 # 연결 리스트와 배열의 비교 - 리스트: 동일한 자료형으로 된 원소(item)들의 모임으로 선형 리스트(linear list)와 연결 리스트(linked list)로 나뉨 > 선형 리스트: 배열로 구현되는 순서 리스트(ordered list)로 원소들이 메모리에 연속적으로 저장되며 인덱스로 접근 * 배열 원소의 개수는 선언 시점 이후에는 변경할 수 없음 → 크기를 잘못 예측하지 않도록 주의해야 함 * 배열은 시스템에 의해 메모리 상에서 관리됨 > 연결 리스트: 원소들이 프로그램 실행 중에 동적으로 생성되거나 삭제되므로 리스트의 크기를 미리 예측할 필요 X 원소들은 링크(link)를 통해 서로 연결되어 있음 논리적으로는 선형적이지만 물리적으로는 분산되어 있음 * 동적 메모리 관리(dyn..

자료구조 개념 및 구현 Chapter 5. 선형 자료구조 - 연습문제 Q1. 아래와 같이 선언된 배열 A가 메모리 상에 행 우선과 열 우선 순서로 각각 저장된다고 가정할 때 배열 원소 A[2][3][4]의 주소를 계산하시오 (단, &A[0][0][0] = 1000이고, sizeof(int) = 4 이다) int A[9][7][8] ; (1) 행 우선 순서(row-major order)로 저장 시 - 1560 / 1000 + (2 * 7 * 8 + 3 * 8 + 4) * 4 (2) 열 우선 순서(column-mafor order)로 저장 시 - 1572 / 1000 + (2 * 7 * 8 + 3 + 4 * 7) * 4 Q2. 7x7 희소 행렬에서 0이 아닌 원소만을 3-순서쌍(row, column, val..

# A Maze Problem - 목표: 입구로부터 출구까지의 경로를 찾음 - 조건: 0은 지나갈 수 있고, 1은 지나갈 수 없음. 직진이나 대각선 방향으로 이동이 가능 > 한 개의 프로그램은 한 개의 미로 경로를 탐색 > 현재 위치에서 이동 가능한 모든 방향 (북쪽부터 시작 → 시계방향으로 이동) 대하여 이동 가능 여부 판단 > 처음 발견한 이동 방향으로 마우스의 좌표를 수정 > 이동 가능한 방향이 없을 경우, 이전 위치로 되돌아감 > 스택을 이용하여 이동했던 위치를 기록하고 이전 위치로 찾아감. 만일 백 트랙을 시도했으나 스택이 비어있다면 결과는 실패 # 미로 찾기 스택 구현 - 구현: 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 pop하여 이전 단계까지 돌아옴 # 미로 문제의 특성 - a..

# Deque - double-ended queue - 후단(rear)으로만 데이터를 삽입할 수 있었던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front) 와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 * 데이터 삽입: front 감소, rear 증가 * 데이터 삭제: front 증가, rear 감소 # Abstract Data Type in deque 1) 매크로 및 타입 재정의 - boolean: 참과 거짓을 return하는 함수 및 변수들을 위해 정의 - 원하지 않는 곳에서 함수가 종료될 시 return 값 통일을 위해 ERROR(-1) 정의 - int type 이외에 다른 type에도 사용하기 위해 element로 type을 정의 #define TRUE 1 #define FALSE 0 ..

# 수식의 평가 - 수식(expression): 연산자(operator)와 피연산자(operand)로 구성된 문장 - 연산자의 종류: 산술 연산자(arithmetic), 논리 연산자(logic), 대입 연산자(assignment) 등 - 피연산자의 종류: 변수(variable) 또는 상수(constant) - 수식의 표기법 # 연산자 우선순위 - 우선순위 (precedence): 아래의 표에서 번호가 높을수록 우선순위가 높음 - 결합성(associativity) 규칙: 연산의 방향을 결정 (왼 → 오 / 오 →왼) # 중위 표기법 vs 후위 표기법 # 후위 수식 계산 알고리즘 - 후위 수식의 평가: (5 7 * 9 + 3 4 / -) - 수식 평가 스택 > stack: 정수 배열로 선언된 수식 평가 스택..

# 큐 - 큐: 처리를 기다리고 있는 작업(원소)들의 리스트 - 선입 선출(FIFO, First-In, First-Out) 방식 / FCFS (First-Come, First-Served) - 우선순위를 부여하지 않음 - 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고 큐의 맨 앞(front) 원소가 먼저 삭제됨 - insert된 순서대로 처리됨 - 스택과 달리 큐의 맨 앞 원소와 맨 뒤 원소를 가리키기 위한 두 개의 front와 rear 포인터가 필요 Q = [a0, a1, ..., an-1] # 큐의 구현 - front: delete할 때 사용 - rear: stack에서의 top과 같은 역할을하며 add할 때 사용 - front와 rear 포인터의 초기 값 = -1 ← 일반적으로 이렇게 설정 - 새..

# 스택 - stack: 선형 리스트의 특별한 형태로, 책 또는 접시 같은 것들을 쌓아 둔 것을 의미 - 후입 선출(LIFO: Last-In, First-Out) 구조 - 함수 호출, 문법 검사, 연산식 평가 등에 활용 - 다음과 같이 원소들의 리스트로 정의 가능 S = [a0, a1, ...., an-1] - push: 원소 추가 / pop: 원소 삭제 - ex) 스택에 원소 a, b, c, d, e 삽입 및 삭제 # 스택 예제 (1) Balanced Parentheses - 괄호의 짝이 맞는지 확인하는 예제 [코드] // c++로 구현한 check_balance 함수 void check_balance(char* p) { struct Stack stack; create(stack, LINESIZE); ..

# Matrix (m rows * n cols) - 2차원 배열: matrix[m][n] - Space complixity = S(m,n) = m*n → 얼마만큼의 기억장소를 필요로하는지 나타내는 척도 * 배열이 int 형일 때, S(m,n) = m*n*4 ex) 4 : 배열 안의 원소를 entry라고 하며 배열을 사용해 나타낼 때는 matrix[0][2]와 같이 나타냄 # Sparse Matrix - 희소 행렬: 행렬의 값이 대부분 0인 행렬 → 저장 공간은 큰데 의미있는 값은 적음 - A[m,n]: 대부분의 값이 0이며 이 행렬을 효과적으로 저장하는 방법을 찾아야함 → 중요한 목표 # Sparse Matrix solution - 0이 아닌 element만 저장한다 - 3튜플을 가지는 배열을 활용한다 ..

자료구조 개념 및 구현 Chapter 4. 알고리즘 분석 - 연습문제 Q1. 점근적 표기법(asymptotic notation)을 사용하는 이유를 적으시오. - 알고리즘의 성능을 비교하기 위해 사용함. 입력의 수가 매우 커질 때, 알고리즘의 복잡도가 증가하는 패턴을 살펴봄 Q2. 시간 복잡도와 공간 복잡도는 각각 무엇을 의미하는가? - 시간 복잡도: 프로그램이 수행을 완료하는데 걸리는 시간 - 공간 복잡도: 알고리즘 실행에 필요한 메모리 Q3. 시간 복잡도에 대한 점근적 표기법의 세 가지 종류를 각각 설명하시오 - 상한선(Big-Oh) 표기법: 시간 복잡도 함수 f(n) = Ο(g(n))이라고 표기할 수 있다면, 이 알고리즘의 수행 시간은 상한선 c·g(n)을 넘지 않는다는 의미 - 하한선(Big-Ome..

# 알고리즘의 성능 분석 - 설계된 프로그램의 구현이 완료될 때 프로그램 성능 평가 과정이 수행됨 - 프로그램은 여러 개의 알고리즘으로 구성될 수 있으므로 알고리즘의 성능 평가라고 부를 수 있음 - 일반적인 성능 평가 질문의 예: 기준이 모호하고 구체적이지 않으므로 객관적인 평가 방법으로 사용하기에 적합하지 않음 더보기 · 프로그램이 본래의 요구 사항들을 만족하고 있는가? · 오류 없이 올바르게 동작하는가? · 효율적으로 구현되었는가? - 실행 가능한 성능 분석 기준: 공간 복잡도(space complexity), 시간 복잡도(time complexity) - 실행 가능한 성능 분석 기준은 알고리즘 간의 성능 비교가 가능함 → 측정 가능한 구체적인 수치를 제공하기 때문 # 공간 복잡도(Space Comp..