본문 바로가기
03-3 스택의 구현(연결 자료구조 방식) ※ 순차 자료구조를 이용해 구현한 스택과 차이점 배열을 사용하여 구현하기는 쉽지만 물리적 크기가 고정되어 있는 배열을 사용하기 때문에 스택의 크기를 변경하기 어렵고 물리적인 공간 낭비가 생길 수 있다. 이러한 문제를 연결 자료구조를 이용함으로써 해결할 수 있다. ※ 연결 자료구조를 통한 구현 스택 초기 상태(공백 스택)는 참조변수 top을 null로 설정. 스택이 push되면 새로 push된 노드는 이전 노드를 가르키고 top은 새로 들어온 노드를 가르킨다. ※ 연결 자료구조를 통한 구현 소스 Interface Stack interface Stack{ boolean isEmpty(); //스택이 공백스택인지 확인하는 함수 void push(char item); //문자를 push하는 함수 char pop.. 더보기
03-2 스택의 구현(순차 자료구조) ※ 스택의 구현 순차 자료구조를 이용한 방식 연결 자료구조를 이용한 방식 ※ 순차 자료구조를 통한 구현 차원 배열 stack[n]을 사용할 때 n이 스택의 크기가 되며 top이 n보다 클 수 없다. 스택에 원소가 쌓이는 순서를 배열의 인덱스로 표현한다. 가장큰 인덱스가 top이된다. top은 0부터 n-1의 인덱스를 저장하므로, 스텍이 초기상태(공백스택, 스택에 값이 없을 때) top에는 -1을 저장한다. ※ 순차 자료구조를 통한 구현 소스 interface Stack interface Stack{ boolean isEmpty(); //스택이 공백스택인지 확인하는 함수 void push(char item); //문자를 push하는 함수 char pop(); //pop 하는 함수(top에 있는 원소를 삭제.. 더보기
03-1 스택 ※ 스택이란? 스택이란 자료구조는 top을 통해 자료가 순차적으로 쌓인다. 또한 top을 통해 순차적으로 출력된다. 그래서 가장 오래된 자료가 가장아래 쌓이고 가장 최신 자료가 제일 위에 쌓인다. 시간에 따라 자료가 쌓이고 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out) 구조를 갖는다. top을 통한 삽입연산을 push라 하며 top을통한 삭제연산을 pop이라 한다. 더보기
02-4 이중 연결 리스트 ※ 이중 연결 리스트 단순 연결 리스트는 선행 노드에 접근하기가 어렵다. 그래서 이를 개선하기 위해 원형 연결 리스트를 구성했다. 하지만 원형 연결 리스트에서도 현재 노드의 선행 노드에 접근하기 위해서는 전체 리스트를 한바퀴 순회해야 하는 문제가 생긴다. 이러한 문제점들을 보완하기 위해 이중 연결 리스트(Doubly Linked List)가 있다. 앞에서 배운 연결 리스트들은 link가 하나였고 다음 노드값들을 저장해 두었다. 하지만 이중연결 리스트는 노드에 link부분을 앞뒤로 두어 선행노드와 후행노드를 각각 연결해둔다. 그래서 선행노드의 접근이 다른 연결 리스트에 비해 쉽다. ※ 구현(아래 이중 연결 리스트로 구현한다) 메인 public class Main { public static void mai.. 더보기
02-3 원형 연결 리스트 ※ 원형 연결 리스트(Circular Linked List)란? 연결 리스트의 구조를 원형으로 만든것 -> 마지막 노드의 링크를 첫번째 노드에 걸어준다. 단순 연결 리스트는 이전 노드에 접근하려면 노드를 다시 처음부터 순회해야 되지만 원형 연결 리스트는 계속 순회하면 이전 노드에 접근할 수 있다. 1.원형 연결 리스트의 삽입연산 운형 연결 리스트에서의 삽입연산은 마지막 노드부분을 처음 노드와 연결하는 부분 빼고 단순 연결 리스트와 똑같다. 또한 원형 연결 리스트의 마지막 노드를 삽입하는 것이 곧 리스트의 첫 번째 노드를 삽입하는 것과 같은 의미이다. 그래서 원형 연결 리스트에서의 삽입연산은 첫 번째 노드 삽입과 중간 노드 삽입의 경우로 나눌 수 있다. ※ 구현 메인 public class Main { p.. 더보기
02-2 단순 연결 리스트 ※ 전장에서 공부했든 연결리스트에 대한 기본 구조는 알고 있을 것이다. 노드를 만들 때 C에서는 link 부분을 포인터를 이용했지만 자바에서는 포인터대신 객체를 이용한다. ex) Node.link.link.link.link 의 방식으로 연결 리스트의 노드를 탐색한다고 생각하자. ※ 자바에서의 포인터개념?? 자바에서 포인터 개념을 알기 위해선 메모리 구조에 대해 알아야 한다. 정적 메모리 스텍(Stack) 영역 스택 영역은 변수값을 저장하게 되는데 기본타입인 정수형(int/short/char/byte)변수와 실수형(float/double)변수와 논리형(boolean)변수를 실제값으로 저장한다 크기가 정해져 있는 타입이다. 메모리 할당시 컴파일할때 이미 계산이 이루어진다. 메소드 작업이 종료되면 할당되어던 .. 더보기
02-1 연결 자료구조 방식 ※ 연결 자료구조 방식 순차 자료구조 방식에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방식 순차 자료구조 방식에서의 문제점이란? 1. 순차 자료구조에서 배열이 갖고 있는 메모리 사용의 비효율성 문제 2. 삽입,삭제 연산 시 발생하는 원소들의 이동 작업으로인한 오버헤드 증가로 인한 성능문제 연결 자료구조 방식에서는 순차 자료구조 방식에서처럼 물리적순서와 논리적 순서가 같을 필요가 없다. 각 원소(노드)에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해서 연결되는 방식 여러개의 작은 공간을 연결하여 전체를 표현하므로 크기 변경이 유연하고 좀더 효율적인 메모리 사용 가능 물리적 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 연결 자료구조(Linked Data Structur.. 더보기
01-3 행열의 순차 자료구조 표현 ※행렬이란? 행과 열로 구성된 자료구조 ※ 전치행렬 이란? 어떤 행렬에서 행과 열을 서로 교환하여 구성한 행렬 ex) ※ 희소행렬 이란? 행렬의 원소 대부분이 0인 행렬 이 행렬을 구현할때 0인 원소를 그대로 넣어서 구현하면 메모리 낭비가 심해진다.(대부분이 0이기 때문에) 그래서 이 행렬은 값이 있는 원소들의 을 추출하여 2차원 배열을 만들어 저장하는것이 메모리 관리에 유리하다. 또한 희소 행렬에 대한 전반적인 정보를 정보를 저장히기 위해서 2차원 행렬의 맨위에는 를 저장한다 그러면 아래와 같은 그림으로 희소행렬을 표현 할 수 있게된다. ★ 무엇인가를 만들 때 메모리 낭비를 줄일 수 있는 방법은 무엇인지 곰곰히 생각해 볼 필요가 있는것 같다. 희소행렬같은 경우에도 제일 아래의 그림처럼 2차원 행렬로 데.. 더보기
01-2 다항식의 순차 자료구조 표현 다항식이란? ex) P(x) = ax^n + bx^n-1 + cx^n-2 ..... zx^0 다항식을 선형리스트로 표현하려면 아래와 같은 형식으로 할 수 있다.쌍을 2차원 배열에 저장한다. ex) P(x) = 3x^10 + 2x^3 - 6x + 7 [0] [1] 10 3 3 2 1 -6 0 7 더보기
01-1. (순차)선형리스트의 기본과 구현 ※ 데이터를 구조화 시키는 가장 기본적인 방법은 나열하는 것이다. 이렇게 나열한 목록을 리스트라 한다. 자료구조에서는 데이터를 구조화시키는 기본 표현 방식으로 순차 자료구조 방식과 연결 자료구조 방식이 있다. 선형 리스트란?? 리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트를 선형리스트(Linear List) 또는 순서 리스트(Ordered List)라고 한다. (내가 코딩하면서 쓰는 기본적인 리스트들을 지칭한다... 메모리에 저장하는 물리적인 순서가 순차적으로 되어있다). 선형리스트에서 원소의 삽입과 삭제 1. 선형리스트에서 원소를 삽입하려면 삽입하려는 위치부터 그 뒤의 원소들을 모두 한칸씩 뒤로 옮긴다음 저장해야 된다. 선형리스트에서 원소를 삭제하려면 원소를 삭제하고 그 뒤의 원소들을 한칸씩.. 더보기
자료구조 시작! 이 게시판은 개인적으로 자료구조를 공부하고 정리한 내용을 작성한 것입니다. 한빛아카데미/이지영 저자의 자바로 배우는 쉬운 자료구조를 통해 공부하였습니다. 한번만 하고 끝낼건 아니라 공부한 내용은 지속적으로 수정하고 업데이트 할 예정입니다. 잘못된 내용의 지적은 매우 감사드립니다. 더보기

티스토리툴바