본문 바로가기

알고리즘41

원래 barkingDog님의 글을 보고 공부를 하고 있었으나 기본적인 제반지식이 부족함을 느껴 좀 더 차분히 깊게 보고 다시 시작하려 한다. 2021. 11. 25.
자바의 자료구조 - 스택의 활용 드디어 본격적인 시작이다. 다시 한번 밝히지만 해당 포스팅들은 https://blog.encrypted.gg/919 이 출처이며, 해당 블로그의 포스팅을 공부하는 포스팅이다. 정확한 정보와 자세한 내용은 해당 블로그를 보는 것을 강력히 권한다. : 수식의 괄호 쌍 간단한 스택의 활용이다. (, {, [ 등이 올때 Stack에 담고, 쌍이 맞는 ),},]이 올때 pop()을 시키어 해결하는 구조다. : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 심화로.. 2021. 11. 21.
자바의 자료구조 - 덱 : DEque deque는 양쪽 끝에서 삽입과 삭제가 모두 가능하다. Double Ended Queue라는 뜻을 갖고 있다. Stack과 Queue를 Deque의 특수한 예시라고 생각해도 좋다. : 시간복잡도 원소의 추가가 O(1) 원소의 제고가 O(1) 제일 앞/뒤의 원소확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. : C에서는 직접 구현하는 내용이 있었지만, 자바에서는 기본 타입중에 있기때문에 직접사용할 수 있다. 2021. 11. 20.
자바의 자료구조 - 연결리스트 : 연결리스트는 순차적으로 연결된 자료구조이다. A, B, C가 있다면 A는 B의 위치를 기억하고, B는 C의 위치를 기억하는 구조이다. A만 알고있으면, 순서대로 나아가기만 하면 전체를 알 수 있다. 다만 이 방식으로만 다른 원소들에 접근할 수 있고, B나 C에 바로 접근할 수는 없다. : 연결리스트 성질 1. k번째 원소를 확인 / 변경하기위해 O(k)가 필요 2. 임의의 위치에 원소를 추가 / 임의의 위치의 원소를 제거 O(1) 3. 원소들이 메모리상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결리스트에서는 임의의 위치에 원소를 추가하거나 임의 위치 원소 제거가 O(1)이다. 배열과 비교시 가장 큰 차이가 있는 성질이고, 연결 리스트의 장점이다. 이는 밑에서 좀 더 .. 2021. 11. 20.
자바의 자료구조 - Heep 역시나 순서는 이상한 기분이지만 크게 지장은 없을 듯 하다. 곱셈을 배우고 덧셈을 배우면 아 이렇게 곱셈에 쓰였구나 할 수도 있으니 앞으로도 나오는 자료구조 포스팅을 참고하면 좋을 듯 하다. : Heep은 우선순위 개념을 Queue에 이용하여 만들어진 자료구조이다. 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터를 먼저 배출한다. 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다. 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기 위한 자료구조이며, 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하.. 2021. 11. 19.
자바의 자료구조 - Stack 순서가 좀 이상해진 기분이 들지만 이번 자료구조는 Stack이다. 스택은 총의 탄창을 생각해보면 구조가 매우 흡사하다. 탄창을 입구로 총알을 넣고, 가장 먼저 넣은 총알이 가장 마지막에 발사되게 된다. 이러한 선입후출의 자료구조가 Stack이다. ( First In Last Out ) 단순한 구조이기 때문에 Stack이 갖는 특징이 있는데, 1. 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다. 2. 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다. 3. 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다. : 스택의 사용 : 재귀 알고리즘 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다. 재귀함수를 빠져 나와 퇴각 검색(backtrack)을.. 2021. 11. 19.
자바의 자료구조 - Map : Map은 Collection 인터페이스와 별개이지만, json형식과 유사한 key-value 자료구조로 자주 사용되는 구현체이다. 사전과 같은 형태의 자료구조로, ( 사전과 달리 순서는 없다. ) 중복된 key를 가질 수 없고 각 key는 오직 하나의 value에만 mapping될 수 있다. Map 인터페이스를 구현한 클래스는 HashMap, TreeMap, LinkedHashMap, Hashtable 이 있다. Hashtable은 null을 허용하지않고, HashMap은 null을 허용한다. 심지어 HashMap은 Key, Value에 모두 null이 허용되고, HashTable은 Key, Value에 모두 null이 불가하다. ( 타 ide는 모르겠지만, 이클립스의 경우 코딩에 오류는 발생하지 않.. 2021. 11. 19.
자바의 자료구조 - 이진 탐색 트리, 레드 블랙 트리 : 이진탐색트리(Binary Search Tree) 이진 탐색 트리에는 자신의 왼쪽 서브 트리에는 현재 노드보다 key값이 작은 것, 오른쪽 서브 트리에는 현재 노드보다 key값이 큰 것, 을 배치해 탐색이 가능. 이진 탐색 트리에서 중위순회를 하게되면, 오름차순으로 정렬된 순서로 key값을 얻을 수 있다. 이렇게 되어 있을때, 중위순회란 7->3->8->1->9->4->10->0->11->5->2->6 이런 순서로 참조하는 것을 말하고, 왼쪽에는 현재보다 key값이 작은 원소, 오른쪽에는 현재보다 key값이 큰 원소가 위치하기에 오름차순으로 정렬되게 된다. 그래서 탐색의 시간 복잡도는 O(h) ( h = 트리의 높이 ) 가 된다. : 레드 블랙 트리 이 역시도 이진 탐색 트리의 일종이다. 그런고로 동일.. 2021. 11. 19.
자바의 자료구조 - List 참고하던 블로그에서는 C언어 기반으로 자료구조를 설명해서 자바의 자료구조는 따로 찾아보았다. 우선 자료구조란? - 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 형태. - 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨 - 자료의 효율적인 관리는 프로그램의 수행 속도와 밀접한 관련이 있음. - 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로, 자료구조에 대한 이해가 중요함. ( 출처 : https://soliloquiess.github.io/study/2021/03/20/java_%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0.html ) 1) Type[] (변수명) 기본적인 타입을 가지고 만드는 배열이다. 선언시 null 혹은 크기를 .. 2021. 11. 18.
공간복잡도 참고자료 : https://blog.encrypted.gg/922 공간복잡도 - 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 이 크기는 메모리의 크기를 의미한다. 참고 : 512mb = 1.2억개의 int ( int 1개가 4바이트 ) 참고 : char 자료형은 1byte = 8bit ( c언어 기준, 자바는 2byte ) N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1) 예상한 코드가 제한이상의 메모리를 요한다면 다른 방법을 고민해보도록 하자. 이러한 1byte는 0,1 즉 이진수가 하나 들어가는 공간이다. int는 byte의 공간을 갖는데 2^31-1개의 숫자를 표현할 수 있다. 2147483647로 21억 정도의 숫자이다. 즉, 이를 벗어난 숫자를 int로 .. 2021. 11. 17.

티스토리툴바