SW_자료구조

About this offer

[자료구조] 01주차 | 자료구조란 무엇이며, 왜 배울까? 이번 주 핵심 질문 같은 데이터라도 어떻게 정리하느냐에 따라 프로그램의 성능이 달라질까? 1. 이번 주 학습목표 자료구조의 의미와 필요성을 설명할 수 있다. 자료구조와 알고리즘의 차이를 구분할 수 있다. 대표적인 자료구조를 생활 속 사례와 연결할 수 있다. 추상자료형과 성능 분석의 기본 의미를 이해할 수 있다. 2. 자료구조란? 자료구조(Data Structure)는 데이터를 저장하고 조직하여, 필요한 작업을 효율적으로 수행하도록 하는 구조이다. 책을 아무렇게나 쌓아 두면 원하는 책을 찾기 어렵다. 반면 분야별로 나누고 제목순으로 정리하면 쉽게 찾을 수 있다. 컴퓨터에서도 데이터를 어떤 구조로 저장하는지에 따라 검색·삽입·삭제에 필요한 작업량이 달라진다. 예를 들어 학생 1,000명의 성적을 관리한다면 다음과 같은 작업이 필요하다. 새로운 학생의 성적 추가하기 특정 학생의 성적 찾기 잘못 입력한 성적 수정하기 성적순으로 정렬하기 자료구조를 선택할 때는 “무엇을 저장할까?”와 함께 “어떤 작업을 자주 할까?”를 생각해야 한다. 3. 자료구조와 알고리즘의 관계 자료구조는 데이터를 조직하는 방식이고, 알고리즘은 문제를 해결하는 절차이다. 구분 자료구조 알고리즘 핵심 질문 데이터를 어떻게 저장할까? 문제를 어떤 순서로 해결할까? 예시 배열, 연결 리스트, 트리 탐색, 정렬 도서관에 비유하면 책의 배치와 분류 방식 원하는 책을 찾는 절차 책이 제목순으로 정리되어 있다면 중간 위치의 책부터 확인하며 찾는 방법을 사용할 수 있다. 정리되어 있지 않다면 한 권씩 확인해야 할 수 있다. 이처럼 데이터의 구조와 상태에 맞는 알고리즘을 함께 선택해야 한다. 4. 대표적인 자료구조 미리 보기 자료구조 주요 특징 이해를 돕는 예시 배열(Array) 같은 자료형의 원소를 연속된 메모리 공간에 저장 번호가 붙은 사물함 연결 리스트(Linked List) 각 노드가 연결 정보를 통해 다음 노드와 이어짐 서로 연결된 기차 칸 스택(Stack) 마지막에 넣은 데이터를 먼저 꺼냄 쌓아 둔 접시 큐(Queue) 먼저 넣은 데이터를 먼저 꺼냄 대기 줄 데큐(Deque) 양쪽 끝에서 데이터를 넣고 꺼냄 양쪽 출입구를 사용하는 대기 공간 트리(Tree) 데이터를 계층적인 관계로 표현 폴더와 하위 폴더 그래프(Graph) 데이터 사이의 연결 관계를 표현 지하철역과 노선 스택과 큐를 구분하는 핵심은 꺼내는 순서이다. 스택: LIFO(Last In, First Out). 나중에 들어온 것이 먼저 나간다. 큐: FIFO(First In, First Out). 먼저 들어온 것이 먼저 나간다. 이 예시들은 구조를 이해하기 위한 비유이다. 실제 프로그램에서는 필요한 연산과 사용 조건을 고려해 구현한다. 5. 자료구조의 기본 연산 연산(Operation)은 저장된 데이터를 대상으로 수행하는 작업이다. 연산 의미 성적 관리 예시 삽입(Insertion) 새로운 데이터 추가 학생 성적 추가 삭제(Deletion) 기존 데이터 제거 잘못 등록한 기록 삭제 탐색(Search) 원하는 데이터 찾기 학번으로 학생 찾기 접근(Access) 특정 위치나 키의 데이터 확인 배열의 세 번째 성적 읽기 갱신(Update) 데이터의 값 변경 성적 수정 순회(Traversal) 정해진 방식으로 원소들을 방문 모든 학생의 성적 출력 같은 연산도 자료구조에 따라 필요한 작업이 다르다. 예를 들어 배열의 중간에 데이터를 삽입하면 뒤쪽 원소를 이동해야 할 수 있다. 따라서 모든 상황에서 가장 좋은 자료구조는 없다. 자주 수행하는 작업에 적합한 구조를 선택해야 한다. 6. 추상자료형: 기능과 구현을 구분하기 추상자료형(Abstract Data Type, ADT)은 데이터와 연산, 그리고 연산이 따라야 하는 규칙을 정의한 것이다. 스택을 예로 들면 다음과 같은 기능을 생각할 수 있다. 연산 기능 push 맨 위에 데이터 넣기 pop 맨 위 데이터를 제거하며 꺼내기 peek 제거하지 않고 맨 위 데이터 확인하기 isEmpty 스택이 비어 있는지 확인하기 여기서 추상자료형은 어떤 기능을 제공하고 어떻게 동작해야 하는지를 정한다. 내부 저장 방식은 배열이나 연결 리스트 등으로 구현할 수 있다. 즉, 같은 스택의 기능을 서로 다른 방식으로 구현할 수 있다. 기능의 정의와 실제 구현을 구분하는 것이 추상화의 핵심이다. 7. 좋은 프로그램은 무엇이 다를까? 프로그램은 먼저 정확한 결과를 내야 한다. 그다음에는 문제를 해결하는 데 필요한 시간과 메모리를 살펴본다. 시간 복잡도(Time Complexity): 입력 크기에 따라 기본 연산의 횟수가 어떻게 증가하는가? 공간 복잡도(Space Complexity): 입력 크기에 따라 필요한 메모리 사용량이 어떻게 증가하는가? 분석할 때는 입력을 저장하는 공간까지 포함하는지, 추가로 사용하는 공간만 계산하는지도 밝혀야 한다. 빅오 표기법 맛보기 빅오(Big-O)는 입력 크기가 커질 때 자원 사용량의 증가율에 대한 점근적 상한을 표현한다. 정확한 실행 시간을 초 단위로 알려 주는 표기는 아니다. 표기 기본 연산 횟수의 증가 형태 대표적인 예 O(1) 입력 크기와 무관하게 일정 배열의 특정 인덱스 접근 O(log n) 입력 증가에 비해 완만하게 증가 정렬된 배열의 이진 탐색 O(n) 입력 크기에 비례해 증가 원소 전체를 한 번 확인 O(n2) 입력 크기의 제곱에 비례해 증가 모든 원소 쌍을 확인 알고리즘 분석은 입력이 커질 때 필요한 자원이 어떻게 증가하는지 비교하는 데 도움을 준다. 8. 간단한 예시: 최댓값 찾기 점수 70, 85, 90, 60 에서 최댓값을 찾는 절차를 생각해 보자. 첫 번째 점수 70 을 현재 최댓값으로 정한다. 85 와 비교해 최댓값을 85 로 바꾼다. 90 과 비교해 최댓값을 90 으로 바꾼다. 60 은 더 작으므로 최댓값을 유지한다. 최종 결과는 90이다. 원소가 n개라면 첫 번째 값을 기준으로 나머지 n−1개를 비교한다. 원소가 늘어나는 만큼 비교 횟수도 증가하므로 시간 복잡도는 O(n)이다. 이 예시에서 점수들을 담는 배열은 자료구조, 비교하며 최댓값을 찾는 절차는 알고리즘에 해당한다. 9. 이번 주 핵심 정리 핵심 개념 한 문장 정리 자료구조 데이터를 저장하고 조직하는 구조 알고리즘 문제를 해결하는 명확한 절차 연산 데이터를 추가·삭제·탐색하는 등의 작업 추상자료형 데이터와 연산의 기능 및 규칙을 정의한 것 시간 복잡도 입력 크기에 따른 기본 연산 횟수의 증가 공간 복잡도 입력 크기에 따른 메모리 사용량의 증가 자료구조를 공부한다는 것은 문제에 맞는 데이터의 조직 방식과 처리 방법을 선택하는 힘을 기르는 것이다. 10. 복습 질문 자료구조와 알고리즘의 차이를 도서관에 비유해 설명해 보자. 실행 취소 기능에 스택이 적합한 이유는 무엇일까? 프린터의 인쇄 대기 작업을 큐로 관리하면 어떤 순서로 처리될까? 같은 스택을 배열과 연결 리스트로 구현할 수 있다는 것은 무엇을 의미할까? 최댓값을 찾을 때 원소가 100개에서 1,000개로 늘어나면 비교 횟수는 어떻게 달라질까? 11. 나의 학습노트 오늘 이해한 개념: 아직 헷갈리는 개념: 생활 속에서 발견한 자료구조의 예: 다음 수업에서 확인하고 싶은 질문: 참고자료 OpenDSA 자료구조와 알고리즘 학습자료 OpenDSA 알고리즘 분석 입문 태그: 자료구조 알고리즘 추상자료형 시간복잡도 수업노트 1주차