[자료구조/java] 스택의 응용 - 역순 문자열 만들기 * 역순 문자열 만들기 "스택(Stack)의 LIFO(후입선출) 성질을 이용하여 역순 문자열을 생성할 수 있다." 더보기 [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 [ 스택 (Stack) - 1차원 배열, 연결리스트를 이용한 구현] "접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조를 말한다" 따라서 스택은 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out)의 구조를 갖는다. * push 삽입 연산 (1) top = top+1; 으로 삽입 될 위치를 확보 (2) S(top) 가 overflow 가 아니라면 top의 위치에 삽입 * pop 삭제 연산 (1) return S(top); 스택이 공백이 아니라면 top의 위치에 있는 원소 반환 (2) top = top - 1; 제일 위의 원소가 삭제되어 top이 한칸 줄었음을 표시 * 스택을 구현하기 전에 설명할 것이 있다. .. 더보기 [자료구조/java] 다항식의 연결 자료구조 표현 * 다항식의 연결 자료구조 표현 - 단순 연결 리스트를 이용하여 다항식 표현하기 - 계수, 지수, 다음노드를 가리키는 참조 노드 세개로 구성 [다항식의 단순 연결 리스트 표현] 단순 연결 리스트를 이용하여 다항식을 표현 하였다. 단순 연결 리스트는 data, next 두개의 멤버변수로만 구성했지만 다항식을 표현한 단순연결리스트는 계수(coef)와 지수(expo), 다음노드를 가리키는 next 노드로 구성하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ListNode.java package polynomial; public class ListNode { int coef; int expo.. 더보기 [자료구조/java] 이중 연결 리스트 (Doubly Linked List) * 이중 연결 리스트 (Doubly Linked List) - 양쪽 방향으로 순회할 수 있도록 연결한 리스트 원형 연결 리스트에서 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제를 해결 [ 삽입연산 ] (1) 삽입할 노드를 가져온다. (2) 새 노드의 데이터 필드에 값을 저장한다. (3) 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장한다. (4) 그리고 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드를 주소를 저장한다. (5) 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 자장한다. (6) 그리고 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장한다. [ 삭제연산 ] (1).. 더보기 [정렬] 큌정렬 (Quick Sort) * 퀵정렬 (Quick Sort) "전체 원소에 대해서 정렬을 수행하지 않는다" - Divide and Conquer (분할 정복) : 재귀적 구현 필요기준값(pivot) 을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(divide)기준값(pivot) 보다 큰 원소는 배열의 오른쪽, 기준값(pivot) 보다 작은 원소는 배열의 왼쪽으로 이동 - 실행 성능은 선택한 기준값(pivot) 에 의해 결정- 일반적으로 기준값(pivot) 은 전체 원소 중에서 가운데 위치한 원소를 선택 [시간 복잡도] * 최선의 경우, 평균의 경우 : O(nlogn)pivot 에 의해서 원소들이 왼쪽 부분집합과 오른쪽 부분집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복* 최악의 경우 : O(n^2)pivo.. 더보기 이전 1 ··· 5 6 7 8 9 10 11 다음
