면접/자료구조, 알고리즘 (8) 썸네일형 리스트형 자료구조(8/10)- 트리2 자료구조(7/10)- 트리1 자료구조(6/10)- 스택, 큐, 덱 OS내부의 많은 시스템이 스택과 큐를 기반으로 하며, 그래프와 트리 순회도 결국은 스택과 큐로 한다. 깊이 우선 탐색은 스택을 이용하는 순회이고, 너비우선 탐색은 큐를 기반으로 한다. 등등 스택과 큐에 대해서, 효율적인 스택과 큐를 구현하는 법에 대해서 알아보장 1. 스택: 데이터를 차곡차곡 쌓는다 한쪽만 출입구인 ㄷ 자모양에 데이터를 넣고 뺀다. PUSH, POP => LIFO(last in first out: 가장마지막에 들어온애가 가장 먼저 나간다) STACK - Object : LIFO 객체 - Operation: 1) empty() : boolean 비었니? 2) push(data) : void 삽입 3) pop() : element 삭제(반환도 동시에) 4) peek() : element 반환.. 자료구조(5/10)- 연결리스트 배열은 충분히 좋은 자료구조지만, 프로젝트가 커지고 복잡해 질수록 배열로는 한계가 있다. - 한계1. 배열은 길이가 정해져 있어야한다. 무한에 가까운 자료를 저장할 수 없다. - 한계2. 중간에서 삽입/삭제 과정이 일어날때 데이터의 이동 및 복사가 매우 빈번히 일어나게 된다. 이것의 한계를 극복하기 위해 나타난 것이 리스트이다! 리스트는 대표적으로 동적 배열을 이용한 배열 리스트와, 자기참조 구조체의 동적 메모리 연산을 이용한 연결리스트가 존재하지만 이중에서 우리는 우선 연결 리스트를 알아본다! 자료구조(4/10)- 배열 초기 배열은 같은 데이터 타입을 가진 변수의 집합으로 쓰였다. 아직도 많은 언어에서 배열은 같은 타입 변수들을 저장하지만, c언어를 제외한 거의 대부분의 언어가 초기 형태의 배열이 아닌 동적 배열을 지원한다. 기존 배열이 가지는 장점은 유지하면서 단점을 보완한 동적 배열을 알아보자. *)기본적인 배열의 특징: 메모리상에서 물리적, 선형적으로 저장된다 일단 필요한 만큼 할당받아 데이터를 저장하다가, 메모리가 더 많이 필요한 순간에는 더 큰 공간을 확보- 복사+추가하여 데이터 삽입하여 저장되는 배열(힙영역 메모리 처리), 이에 여러가지 유용한 연산을 추가해서 오늘날의 동적 배열이 완성되었다. 자료구조(3/10)- 목차와 실제 사례 [자료구조] 1. 배열 : 변수가 한 곳에 모여있으면 빠르다! 2. 연결리스트: 삽입과 삭제를 빠르게! 3. 스택, 큐, 덱: 스택: 데이터를 차곡차곡 큐: 데이터로 줄 세우기 덱: 스택으로도, 큐로도 사용할 수 있다! 4. 그래프 : 관련있는 데이터 연결하기 그래프의 모든 노드 방문 : 도시를 모두 여행하자 1) 너비 우선탐색: 인근 도시부터 2) 깊이 우선탐색: 한 방향으로 쭉 여행하기 5. 트리: 쓸 데가 많은 자료구조 1) 이진 탐색 트리 2) 레드 블랙 트리 3) B트리 4) 힙과 우선순위 큐 [다양한 그래프 알고리즘] .. 알고리즘 편에서 1. 위상 정렬 2. 최소 비용 신장트리 1) 탐욕 알고리즘 2) 크루스칼 알고리즘 3) 프림 알고리즘 3. 최단경로 1) 데이크스트라 알고리즘 실제 적용된.. 자료구조(2/10) - 빅오 표기법, ADT 빅오 어떤 자료구조가 다른 자료구조에 비해 성능이 좋다고 이야기할수 있는 방법은? 어떤 기준을 설정하고 두 함수를 상대적으로 비교하는것 다시) 자료구조: 데이터를 저장하는 구조 데이터를 저장하는 방식(함수들의 조합)이 자료구조마다 다른데 함수 내에 있는 반복문, 분기문의 실행횟수, 혹은 덧셈이나 곱셈 같은 연산 횟수 등을 세면 실제 물리적인 실행 환경 말고, 추상적으로? 성능을 개략적으로 어떻다고 판단할수 있다. 입력값 n에 대해 이러한 연산횟수는 방정식T(n)으로 표기할수 있는데, 알고리즘 성능을 분석할때는 점근적 표기법을 주로 사용한다. 2n+3이라는 T(n)이 있을때 2n+3 = O(n) => 즉 2n+3의 빅오는 n이다라고 말할 수 있다. (n은 어느시점에서 반드시 2n+3보다 크다) 2n+3 =.. 자료구조(1/10)- 시작 /* 이 시리즈의 글은 '파이썬으로 배우는 자료 구조 핵심원리' 책과 함께 합니다*/ 자료구조 데이터를 원하는 규칙, 혹은 목적에 맞게 저장하기 위한 구조 알고리즘 자료구조에 쌓인 데이터를 활용해 문제를 해결하기위한 여러 동작들의 모임 도서관의 책장이 자료구조라면 특정한 책을 찾는 행위가 알고리즘 어떤 상황에서 어떤 자료구조를 사용해야 좀 더 효율적으로, 성능이 좋은 프로그램을 만들수 있는지 각 자료구조의 연산 성능을 판단하는데 사용되는 알고리즘 성능분석 기법 빅오 자료구조를 구성하는 객체와 연산을 기술하는 방법 추상 자료형 그림이 째끔 촌스럽지만.. 익혀둬야할 자료구조를 도식화하면! 그리고 젤 중요한.. 왜 이걸 공부하냐면... 면접에 나와서.. 도 있지만 최적의 효율을 위해 자료(=data)를 구조화.. 이전 1 다음
