반응형 Programming/Algorithm&DataStructure13 [JAVA/자료구조] Queue Interface Queue 선입선출(FIFO) '대기열'을 뜻함 시간 순으로 어떤 작업 또는 데이터를 처리할 필요가 있는 것들은 큐의 성질을 갖고 있다. 대표적으로 알고리즘에서는 BFS(너비 우선 탐색)에 사용된다. 자바에서 제공하고 있는 큐는 인터페이스에 불과하고, 큐를 구현하는 클래스는 크게 세 가지가 있다. PriorityQueue(우선순위 큐), ArrayDeque(배열 양방향 큐), LinkedList(연결리스트) Queue Interface에 선언된 대표적인 메소드 java에서는 Vector클래스를 상속받다보니 아래의 클래스보다 훨씬 많은 메소드를 지원한다. 메소드 리턴 타입 설명 offer(E e) boolean 큐의 마지막에 요소를 추가한다. poll() E 큐의 첫번째 요소를 제거하고 제거된 요소를 반환.. 2021. 8. 19. [JAVA/자료구조] Stack 구현 https://prinha.tistory.com/entry/JAVA%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack-Interface [JAVA/자료구조] Stack Interface Stack 후입선출(LIFO) 한 번쯤, StackOverflowError를 마주할 수 있는데 재귀가 깊어지면서 발생한 오류이다. 메소드를 호출할 때마다 메소드 내에 정의된 변수들의 값이 Stack내에 쌓이게 되는데, 재귀가 prinha.tistory.com Stack Interface Source 더보기 package Interface_form; /** * * 자바 stack Interface입니다. * StackInterface는 Stack에 의해 구현됩니다. * * @author st_lab.. 2021. 8. 9. [JAVA/자료구조] Stack Interface Stack 후입선출(LIFO) 한 번쯤, StackOverflowError를 마주할 수 있는데 재귀가 깊어지면서 발생한 오류이다. 메소드를 호출할 때마다 메소드 내에 정의된 변수들의 값이 Stack내에 쌓이게 되는데, 재귀가 깊어지면 Stack 메모리에 이 값들이 쌓이면서 총량이 할당된 메모리 양보다 커질 때 내뱉게 된다. Stack의 활용 1) 페이지 뒤로가기, 실행 취소 가장 최근에 방문했던 페이지가 가장 상단에 위치함, 실행 취소 또한 마찬가지다. 2) 수식 괄호 검사 여는 괄호가 있으면 닫는 괄호 또한 반드시 있어야 한다. 어느 하나라도 부족하거나 많을 경우 수식을 완성할 수 없다. Stack Interface에 선언된 대표적인 메소드 java에서는 Vector클래스를 상속받다보니 아래의 클래스보.. 2021. 8. 9. [JAVA 자료구조] Doubly LinkedList (이중 연결리스트) Doubly LinkedList 단일 연결리스트와 달리 '이전 노드'를 가리키는 변수가 추가된 양방향 리스트 - 단일 연결리스트에 비해 검색(색인) 능력이 좋아진다. - 이전 노드를 가리키는 변수를 갖고 있기 때문에 tail부터 탐색할 수 있다. (좀 더 효율적) 더보기 package Interface_form; /** * * 자바 List Interface입니다. * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다. * * @author st_lab * @param the type of elements in this list * * @version 1.0 * */ public interface List { /** * 리스트에 요소를 추가합니다.. 2021. 8. 9. [JAVA 자료구조] Singly LinkedList (단일 연결리스트) Singly LinkedList 배열이 아닌 '노드'를 이용하여 여러 노드를 하나의 체인처럼 단방향으로 연결한 리스트 (위 그림에서 각각의 레퍼런스 변수는 다음 노드객체를 가리키고 있음) 이미지 출처 : https://st-lab.tistory.com/167 더보기 package Interface_form; /** * * 자바 List Interface입니다. * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다. * * @author st_lab * @param the type of elements in this list * * @version 1.0 * */ public interface List { /** * 리스트에 요소를 추가합니다. *.. 2021. 8. 5. [JAVA 자료구조] ArrayList ArrayList Object[] 객체 배열을 사용하는 자료구조로 사이즈를 정하지 않고 동적으로 활용할 수 있다. 리스트 계열 자료구조는 데이터 사이에 빈 공간을 허락하지 않는다. 더보기 package Interface_form; /** * * 자바 List Interface입니다. * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다. * * @author st_lab * @param the type of elements in this list * * @version 1.0 * */ public interface List { /** * 리스트에 요소를 추가합니다. * * @param value 리스트에 추가할 요소 * @return 리스트에서 .. 2021. 8. 4. [JAVA 자료구조] List Interface (리스트 인터페이스) 배열 vs List 인터페이스 공통점 1. 동일한 특성의 데이터타입을 묶는다. 2. 반목문내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다. 차이점 - 배열 1. 처음 선언한 배열의 크기는 변경할 수 없다. 정적 할당(static allocation) 2. 메모리에 연속적으로 나열되어 할당된다. 3. 인덱스에 위치한 하나의 데이터를 삭제하더라도 해당 인덱스는 빈공간으로 남는다. 차이점 - 리스트 1. 리스트의 길이가 가변적이다. 동적 할당(dynamic allocation) 2. 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지않고 데이터들은 주소로 연결되어있음. ex.C의 포인터) 3. 데이터 사이에 빈 공간을 허용하지 않는다. 장점 1. 데이터의 크기가 정해져있을 경우 메.. 2021. 8. 4. [Algorithm] 정렬 알고리즘 요약 정리 선택정렬 - 정렬되지않은 데이터 중 순차적으로 가장 작은 수를 선택하고 교환해나가는 정렬 - 장점 : 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점 (풀스캔) - 단점 : 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 오래걸림 - 시간복잡도 : O(N^2) - 연산법 : N*(N+1) / 2 public class sortAl { /** * 알고리즘 * * * 1. i = 0 * * * 2. i부터 N-1까지 가장 크거나 작은값을 찾는다. * * * 3. i와 가장 크거나 작은값을 교환한다. 동일한 값일 경우 교환하지 않는다. * * * 4. ++i * 5. 2부터 다시 반복한다. */ int value[] = {5, 3, 8, 2, 10, 9, 4, 1}; .. 2021. 8. 1. [Algorithm] 시간 복잡도 & Big-O표기법 시간복잡도(Time Complexity) 특정 알고리즘이 문제를 해결하는데 걸리는 시간 정확한 값을 산출하는 것이 아니라 근사치를 계산한다. 점근적 표기법 - 시간복잡도를 나타내는데 사용됨 1) 최상의 경우 : 오메가 표기법(Big-Ω Notation) 최적의 입력을 한 상태에서 작업을 완료하는데 가장 빠른 시간 2) 평균의 경우 : 세타 표기법 (Big-θ Notation) 여러가지 다른 경우의 수를 입력하여, 총실행시간을 계산하고 시행횟수로 나눈다. 3) 최악의 경우 : 빅오 표기법 (Big-O Notation) 최악의 입력을 한 상태에서 작업을 완료하는데 가장 느린 시간 -> 평균인 세타 표기법을 사용하면 좋겠지만 평가하기가 까다로워 최악의 경우인 빅오를 많이 사용한다. Big-O 표기법 - 점근적.. 2021. 7. 30. [Algorithm] 공간 복잡도 공간복잡도(Space Complexity) 프로그램이 얼마나 많은 공간(메모리)를 차지하느냐를 분석하는 방법 공간복잡도 빅-오 계산법 1) 일반적으로 공간이 하나씩 생성되는 것을 1이라고 표현함 아래의 공간복잡도는 O(1) int a = 5; 2) 반복문에서의 지역변수 사용시 n값에 상관없이 공간복잡도는 O(1) 반복문이 N번만큼 반복하여도 for문 안에서의 지역변수이므로 다른 것에 영향 X int f(int n) { int i = 0; int result = 1; for(i = 1; i 1) return n * factorial(n -1); else return 1; } 프로그램에 필요한 공간은 고정, 가변 공간으로 나눌 수 있다. 시간적인 측면을 무시하고 공간복잡도만을 생각한다면 고정 공간보다는 가변.. 2021. 7. 30. [Algorithm] 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 바로 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 정렬법(반복) - 선택 정렬과 같이 직관적인 알고리즘 - 가장 비효율적인 정렬 알고리즘 - 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 시간이 오래걸림 예제) 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 1) 한번의 반복이 끝나면 가장 큰 값이 뒤로 보내지는 정렬법 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 8 7 10 6 4 3 2 9 1 5 8 7 6 10 4 3 2 9 1 5 8 7 6 4 10 3 2 9 1 5 8 7 6 4 3 10 2 9 1 5 8 7.. 2020. 8. 10. [Algorithm] 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 가장 작은 것을 선택해서 제일 앞으로 보내고 자리를 바꾸는 정렬법(반복) - 비효율적인 정렬 알고리즘 - 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 시간이 오래걸림 예제) 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 - 코딩하기 전 정렬 해보기 - 1 10 5 8 7 6 4 3 2 9 1 2 5 8 7 6 4 3 10 9 1 2 3 8 7 6 4 5 10 9 1 2 3 4 7 6 8 5 10 9 1 2 3 4 5 6 8 7 10 9 1 2 3 4 5 6 7 8 10 9 1 2 3 4 5 6 7 8 9 10 #include int main(void){ int i,j,min,index,tem.. 2020. 8. 5. 이전 1 2 다음 반응형
