Major/Data Structure & Algorithm (14) 썸네일형 리스트형 [Algorithm] DP public class seq_Matrix { /* * 연쇄행렬 최소곱셈 알고리즘 * 두개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구함 * 복잡도 : O(n^3) * DP table의 칸의 개수 n*n = n^2 . * 한개의 칸을 채울 때 필요한 연산의 개수는? * 최악의 경우 DP[1][6]인 경우에 가장 많은 연산을 요구. * 한칸을 채울 때 최악의 경우 n번의 연산을 해야하므로 * O(n^3)의 시간복잡도 가진다. */ public static int minmult(int n, int d[], int P[][]){ int M[][] = new int[n+1][n+1]; for(int i = 0; i < n; i++) M[i][i] = 0; for(int diag = 0; diag < n; di.. DFS(Depth First Search) - 인접 행렬을 이용한 DFS 구현 a[x][i] 값이 1인지(=연결된 간선이 있는지) 확인하면서 방문한 적이 없는 정점을 방문 해야함. void dfs(int x) { check[x] = true; for(int i = 1; i 인접 리스트에 이미 연결된 간선만 저장되어 있기 때문이다. void dfs_list(int x) { check[x] = true; for(int i = 0; i < a[x].length(); i++) { int y = [x][i]; if (check[y] == false) { dfs(y); } } } 배열 visited를 F로 초기화하고 공백 스택을 생성한다. 방문한 정점은 T로. (=visited) 정점 A에 아직 방문하지 않은 정점 B,C가 있으므로 스택에 A 집어넣고 오름.. Binary Tree [자료구조] 트리 (Tree) (velog.io) [자료구조] 트리 (Tree) 사진의 출처 : 링크트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른 velog.io *이진 탐색 트리 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조. 1. 모든 원소는 서로 다른 유일한 키를 갖는다. 2. 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다. 3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다. 기본적으로 루트에서 탐색을 시작한다. 탐색할 키 값 x를 루트 노드의 키 값과 비교한다. - 3개.. 후위식 연산 후위연산식은 컴퓨터가 계산하기에 훨씬 편한 연산식 형태이다. 피연산자를 스택에 push하고 연산자를 만나면 스택에서 두개의 피연산자를 꺼내서 계산하고 다시 스택에 push한다. 스택이 공백이 될 때까지 진행하고 결과를 출력한다. package stack_self; class StackNode { int data; StackNode link; } class LinkedStack02 implements Stack02{ private StackNode top; public boolean isEmpty() { return (top == null); } public void push (int item) { StackNode newNode = new StackNode(); newNode.data = item; ne.. Stack , 괄호검사(Valid Braces), Infix to Postfix algorithm 먼저 들어간 것이 나중에 나온다 - 후입선출(LIFO) ADT - pust, pop, pick void StackInt(Stack *pstack); - 스택 초기화 진행 - 스택 생성 후에 가장 먼저 호출되어야 하는 함수임. int isEmpty(Stack * pstack); - 스택이 비어있는 유무에 따라서 bool값(0or1) 리턴 void push(Stack * pstack, Data data) - 스택에 데이터 저장. Data pop(Stack * pstack); - 마지막에 저장된 요소 삭제, 삭제된 데이터는 반환- 이 함수의 호출을 위해서는 데이터가 하나 이상 꼭 존재해야함 Data Peek(Stack *pstack); - 마지막에 저장된 요소를 반환하나 삭제는 안함- 얘도 마찬가지로 데이터가.. review 원하는 형태의 이중 연결리스트 만들기. 일단 틀부터 짜자. class DoubleNode{ DoubleNode llink; DoubleNode rlink; private String data; public DoubleNode() { this.data = null; this.llink = null; this.rlink = null; } public DoubleNode(String data) { this.data = data; this.llink = null; this.rlink = null; } public String getData() { return this.data; } public void setData(String data) { this.data = data; } public DoubleNode .. 원형 연결 리스트 원형 연결 리스트 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 해서 리스트의 구조를 원형으로 만든 리스트 1. 첫번째 노드의 주소를 temp에 저장해서 순회 시작점을 지정한다. (temp는 순회용 포인터임.) 2. while문 돌려서 temp를 마지막 노드까지 이동시킨다. 3. 노드 new가 temp의 다음 노드, 즉 삽입하기 전 리스트의 첫번째 노드를 가리키게 함. 원형 연결 리스트이기 때문에 마지막 노드의 다음 노드가 첫번째 노드가 된다. 4. 포인터 new의 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장하여 마지막 노드가 노드 new를 가리키게 한다. 5. 노드 new의 주소를 리스트 포인터에 저장한다. 이 과정으로 노드 new가 리스트의 첫번째 노드로 지.. 이중 연결 리스트의 삽입, 삭제 + (다항식 연산 ) 다항식의 연결 자료구조 표현 * 공백 다항식에서의 항 삽입 복잡하게 생각할 필요 없이 새롭게 삽입할 노드 new의 포인터 값을 리스트 포인터에 저장한다. 이와 같은 과정으로 new가 list의 첫번째가 되고, null값을 가진 last에 포인터 new의 값을 저장하면 마지막 노드가 new를 가리키게 된다. 끝! * 다항식에서의 항 삽입 포인터 new의 값을 노드 last의 링크에 저장한다. 노드 new를 노드 last의 다음 노드로 연결함 포인터 new의 값을 포인터 last에 저장하고 노드 new를 마지막 노드로 지정하면 됨. *다항식 연산도 가능 addPoly() 메소드 구현 시 차수 비교를 기준으로 케이스 나누기. 순회용 참조변수인 p와 q를 다음으로 이동시키면서 결과 다항식 C에 appendTer.. 이전 1 2 다음
