알고리즘/자료구조
-
Queue (큐)알고리즘/자료구조 2020. 12. 30. 00:24
Queue FIFO(First In First Out, 선입선출) 구조를 가지고 있는 자료구조다. 매표소에서 표를 예매하는 것과 같다. 매표소에 줄을 섰을 때, 먼저 온 사람이 앞에 서서 먼저 표를 구매하고 빠져나간다. 나중에 온 사람은 앞에 사람들이 빠질 때 까지 기다렸다가 자기 차례가 오면 구매하고 빠져나간다. 큐에 데이터를 넣는 행위를 enqueue라고 한다. 큐에서 데이터를 꺼내는 행위를 dequeue라고 한다. 두가지 자료구조를 활용해서 큐를 구현했다. 하나는 배열, 하나는 ListNode(LinkedList를 실습하기 위해 만든 클래스)이다. 배열로 구현했을 땐, 크기를 미리 정해야하기 때문에 가변적이지 못하다. ListNode로 구현했을 땐 큐 크기 제한이 없다. 테스트코드 포함 전체 코드 ..
-
Stack (스택)알고리즘/자료구조 2020. 12. 29. 23:32
Stack LIFO(Last In First Out) 구조를 가진 자료구조다. 말그대로 나중에 들어온 데이터가 먼저 나간다. 먼저 들어온 데이터가 가장 아래에 위치한다. 아래있는 데이터를 꺼내려면 그 위에 있는 데이터를 모두 꺼내야 한다. 스택에 데이터를 넣는 행위를 push 이라고 한다. 스택에서 데이터를 꺼내는 행위를 pop 이라고 한다. 두가지 자료구조를 활용해서 스택을 구현했다. 하나는 배열, 하나는 ListNode(LinkedList를 실습하기 위해 만든 클래스)이다. 배열로 구현했을 땐, 크기를 미리 정해야하기 때문에 가변적이지 못하다. ListNode로 구현했을 땐 스택 크기 제한이 없다. 구현1 (int 배열 사용) 테스트코드 포함 전체 코드 링크 package com.example.wee..
-
Linked List (연결 리스트)알고리즘/자료구조 2020. 12. 29. 21:26
Linked List 리스트 자료구조는 중복 저장을 허용하며 데이터를 나란히 저장한다. 자바에는 리스트 자료구조를 정의해놓은 List컬렉션이 있다. (인터페이스) 객체를 인덱스로 관리하여 객체를 삽입하면 인덱스가 자동으로 부여된다. 그래서 인덱스로 객체에 검색, 삭제가 가능하다. 객체를 직접 저장하고 있지 않고 객체의 주소를 가지고 있다. null도 저장이 가능하다. (아무것도 참조하지 않는 상태) 구현체로 ArrayList, LinkedList, Vector 등이 있다. LinkedList(연결 리스트)는 List 인터페이스의 구현체로 메모리의 동적할당을 기반으로 구현된 리스트다. LinkedList의 모든 노드는 인접 노드를 참조해서 체인처럼 관리한다. 노드를 리스트의 중간에 삽입하여도 인접한 노드들..
-
리스트 (List)알고리즘/자료구조 2019. 8. 17. 19:53
리스트의 가장 큰 특징은 ★순서대로 저장. ★중복저장 허용 이다. 배열과 비교 1. element 추가 예를들어 3번째 인덱스에 데이터를 추가하면 배열: 3번째 인덱스에 있던 기존의 데이터가 지워지고 새로운 데이터가 저장된다. (덮어쓰기) 리스트: 3번째 인덱스에 있던 데이터부터 한칸씩 밀려나고 새로운 데이터가 3번째 인덱스 자리에 추가된다. 2. element 제거 예를들어 3번째 인덱스에 데이터를 제거하면 배열: 3번째 인덱스에 있던 기존의 데이터가 지워지고 element는 유지된다. 메모리를 추가로 차지하게 된다. 리스트: 3번째 인덱스에 있던 element가 제거되어 4번째 인덱스에 있던 데이터부터 한칸씩 당겨진다. 3. 인덱스 배열에서 인덱스는 값에 대한 유일한 식별자이다. 배열은 인덱스가 중요..
-
배열 (Array)알고리즘/자료구조 2019. 8. 17. 17:33
배열은 이미 많이 사용하고 있기때문에 아는 내용이지만 좀더 명확하게 배열의 장단점 및 특징을 정리해보려고 한다. 배열도 하나의 자료구조(Data Structure)이고 이걸 인지하면 자료구조를 바라보는 시선이 조금 편안해진다.. 특징 -★index를 이용해 식별-저장-데이터를 가져온다. -그룹으로 관리되고, 그룹에 해당되는 데이터만 처리가 가능하다. -반복문(for, while, iterator등)을 이용하여 데이터에 접근하는 등 처리를 한다. -데이터가 많고 그룹관리가 필요할때 배열을 사용한다. -배열은 하나의 이름으로 그룹핑하여 관리하게 된다. 한계, 단점 만약 한 학급을 배열에 넣어 관리할때, 한 학생이 전학을 간다면? 인덱스3에 null값이 들어있다고 가정하면 반복문으로 출력시 순서대로 이름과 중..
-
자료구조 공부 시작.알고리즘/자료구조 2019. 8. 17. 16:34
https://www.opentutorials.org/module/1335 이 강의를 참고하여 공부를 시작하려고 한다. 학교에서 자료구조 강의를 이미 들었지만 성적이 좋지않았고 필요성을 느끼지 못해 열심히 하지 않았었다. 그리고 그마저 군대에 다녀온후 모두 잊어버렸다. 학교에서 c로 직접 자료구조를 구현하는 실습을 많이 했었는데 자바에는 이미 collection framework가 존재한다. list, map, set등의 인터페이스가 존재하고 각각 인터페이스의 특징을 알고 활용을 위해 클래스들을 알아야한다.