bootcamp/Java (24) 썸네일형 리스트형 1204 스택 스택 -인터넷 브라우저가 간 순서를 저장하는 것 -데이처를 차곡차곡 저장해두고 있다가 가장 먼저 들어간 데이터가 마지막으로 삭제 됨 -last in-first out/fist in-last out -> 후입선출 방식 ->변수 스택의 연산 1) push - 데이터를 저장하는 연산 2) pop - 데이터를 삭제하는 연산 3) stop - 제일 마지막에 저장된 값 확인 4) isEmpty - 스택에 값이 모두 비어있는지 학인 5) isFull - 스택에 값이 모두 저장되어있는지 학인 -> 메소드 1212 그리디 그리디 탐욕 알고리즘 현재 상태에서 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 동작 방식 현재 상태에서 가장 최선이라고 생각되는 해를 선택 현재 선택한 해가 전체 문제의 제약 조건에 안벗어나는지 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사 전체 문제를 해결하지 못하면 1로 돌아가 같은 과정을 반복 1212 깊이우선탐색(DFS)/너비우선탐색(BFS) 그래프 노드와 간선으로 이루어진 자료 구조 깊이우선탐색(DFS) 그래프 완전 탐색 기법 중 하나 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 스택을 사용 동작 방식 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 X - 스택에서 최상단 노드를 꺼냄 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 깊이 우선 탐색의 구현 스택에 시작 노드를 넣는다 스택이 비어 있지 않으면 계속 반복 스택에서 노드을 하나 pop해서 가져온다 가져온 노드가 방문한 적 없으면 방문한 노드 출력 방문 처리 .. 1211 동적프로그래밍 동적 프로그래밍 복잡한 문제를 여러 개의 간단한 문제로 분리 부분의 문제들을 해결, 최종적으로 복잡한 문제의 답을 구함 동적 프로그래밍 구현 큰 문제를 작은 문제로 나눌 수 있어야 한다. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모이제이션memoization 기법이라고 한다. 동적 계획법은 톱-다운 방식top-down과 바텀-업bottom-up 방식으로 구현할 수 있다. 1208 정렬 선택 첫칸부터 데이터들 중에 제일 작은 데이터를 찾아서 채우는 방식으로 정렬하는 알고리즘 0회전 59 34 80 27 61 90 55 37 25 43 1회전 25 34 80 27 61 90 55 37 59 43 2회전 25 27 80 34 61 90 55 37 59 43 3회전 25 27 34 80 61 90 55 37 59 43 4회전 25 27 34 37 61 90 55 80 59 43 5회전 25 27 34 37 43 90 55 80 59 61 6회전 25 27 34 37 43 55 90 80 59 61 7회전 25 27 34 37 43 55 59 80 90 61 8회전 25 27 34 37 43 55 59 61 90 80 9회전 25 27 34 37 43 55 59 61 80 90 거품 서로 인접.. 1206 AVL Tree 1. AVL 트리란? 균형 트리 중 하나 AVL 특징 BF 밸런스 팩터 Balance Factor 특정 노드의 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이의 절대값 BF가 2이상이 되지 않는 트리 구현(삽입) 우회전 부모 노드의 오른쪽 자식을 조부모 노드로 변경 조부모 노드의 왼쪽 자식을 원래 부모의 오른쪽 자식으로 변경 좌회전 부모 노드의 왼쪽 자식을 조부모 노드로 변경 조부모 노드의 오른쪽 자식을 원래 부모의 왼쪽 자식으로 변경 LL 우회전 LR 부모을 기준으로 좌회전 후 다시 우회전 RR 좌회전 RL 부모를 기준으로 우회전 후 다시 좌회전 1206 Red Black Tree 1. 레드 블랙 트리란? 균형 트리 중 하나 특징 모든 노드는 빨간색 혹은 검은색 루트 노드는 검은색 모든 노드는 우선 NIL 노드를 자식으로 가지고 있다. 빨간색 노드의 자식은 검은색 (연속된 빨간색 노드가 올 수 없다.) 모든 NIL노드에서 루트까지의 검은색 노드의 수는 같다. 새로운 노드 추가할 때 새로운 노드는 우선 빨간색 NIL 노드 데이터를 저장하지 않은 노드 모든 NIL 노드들은 검은색 구현( 삽입) 맨 처음 노드 삽입 ㅡ> 새로운 노드 생성 후 검은색으로 변경 두번째부터 빨-빨이 오면 변형 삼촌 노드가 검정색 Restructuring 새로운 노드, 부모 노드, 조무보 노드를 오름차순으로 정렬 셋 중 중간 값을 부모로 만들고 나머지를 자식으로 만든다. 새로 부모가 된 노드를 검은색으로 만들고.. 1206 B-Tree 1. B트리란? 균형 트리 중 하나, BST에서 데이터가 한쪽으로 치우치는 것을 방지(치우치면 검색 성능이 안좋아짐) 2. B트리의 특징 M 입력받은 차수, 노드의 최대 자식 노드 수 M - 1 각 노드에 저장될 수 있는 최대 데이터의 수 M/2 올림 각 노드의 최소 자식 노드 수(루트 노드, 리프 노드 제외) M/2 - 1올림 각 노드의 최소 데이터의 수(루트 노드) 3. 구현(3차 B트리) 삽입 추가할 때는 항상 리프 노드에 데이터를 추가 노드에 저장할 수 있는 최대 데이터 수를 넘으면 가운데 데이터를 기준으로 좌우 노드로 나눠주고 가운데 노드를 부모로 만들어준다. 노드 안에 데이터들은 오름차순으로 정렬해서 저장 1. B트리란? 균형 트리 중 하나, BST에서 데이터가 한쪽으로 치우치는 것을 방지(치.. 1206 트리 트리란? 계층을 가지도록 데이터를 나열한 것 트리에서는 각각의 요소를 노드라고 한다. 노드는 데이터와 자식 노드들로 이루어져 있다. 트리의 용어 트리의 루트 노드 가장 윗부분에 있는 노드 트리의 리프 노드 사장 밑부분에 있는 노드 특정 노드의 부모 특정 노드의 상위 노드 특정 노드의 자식 특정 노드의 하위 노드 특정 노드의 형제 부모가 같은 노드 특정 노드의 조상 부모의 부모의 부모의 부모의 ....... 까지 특정 노드의 자손 자식의 자식의 자식의 자식의 ....... 까지 특정 노드의 레벨 루트로부터 얼마나 떨어져 있는가 특정 노드의 차수 자식 노드의 수 트리의 높이 루트에서 제일 먼 리프까지의 거리 이진트리 최대 차수가 2인 트리 삼진트리 최대 차수가 3인 트리 사진트리 최대 차수가 4인 트리 이진.. 1205 리스트 리스트란? 순서를 가지도록 데이터를 나열한 것 리스트에서는 각각의 요소를 노드라고 한다. 노드는 데이터와 다음 노드로 이루어져 있다. 리스트의 구현 리스트 클래스부터 만든다. 노드 클래스 데이터와 노드를 저장할 수 있는 클래스 리스트 클래스 head 맨 처음 노드 생성자 head에 null 저장 display insertFirst 맨 처음에 데이터를 추가하는 기능 insertLast 마지막에 데이터를 추가하는 기능 insertIndex 원하는 순서에 데이터를 추가하는 기능 removeFirst 맨 처음 노드를 삭제하는 기능 removeLast 맨 마지막 노드를 삭제하는 기능 removeIndex 원하는 순서의 노드를 삭제하는 기능 (2) insertFirst 데이터 하나를 전달 받는다. 노드 객체 생성 .. 이전 1 2 3 다음
