전체 글 (74) 썸네일형 리스트형 덱(Deque) Goal 덱을 구현 할 수 있다 덱의 구조를 그리고 설명할 수 있다 덱(Deque) 데이터의 입/출력이 양 끝단에서만 이루어지는 형태의 자료구조 특징 원소의 추가 O(1) 원소의 삭제 O(1) 원소의 확인 O(1) - 제일 앞, 뒤쪽만 확인 가능 삽입 삭제가 양 끝단에서만 이루어지는 제한적 선형 자료구조이다 덱(Deque)은 앞, 뒤 양쪽에서 데이터의 삽입 삭제가 가능하다는 점에서 스택이나 큐보다 덜 제한적이다. 이런 특징 때문에 Deque을 Stack또는 Queue형태로 사용이 가능하다. (입출력 부분의 함수를 제한을 걸면된다) 덱(Deque)의 구현 BOJ 덱 구현 문제 : https://www.acmicpc.net/problem/10866 - 배열 덱 - https://github.com/jihyu.. 큐(Queue) Goal 큐를 구현할 수 있다. (배열, 링크드 리스트로 구현) 큐 구조를 그리고 설명할 수 있다 큐가 사용되는 예시를 들고, 어떨 때 사용되는지 설명할 수 있다 큐(Queue) 데이터의 입력은 가장 뒤쪽(back, rear)에서, 출력은 가장 앞쪽(front)에서 이루어지는 형태의 제한적 선형자료구조 먼저 입력된 순서대로 출력되는 선입선출(FIFO) 형태의 자료구조 특징 원소의 추가 O(1) 원소의 삭제 O(1) 제일 앞쪽(front), 제일 뒤쪽(back) 원소 확인 O(1) => 원칙적으로 중간에 있는 데이터 확인 및 변경 불가능 원형 큐(Circular Queue) 큐를 논리적으로 원형 형태로 설계한 자료구조 원형큐는 큐를 배열로 구현했을 때 발생하는 문제점을 보완하기 위해 고안된 자료구조이다. .. 스택(Stack) Goal 스택을 구현할 수 있다. (배열 또는 연결리스트로 구현) 스택 구조를 그리고 스택에 대해 설명할 수 있다 스택이 사용되는 예시를 들 수 있고, 어떨 때 사용되는지 설명할 수 있다 스택(Stack) 한쪽 끝에서만 데이터가 삽입, 삭제가 일어나는 제한적 선형 자료구조 먼저 들어온 데이터가 나중에 출력되는 선입후출 FILO(First In Last Out) 형태의 자료구조 (FIFO = LIFO) 성질 데이터의 삽입, 삭제가 한쪽 끝에서만 이루어지는 제한적 선형자료구조 선입 후출 FILO(First In Last Out) (= 후입 선출 : LIFO) 형태의 자료구조 (스택, 큐, 데크와 같이 삽입 삭제가 특정 위치에서만 제한적으로 이루어지는 자료구조를 제한적 선형자료구조라 한다) 특징 원소의 추가 .. 연결 리스트(Linked List), 리스트(List) Goal 연결 리스트의 특징을 이해하고 장단점을 말할 수 있다 연결 리스트를 구현할 수 있다 배열과 연결 리스트의 차이점을 알고 적절히 사용할 수 있다 연결 리스트(Linked List) 개념 : 각 노드를 간선으로 연결시켜 표현한 자료구조 또는 그러한 표현 기법 특징 일반적으로 배열과 반대되는 특징들을 가지고 있다 연속된 메모리 공간에 저장할 필요가 없다 임의 접근이 불가능하다 저장 공간의 활용이 자유롭다 장단점 연결 리스트는 포인터의 연결을 맺고 끊을 수 있기 때문에 다음과 같은 장단점이 있다 [장점] 삽입, 삭제가 용이하다 배열에 비해 저장 공간 활용이 자유롭다 => 필요할때 추가/삭제가 가능하기 때 낭비되는 메모리가 적고 크기 변환에 유연하다 [단점] 배열에 비해 탐색이 느리다 O(n) => 임의.. 배열 Goal 배열의 특징을 이해하고 장단점을 말할 수 있다 배열의 장단점을 이해하고 적절한 상황에 맞게 배열을 사용할 수 있다 배열(Array) 개념 : 동일한 자료형을 연속적인 메모리 공간에 저장한 자료구조 특징 인덱스(index)를 사용하여 임의 접근(Random Access)이 가능하다. 각 항목이 동일한 자료형이므로 동일한 크기를 갖는다 저장 공간의 크기가 고정적이다. 장단점 [장점] 1. 원소 접근이 빠르다 원소 접근하는데 걸리는 시간이 상수 시간 O(1)이다. (배열시작 주소 + index * 원소 크기)로 해당 원소에 접근이 가능 => Random Access 가능 2. 캐시 적중률(Cache hit rate)이 높다 연속된 메모리 공간에 저장되기 때문에 캐시 지역성(cache locality).. 추상 자료형(Abstract Data Type) Goal 추상화와 추상자료형(ADT)에 대한 이해 추상 자료형을 정의할 수 있다 자료형(Data Type) 데이터를 식별하는 구분, 연산, 저장 방법 등을 모두 포함한 것 추상화(Abstraction) 핵심 개념이나 기능을 간추려 내는 것 => 개념을 만들어 가는 과정(개념의 일반화) 특징 자료구조에서 추상화는 세부 구현으로 부터 분리하여 개념을 일반화 시키는 것을 의미 (데이터 모델링) 무엇(what)인지는 정의하지만 어떤 언어를 사용해서 어떻게(how)구현할 것인지는 정의하지 않음 추상 자료형(Abstract Data Type : ADT) 세부 구현으로부터 분리해 핵심 개념이나 기능을 간추려 낸 자료형 => 구현 내용은 명시하지 않고 인터페이스만 제공 특징 추상화를 통해 정의됨 (데이터 모델링) 무엇.. 자료 구조 Orientation Goal자료구조에 대한 이해자료 구조(Data Structure)개념 : 자료를 효과적으로 표현, 저장, 처리하기 위한 기술 또는 그러한 형태사용 이유 : 자료의 특성이나 자료간의 관계 등에 따라 효율적으로 관리하기 위해 적절한 자료구조가 필요자료 구조의 구분자료들은 여러 가지 형태로 분류할 수 있다. - 정수, 실수, 문자 등과 같이 프로그래밍 언어 차원에서 기본적으로 제공되는 원시 타입(Primitive type)- 여러 자료구조가 복합적으로 구성된 복합 자료 구조- etc 주로 다룰 내용은 복합 자료구조이다. 선형 자료구조 / 비선형 자료구조선형 자료구조개념 : 자료들을 구성하는 원소들을 순차적으로 나열 시킨 형태종류 : 배열(리스트), 연결 리스트, 스택, 큐, 데크 등특징 : 한 원소 뒤에 하나.. 코딩 테스트 입문 (with C++) 백준 온라인 저지(BOJ)를 통한 코딩 테스트 이해 하기 BOJ 동작 원리 : https://www.acmicpc.net/blog/view/55 BOJ 채점 결과 : https://www.acmicpc.net/board/view/23037 BOJ 채점 결과 FQA : www.acmicpc.net/board/view/4206 어떤 코딩 테스트 사이트를 이용하는지에 따라 조금씩 차이가 있겠지만, 대부분은 위 내용과 비슷합니다. 코딩 테스트를 위한 C++ 입출력 이해하기 입출력 방식에 따라 성능의 차이가 발생하기 채점 결과가 달라질 수 있습니다. => 코딩 테스트를 위해서 입출력에 대한 이해를 할 필요 저는 C++ 언어를 사용할 것이기 때문에 C++에서 코딩 테스트를 위한 입출력 방식에 대해 말씀 드리겠습니다.. 이전 1 ··· 6 7 8 9 10 다음
