본문 바로가기

프로그래밍 언어40

자료구조 - 해싱 해싱(Hashing) 해싱이란? 해시 함수와 해시 테이블을 이용하여 데이터를 빠르게 저장하고 탐색하는 방법 데이터를 해시 테이블이라는 배열에 저장하고 데이터의 키 값으로 해시 함수를 통하여 테이블의 주소를 반환하여 원하는 데이터를 찾는 방식 해시 테이블 값의 연산에 의해 직접 접근 가능한 구조 해시 함수 해시 테이블에서 기 값을 주소로 변환하는데 사용되는 함수 계산이 빠르고 간단해야 하며, 다른 키 값이 같은 주소를 산출하는 경우가 적어야 함 해시 함수 종류 나눗셈법 중간 제곱법 폴딩법 기수 변환법 자리수 분석법 나눗셈법 키 값을 정수로 보고 이를 적당한 양의 정수(주소, 해시 테이블의 크기 등)로 나누어 그 나머지를 해시 주소로 하는 방법 h(k) = k mod N h(): 해시 함수 k: 키 값 N:.. 2021. 12. 1.
자료구조 - 탐색 탐색(Search) 탐색이란? 데이터의 집단 내에서 특정 데이터를 찾아내는 구조 탐색 알고리즘의 효율성은 탐색 집단의 구조가 어떻게 구성되어 있느냐에 따라 영향을 받음 컴퓨터가 가장 많이 하는 작업 중의 하나 탐색에서 사용되는 자료 구조 배열, 연결 리스트, 트리, 그래프 등 탐색 방법 순차 탐색 이진 탐색 보간 탐색 이진트리 탐색 순차 탐색 (Sequential Search) 정렬되지 않은 데이터의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾는 방법 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 크기가 적은 리스트에서는 효유류적이지만 크기가 큰 리스트에서는 매우 비효율적 장점 하나씩 비교하기 때문에 탐색에 용이 탐색 알고리즘이 간단함 단점 탐색 시간이 느리며 수행 시간 오래 걸림.. 2021. 12. 1.
자료구조 - 정렬 정렬(Sort) 정렬이란? 일련의 자료들을 자료 중에 포함된 몇 가지 항목을 우선 순서대로 지정하여 그 순서에 따라 모든 자료를 배열(나열)하는 방법 컴퓨터 공학분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 자료 탐색에 있어서 필수적 정렬 알고리즘의 종류 버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 쉘 정렬 (Shell Sort) 퀵 정렬 (Quick Sort) 2원 합병 정렬 (Two-way merge Sort) 기수 정렬 (Radix Sort) 힙 정렬 (Heap Sort) 정렬 알고리즘 단순하지만 비효율적인 방법: 삽입 정렬, 선택 정렬, 버블 정렬 복잡하지만 효율적인 정렬: 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬.. 2021. 12. 1.
자료구조 - 트리 컬렉션 프레임워크(Collection Framework) 트리 자료의 항목(node)들이 가지(edge)로 연결될 수 있게 자료가 구성되어 있는 구조 계층적 구조 부모-자식 관계의 노드로 구성 트리의 용어 노드(node): 트리를 구성하는 각 자료 항목: A, B, C, D, E, F, ... 근 노드(root node) 트리 구조를 시작하는 노드 제일 상위 계층에 존재하는 하나의 노드 A 자식 노드 임의의 노드에 연결된 다음 레벨의 노드들의 집합 D의 자식 노드는 H, I, J 부모 노드 임의의 노드에 연결된 상위 계층의 노드 A는 B, C, D의 부모 차수(degree) 노드에 연결된 자식 노드의 수 A의 차수: 3, B의 차수: 2, C의 차수: 1 레벨 root node 레벨을 0으로 하고 그 아.. 2021. 11. 30.
컬렉션 프레임워크(6) Map 인터페이스 컬렉션 프레임워크(Collection Framework) Map 컬렉션 Map 인터페이스 키(Key)와 값(Value)의 쌍으로 이루어진 데이터의 집합 키와 값은 모두 객체 키는 중복될 수 없지만 값은 중복 저장 가능 기존에 저장된 데이터와 중복된 키 값을 저장하면, 기존의 값은 없어지고 마지막에 저장된 값이 남음(덮어씀) 구현 클래스: HashMap, Hashtable, LinkedHashMap, Porperties, TreeMap 일반적으로 키 타입은 String을 주로 사용 HashMap을 생성하기 위해서는 key 타입과 value 타입 매개변수로 주고 기본 생성자 호출 기본 형식 Map map = new HashMap(); HashMap 예제 HashMapEx.java package map; im.. 2021. 11. 30.
컬렉션 프레임워크(5) Set 인터페이스 - HashSet 컬렉션 프레임워크(Collection Framework) Set 컬렉션 Set 인터페이스 수학의 집합에 비유 저장 순서가 유지되지 않음 객체 중복 저장 불가 구현 클래스: HashSet, LinkedHashSet, TreeSet 전체 클래스를 대상으로 한 번씩 반복해 가져오는 반복자(Iterator) 제공 인덱스로 객체를 검색해서 가져오는 메소드 없음 get() 메소드 없음 HashSet 예제 HashSetEx.java package set; import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class HashSetEx { public static void main(String[] args) { Set set.. 2021. 11. 30.
컬렉션 프레임워크(4) List 인터페이스- Vector 컬렉션 프레임워크(Collection Framework) Vector(벡터) ArrayList와 동일한 내부 구조 스레드 동기화(synchronization) 되어 있기 때문에 복수의 스레드가 동시에 Vector에 접근해 객체를 추가, 삭제하더라도 스레드에 안전 Vector 예제 Vector를 이용해서 Board 객체 추가, 삭제, 검색 Board.java package list; public class Board { String subject; String content; String writer; public Board(String subject, String content, String writer) { this.subject = subject; this.content = content; this... 2021. 11. 30.
컬렉션 프레임워크(3) List 인터페이스 - LinkedList 컬렉션 프레임워크(Collection Framework) LinkedList List 구현 클래스이므로 ArrayList와 사용 방법은 동일 내부 구조가 다르다 ArrayList: 배열로 만들어져 있어서 인덱스 사용 LinkedList: 인접 참조를 링크해서 체인처럼 관리 (이전/다음 객체의 주소 갖고 있음) 특정 인덱스에서 객체를 제거하거나 추가하게 되면 바로 앞뒤 링크만 변경 빈번한 객체 삭제와 삽입이 일어나는 곳에는 ArrayList보다 성능 좋음 순차적으로 추가/삭제 할 경우 ArrayList가 LInkedList보다 빠름 ArrayList가 용량이 충분하면 더 빠르지만 충분하지 않으면 새로운 크기의 ArrrayList를 생성하고 데이터를 복사하는 일이 발생하기 때문에 순차적으로 데이터를 추가해도.. 2021. 11. 30.
컬렉션 프레임워크(2) List 인터페이스- ArrayList 연습문제 ArrayList 연습문제 -1 4개의 단어를 입력받고 가장 긴 단어와 단어의 길이를 출력하는 프로그램 작성 ArrayListTest1.java package list; import java.util.ArrayList; import java.util.Scanner; public class ArrayListTest1 { public static void main(String[] args) { ArrayList a = new ArrayList(); Scanner scanner = new Scanner(System.in); for (int i = 0; i < 4; i++) { System.out.print("단어 입력: : "); String s = scanner.next(); a.add(s); } Syste.. 2021. 11. 30.

티스토리툴바