Algorithm (31) 썸네일형 리스트형 트리의 운행 (tree traverse) 트리의 운행 (tree traverse) : 트리 구조의 각 노드를 전부 한번씩 방문하여 검색해내는 방법 레벨 순서 운행 방법 - 상향식 레벨 순서 운행법 - 하향식 레벨 순서 운행법 노드의 위치에 따른 운행법 - 전위 운행법 - 중위 운행법 - 후위 운행법 이진 트리의 운행법 일반적인 트리의 운행보다 간단 나타낼 수 있는 조합의 수는 6가지이지만 왼쪽 서브트리가 오른쪽 서브 트리보다 선행한다는 제약을 주면 3가지 운행법만 존재 전위 운행법 : root - left - right 중위 운행법 : left - root - right 후위 운행법 : left - right - root 이진 트리 운행법 예제 전위 운행법 : A B D G E H C F 중위 운행법 : D G B H E A C F 후위 운행법.. 이진 트리 이진 트리 왼쪽 서브 트리와 오른쪽 서브 트리라고 부르는 2개의 분리된 트리로 구성된 노드들의 유한 집합 이진 트리는 모든 노드들의 차수는 2를 초과할 수 없음 root 노드만 있어도 이진 트리로 인정 왼쪽과 오른쪽의 반향성 존재 트리 (a)와 트리 (b)는 다른 트리 (c)와 같이 서브 트리가 왼쪽/오른쪽이 아닌 아래로 향한 트리는 이진 트리가 아님 Vector Vector ArrayList와 동일한 내부 구조 스레드 동기화(synchronization) 되어 있음 복수의 스레드가 동시에 Vector에 접근해 객체를 추가, 삭제하더라도 스레드에 안전 Vector 예제 Vector를 이용하여 Board 객체 추가, 삭제, 검색 package list; public class Board { String subject; String content; String writer; public Board(String subject, String content, String writer) { super(); this.subject = subject; this.content = content; this.writer = writer; } } package list; import .. List 인터페이스 - ArrayList List 인터페이스 특징 순서가 있는 집합 인덱스로 관리 중복하여 객체 저장 가능 구현 클래스 ArrayList LinkedList Vector 주요 메서드 add() / get() / isEmpty() / size() / remove() / clear() ArrayList List 인터페이스의 구현 클래스 크기가 가변적으로 변하는 선형리스트 배열과 유사 (순차리스트, 인덱스 사용) ArrayList와 배열의 차이점 배열은 크기가 고정되어 있음 ArrayList는 객체 추가 가능 존재 -> 크기가 가변적으로 변함 (저장 용량 초과 시 자동으로 저장 용량 증가) ArrayList의 단점 데이터를 읽어오고 저장하는데 효율적 용량을 변경해야 할 때는 새로운 배열을 생성 후 기존 배열로부터 새로운 배열로 복사 .. 순차 리스트 ( 배열 / 행렬 / 레코드 / 스택 / 큐 / 데크 ) 자료 구조의 종류 순차 리스트 : 각 자료가 메모리 중에서 서로 이웃해 있는 구조 : 선형 구조라고도 함 : 메모리에 연속되어 저장 : 배열 / 행렬 / 레코드 / 스택 / 큐 / 데크 배열 : 원소들의 크기와 자료형 같음 : 배열의 원소는 메모리 내에서 연속적으로 순서대로 저장 : 각 배열의 원소는 인덱스로 구별 레코드 : 서로 다른 데이터 형태와 크기로 구성되어 있는 데이터 구조 (이질적 구조) : ex) 어떤 사람에 관한 자료들인 이름, 주민등록번호, 주소 등과 같이 서로 관계있는 여러 필드를 하나로 묶어서 구성 : 배열은 데이터 원소의 크기와 데이터 형태 동일하지만, 레코드는 데이터 원소의 크기와 데이터 형태 서로 다름 스택 (stack) : 쌓아 올린 더미를 의미 : 선형 리스트 구조의 특별한 .. 분할 정복 기법 VS 동적 프로그래밍 기법 분할 정복 기법과 동적 프로그래밍 기법의 차이점 분할 정복 기법 동적 프로그래밍 기법 공통점 문제를 잘게 쪼개어 가장 작은 단위로 분할 차이점 하향식 설계 기법 부분 문제는 중복되지 않음 Memorization 기법 활용하지 않음 상향식 설계 기법 부분 문제는 중복되어, 상위 문제 해결 시 재활용 됨 부분 문제의 해답을 저장해서 재활용 (Memorization 기법 활용) 동적 프로그래밍 기법 (dynamic programming) 동적 프로그래밍 기법 (dynamic programming) : 분할 정복 기법과 유사 : 주어진 문제를 여러 개의 작은 문제로 분할하여 문제를 해결 : 상향식 설계 기법 (작은 문제부터 먼저 해결 -> 그 결과를 큰 문제에서 활용 -> 효율성 증가) 동적 프로그래밍 방식 적용 방법 : 분할 정복식 방법과 마찬가지로 문제를 여러 개의 작은 문제로 분할 : 주어진 부분 문제들을 한 번 계산한 후에는 특정 장소에 저장 (일반적으로 배열 사용) : 해당 부분 문제의 해가 필요할 때, 이를 다시 계산하지 않고 이전에 저장해 둔 결과 이용 동적 프로그래밍 적용 대상 : 최소치 또는 최대치를 구하는 최적화 문제에 적용 : 최적해는 기본적인 소문제의 최적해로부터 더 큰 크기의 소문제의 최적해를 구하는 과정 거침 : .. 욕심쟁이 기법 (Greedy method) 욕심쟁이 기법 (Greedy method) : 선택을 하는 매 순간마다 현재 상태에서 가장 좋아 보이는 원소를 선택하는 전략 : 최적의 해를 찾는 전형적인 해결 방법 : 각 순간에 지역적으로 가장 좋아 보이는 선택들이 모여 전체적으로도 가장 좋은 최종의 답에 이르는 경우 많음 : 모든 최적화 문제를 해결할 수는 없지만, 많은 경우의 문제에 쉽게 적용할 수 있는 기법 중 하나 욕심쟁이 기법 적용 예시 : 배낭 채우기 문제 : 거스름돈 문제 // 거스름돈 문제 import java.util.Scanner; public class exGreedyCoinArray { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Sys.. 계수 정렬 (Counting Sort) 계수 정렬 (Counting Sort) : 각각의 데이터가 몇 번씩 등장했는지를 세는 방식으로 동작하는 정렬 알고리즘 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능한 정렬 알고리즘 : 요소 값들끼리 서로 비교하지 않고 정렬 수행 : 특정 조건 부합 시에만 사용 가능하지만, 특정 조건 만족 시 퀵 정렬보다도 빠르게 동작함 : '배열 내 최대값 + 1' 길이의 배열 필요 -> 메모리 낭비 가능성 존재 ( = 상대적으로 공간 복잡도 높다) : 동일 값 가지는 데이터 여러 개 등장할 때 효과적 계수 정렬 동작 과정 1. 카운팅 배열 생성 : 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 배열 : 배열 내의 원소 값들의 개수를 저장하는 배열 2. 순회하며 각.. 이전 1 2 3 4 다음