GONI

계모가 3만명의 학생 정보를 주며 17,213등이 누구냐고 알아보라고 함, 텍스트 에디터와 C컴파일러 쓸 수 있게 해줌, 동점자는 없다고함(착하다...) 오늘 못 알아오면 맴매 맞는다고함(못됐다...) 콩쥐의 해결책: 정렬 알고리즘 정렬의 목적 : 찾으려고 하는 것을 쉽게 찾고자 하는데 있음(탐색을 쉽게 하려고) 버블 정렬 버블 정렬을 소개합니다 버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 마치 물 속 깊으느 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름 버블 정렬(Bubble Sort)은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행 6뽀글뽀글 위로 올라오고 뒤로 가면서 완료됨, 6을 제외하고 나머지에 대해 위의 내용을 반복 버블 정렬은 ..

트리기초 다지기 트리를 소개합니다 트리(Tree)는 이름에서 알 수 있는 것처럼, 나무를 닮은 자료구조이다 컴퓨터 과학에서도 트리는 굉장히 활용도가 높다. 운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조로 이루어져 있다. 검색 엔진이나 데이터 베이스도 트리 자료구조에 기반해서 구현된다. 트리를 열어봅시다 트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어짐 뿌리, 가지 잎 모두 실제로는 노드이다. 이들은 트리 내의 위치에 따라 명칭만 달라짐. 루트는 트리의 가장 위에 있는 노드를 가리키고, 가지는 루트와 잎 사이에 있는 모든 노드를 일컫는 말이다. 잎 노드는 끝에..

큐 먼저 들어간 데이터가 먼저 나옴, FIFO(First In First Out), 선입선출(先入先出) 큐의 주요 기능: 삽입과 제거 큐의 가장 앞 요소를 전단(Front), 마지막 요소를 후단(Rear)라고 부름 큐는 삽입(Enqueue)은 후단, 제거(Dequeue)는 전단에서 수행 끝은 새로운 시작이다: 순환 큐 순환 큐를 소개합니다. 위의 그림과 같은 방법으로 큐를 만든다면 제거(Dequeue)가 될 때마다 나머지 요소를 앞으로 이동해야하는 비용이 필요하다 그래서 전단을 가리키는 변수를 도입하여 배열의 요소를 변경하는 대신 변경된 전단의 위치만 관리할 수 있다. 요소들의 이동에 대한 부하는 해결할 수 있지만 요소를 제거하고나서 전단의 앞의 요소를 사용하지 못하여 용량이 줄어드는 문제가 생긴다 그래..

