창문을 열심히 닦아요

이전에 정리한 내용이 있지만, 책을 보며 예제 풀이를 진행하는 것이라 한 번 더 포스팅한다. [4장. 스택과 큐] 1. 스택 스택이란? 스택은 데이터를 일시적으로 저장하기 위한 자료구조이다. 후입 선출 방식(LIFO)으로 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. push : 스택에 데이터를 넣는 작업 pop : 스택에서 데이터를 꺼내는 작업 top : push와 pop을 하는 위치 bottom : 스택의 가장 아랫부분 스택 만들기 생성자 IntStack : 생성자는 스택 본체용 배열을 생성하는 등 준비작업을 수행한다. 생성시 스택은 비어있으므로 스택 포인터는 0을 가리킨다. 푸시 메소드 push : 스택에 데이터를 넣는 메소드이다. 스택이 가득차서 푸시할 수 없을 경우는 예외처리를 해준다. 포인터값..

[3장. 검색] 1. 검색 알고리즘 검색과 키 검색 : 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 것이다. 키 : 주목하는 항목. 키는 데이터의 일부에 해당한다. 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용하여 복합해서 지정하기도 한다. 배열에서 검색하기 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법이다. 오픈주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다. 데이터의 검색, 추가, 삭제에 소요되는 비용을 종합적으로 계산해..

자료구조와 함께 배우는 알고리즘 입문을 통해 자료구조 기초를 쌓아보자! [1장. 기본 알고리즘] 1. 알고리즘이란? - 값과 최댓값 순차적 구조 : 여러 문장(프로세스)이 순차적으로 실행되는 구조 선택 구조 : 식의 평가결과에 따라 프로그램의 실행 흐름을 변경하는 if문 개발할 때 순서도(플로우 차트)를 그리는 습관을 가지는 것이 좋다! 개발 구상이 복잡하거나, 팀원들과 전체 서비스 흐름을 공유하고 검토받는 데 유용하다. 알고리즘 : 문제를 해결하기 위한 것으로 명확하게 정의되고 순서가 있는 유한개의 규칙으로 이루어진 집합 - 조건 판단과 분기 연산자 : +,- 등의 연산기호 단항 연산자 : 피연산자 1개 a++ 2항 연산자 : 피연산자 2개 a < b 3항 연산자 : 피연산자 3개 a ? b : c 피..

Map 맵은 hash라고도 불린다. 배열이나 딕셔너리와 관련 있는 key-value 형태의 저장소이다. 키 값은 트리상에서 한 번만 나타난다(중복되지 않는다). 만약, 동일 키로 다시 데이터를 입력할 경우 원본 키에 있던 값은 덮어씌워진다. Map의 종류 HashMap : Map 인터페이스를 구현하기 위해 HashTable을 사용한 클래스. 중복을 허용하지 않고 순서를 보장하지 않음. key와 value로 null이 허용 HashTable : HashMap보다 느리지만 동기화를 지원한다. key와 value로 null이 허용되지 않는다. TreeMap : 이진 검색 트리의 형태로 key-value 쌍으로 이루어진 데이터를 저장한다. 정렬된 순서로 키, 값 쌍을 저장하므로 빠른 검색이 가능하다. 저장 시 ..

1. Stack - 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다. - LIFO : Last In First Out 방식으로 자료를 처리한다 . - 사용용도 서브 프로그램 호출 시 복귀 주소를 저장할 때 함수 호출의 순서 제어 인터럽트가 발생하여 복귀 주소를 저장할 때 후위 표기법으로 표현된 산술식 연산 0 주소 지정방식 명령어의 자료 저장소 재귀프로그램의 순서 제어 컴파일러를 이용한 언어 번역 Top : Stack으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소. 스택 포인터 Bottom : 스택의 가장 밑바닥 Push : 스택에 자료 입력 Pop : 스택에서 자료 출력 package com; import java.util.EmptyStackE..

1. List 순서가 있는 데이터의 집합, 데이터 중복 허용한다. 배열과는 다르게 크기 지정에 한계가 없으므로 크기를 지정할 필요가 없다. 2. Array List 배열로 이루어진 리스트이다. 기존의 Vector class를 개선한 것이다. 논리적인 저장순서와 물리적인 저장순서가 동일하다. 데이터 삽입시 만약 첫번째 자리에 새로운 데이터를 추가할 경우(worst case) 모든 원소들을 1씩 shift 해야 한다. 이 경우 시간복잡도는 O(n)에 해당한다. 3. Linked List 연결리스트: 자료들을 임의의 기억공간에 기억하며. 일렬로 연결된 자료를 저장할때 사용한다. 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다. (= 논리적 저장 순서와 물리적 저장 순서가 일치..