스택 주차장의 추억 '가장 먼저 들어간 데이터가 가장 마지막에 나오는 구조' 스택은 뭔가를 쌓아놓은 '더미'를 뜻함 LIFO(Last In, First Out) 요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 것이 특징 스택의 주요 기능 : 삽입과 제거 스택의 주요 기능은 '삽입(push)'와 '제거(pop)' 배열로 구현하는 스택 스택과 스택의 노드 표현하기 노드 typedef int ElementType; typedef struct tagNode { ElementType data; } NODE; 스택 구조체 typedef struct tagArrayStack { int capacity; // 용량 int top; // 최상위 노드의 위치 NODE* node; // 노드 배열 } ArraySt..

링크드 리스트 배열 유감 배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조 리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다는 점에서 중요 링크드 리스트를 소개합니다 링크드 리스트 : 노드를 연결해서 만드는 리스트 노드 : 데이터를 보관하는 필드 + 다음 연결 고리 역할을 하는 포인터 로 구성됨 헤드(머리)와 테일(꼬리)을 가지고 있음 데이터가 늘어날 때마다 테일에 붙이면 됨 C 언어로 표현하는 링크드 리스트의 노드 typedef struct Node { int Data; // 데이터 필드 struct Node* NextNode ; // 다음 노드를 가리키는 포인터 } NODE ; 링크드 리스트의 주요 연산 노..

part1. 자료구조 1장. 리스트 링크드 리스트 배열 유감 링크드 리스트를 소개합니다 C 언어로 표현하는 링크드 리스트의 노드 링크드 리스트의 주요 연산 링크드 리스트 예제 프로그램 링크드 리스트의 뒷이야기 더블 링크드 리스트 더블 링크드 리스트를 소개합니다 더블 링크드 리스트의 주요 연산 더블 링크드 리스트 예제 프로그램 환형 링크드 리스트 리스트 세계와 우로보로스, 환형 링크드 리스트 환형 더블 링크드 리스트의 주요 연산 환형 더블 리읔드 리스트 예제 프로그램 2장. 스택 스택 주차장의 추억 스택의 주요 기능 : 삽입과 제거 배열로 구현하는 스택 스택과 스택의 노드 표현하기 스택의 기본 연산 구현하기 배열로 구현하는 스택 예제 프로그램 링크드 리스트로 구현하는 스택 스택과 스택의 노드 표현하기 스택..

42.1 읽기 알고리즘 42.1.1 find 원하는 정보를 구하기만 하는 알고리즘 find 함수 원형 Init find( Init first, Init last, const T& val ) ; 입력 반복자 두 개로 검색 대상 구간을 지정, 검색하고자하는 값을 세번째 인수로 전달 값이 있으면 그 반복자 리턴, 없으면 last 리턴 예제 find #include #include #include #include using namespace std ; void main ( void ) { string name[] = { "김정수", "구홍녀", "문병대", "김영주", "임재임", "박미영", "박윤자" } ; vector as( &name[0], &name[7] ) ; vector::iterator it ; ..

41.1 셋 41.1.1 pair 연관 컨테이너(Associative Container)는 키와 값처럼 관련이 있는 데이터를 하나의 쌍으로 저장하는 컨테이너 연관 컨테이너 분류 저장 대상 키 키 + 값 중복 불허 셋 맵 중복 허용 멀티셋 멀티맵 연관 컨테이너의 반복자는 모두 양방향 반복자이다. 자료들이 항상 정렬된 상태를 유지하므로 다시 정렬할 필요가 없으며 검색이 워낙 빠르기 대문에 이분 검색을 할 필요도 없다. 언제든지 순서대로 순회하면 정렬된 결과를 얻을 수 있고 검색은 원래부터 초고속이므로 굳이 임의 접근 반복자가 필요하지도 않다. 연관 컨테이너들은 키와 값의 쌍을 표현하기 위해 pair구조체를 사용 pair 구조체 연관 컨테이너들이 키와 값의 쌍을 표현하기 위해 사용하는 일종의 유틸리티 클래스,..

40.1 벡터 40.1.1 벡터 벡터는 동일 타입의 자료 집합인 시퀀스 컨테이너 대표이다. 템플릿 기반이므로 임의 타입을 요소로 가질 수 있으며 요소의 개수에 따라 자동으로 메모리를 관리한다. 임의 타입의 동적 배열 벡터의 내구적인 구성 원리는 C의 정적 배열과 거의 유사, 특성과 장단점도 배열과 동일 요소들의 크기가 똑같고 인접한 위치에 이웃하여 배치되어, 메모리를 적게 차지하며 임의 위치를 빠른 속도로 액세스 가능 삽입, 삭제 속도가 느리다 벡터의 선언문 template class vector Type은 벡터에 저장되는 요소의 타입이며 벡터는 이 타입의 집합을 관리 Allocator는 내부적인 메모리관리에 사용되는 할당기인데 디폴트가 제공되므로 생략 가능 컨테이너 조작을 위해 사용되는 타입 타입 설명..

39-1 반복자의 정의 가. 반복자의 정의 반복자는 컨테이너의 한 지점을 가리키는 객체이다. 배열의 첨자나 연결 리스트의 노드 포인터도 이런 역할을 하지만 반복자는 기존의 포인터에 비해 훨씬 더 일반화된 개념이다. 컨테이너의 종류와 내부 구조에 상관없이 한 요소를 가리키는 목적으로 반복자라는 동일한 장치를 일관된 방법을 사용할 수 있다. 컨테이너에 대해 어떤 작업을 하고 싶다면 먼저 이 컨테이너에 저장되어 있는 요소에 접근해야 하므로 순회가 꼭 필요하다. 알고리즘이란 컨테이너 자체에 대해 적용되는 것이 아니라 결국은 컨테이너의 요소들에 적용되는 것이므로 요소를 읽고 쓸 수 있어야 하는데 이를 위해 반복자가 사용된다. 반복자를 관리하는 기본적은 방법은 ++, --, *, ==, >, < 등의 연산자이며 이..