자료구조, 알고리즘

[정렬] 정렬 문제 풀이 및 속도 비교

■ 정렬의 속도 / 메모리 사용 비교 - 미니멈이 1이고, 맥시멈이 백만인 숫자를 입력받아 정렬한다고 할 때, 어떤 정렬을 쓰는게 좋을까....? - 문제를 풀어본 결과, Merge sort가 가장 빨랐고, 그 다음에 Arrays.sort, 그 다임이 Quck Sort 였다. - 그럼 Arrays.sort는 무슨 정렬을 사용하는 걸까... https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net ■ Collections와 Arrays의 Sor..

[정렬] 병합정렬(Merge Sort)

☆ 공부한 내용을 정리한 내용입니다. 잘못된 부분이 있으면 고정 위해 댓글 부탁드립니다. https://www.youtube.com/watch?v=QAyl79dCO_k&list=PLjSkJdbr_gFZMNhIMl2AJ9n5c2hNK-qJk&index=2 ■ 병합 정렬 - 병합 정렬이란? 요소가 하나만 남을 때까지 리스트를 나눠준 후[분할], 나눴던 리스트를 대소 관계에 맞게 다시 합치는 방법[병합] - 분할 분할 분할 분할.... 병합 병합 병합 병합... 을 반복한 결과 - 안정적이지만, 자료구조를 하나 더 만들 필요가 있다. *자료구조를 더 만들 수 없을 땐 퀵 소트를 쓴다. - 시간 복잡도 O(n log n) , 최악(n log n) ■ 자바로 구현한 병합 정렬 //[[부스트 코스 방식]] stat..

[정렬] 퀵 정렬(Quick Sort)

☆ 공부한 내용을 정리한 내용입니다. 잘못된 부분이 있으면 고정 위해 댓글 부탁드립니다. ■ 퀵 정렬 원리 ) 중심점(Pivot Point)을 임의로 고른 후 이 중심점보다 작은 수를 한 쪽으로 분류하고, 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법 * 분할과 정복 - 중앙값 정렬 방식을 확장하여 개발한 방식. - 평균 정렬 결과가 필요할 때 사용하는 것이 좋다. - 퀵 정렬은 멀리 있는 값을 서로 비교하고 교환하기 때문에 안정성은 떨어진다. - 시간 복잡도 O(n log n) ※ 피벗을 중간 또는 마지막을 잡는 이유 : - 피벗은 첫번째, 중간, 마지막 인덱스나 랜덤으로 선정 가능하다. - 무엇을 피벗으로 잡느냐에 따라 처리 시간이 달라진다. - 피벗 값이 중간 크기일 수록 더 균등하게 리스트를 분할..

[자료구조] 큐(Queue)

■ 큐란? - FIFO (First in First Out) 방식으로 데이터를 입출력 - 현실 세계의 큐 예 ) 티켓 판매기에서 대기하고 있는 사람들, 일방통행 도로의 차동자들, 인쇄기의 인쇄 순서, CPU의 테스크 스케줄링 - 큐의 한계 : 1) front부터 삭제되며, 삭제된 공간을 다시는 사용하지 못한다. 2) (배열을 사용할 경우) 큐의 크기가 정해지기 때문에 rear가 더 움직이지 못한다. (-> 이 부분은 자바에서는 동적관리 객체인 LinkedList로 해결했다) - 큐의 한계를 보완 : 원형 큐, 우선순위 큐 ■ 큐의 내부 구조 - 유투브의 영상에 나와있는 튜토리얼에 따라 큐를 구현해보았다. https://www.youtube.com/watch?v=W3jNbNGyjMs&list=PLjSkJd..

[자료구조] 스택

[자료구조 알고리즘] Stack 구현하기 in Java - YouTube [ 스택의 활용 예 : 출처 자바의 정석 ] 수식 계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로 ★ 문제 : 10828번: 스택 (acmicpc.net) 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ★ 스택 단계 (acmicpc.net) 스택 단계 주어진 문자열이 올바른 괄호열인지 판단하는 문제 www.acmicpc.net ■ 스택을 생성해보는 예제 import java.io.Buff..

[검색] 선형탐색과 이진탐색

■ 선형검색 : 정렬되지 않은 데이터를 0부터 끝까지 확인할 때 유리 - 의사코드 for i from 0 to n-1 if i'th element is the target value return true return false - 자바코드 package linearSearch; import java.util.Arrays; public class LinearSearch1 { public static void main(String[] args) { int[] arr = new int[10]; init(arr); System.out.println(Arrays.toString(arr)); //linear search //전제 : 정렬되지 않은 데이터 //찾으려는 수 : 5 for (int i = 0; i < a..

[자바의 정석] 스택과 큐

1. 스택과 큐 https://www.youtube.com/watch?v=ktvhRSRohR4 ▶ 스택(Stack) : 밑이 막힌 상자 - LIFO구조. Last in First Out / push(저장) & pop(추출) 방식 - 배열이 적합 *순차적인 추가/삭제 ▶ 큐(Queue) : 양끝이 뚫린 상자(포장마차의 종이컵 빼는 것과 같다) - FIFO구조. First in First Out / otter(저장, 제공한다) & poll(추출) - 링크드리스트가 적합 *비순차적인 추가/삭제 ■ 스택의 메소드 **JAVA에서 스택은 클래스 (객체생성 가능) push(Object) : Object --- Stack객체에 item을 저장 pop( ) : Object --- 맨 위의 것 꺼내기 empty( ) :..

[자바의 정석] ArrayList/LinkedList

1. ArrayList : 배열 기반 리스트 https://www.youtube.com/watch?v=_2e-cgwMOyc ▶ Vector를 개선. *차이점) Vector는 동기화 가능/ ArrayList는 동기화X ▶ 생성자 ArrayList() ArrayList(Collection c) 컬렉션을 넣으면 배열리스트로 변경됨 ArrayList(int initalCapacity) 저장하려는 갯수만큼 길이 지정 * 저장갯수를 지정해주지 않으면 배열이 늘어나고 줄어들 때마다 배열이 새로 생성되기에 성능 떨어진다. ▶ 메소드 추가 삭제 검색 기타 add(Object o) : boolean add(int index, Object element) addAll(컬렉션) addAll(index, 컬렉션) remove(..

[자바의 정석] 컬렉션 프레임웍(Collection Framework) 기초

▶ 들어가기 전에.. 컬렉션의 대부분의 내용은 자바의 정석 강의을 보고 공부하고 있습니다. 영상 내용 중 중요한 것을 작성했으나 제가 쓴 부분이 오류가 있을 수 있으니 오류가 있으면 댓글 부탁드립니다. 1. 컬렉션 프레임웍(Collection Framework)의 이해 https://www.youtube.com/watch?v=z9GpUGoYCw4 ■ 용어 ▶ 컬렉션 (모아놨다) ▶ 프레임웍(정형화된 틀) : 라이브러리 + 프로그래밍 방식 *라이브러리 : 다른 사람이 이미 만들어 놓은 걸 모아논 곳(라이브러리=도서관). 기능만 제공한다(ex. JavaAPI) ▶ 컬렉션 프레임웍 : 다수의 객체를 다루기 위한 표준화된 프로그래밍 방식 *객체 = 데이터 - java.util 패키지에 포함. (JDK2.0부터)..

[정렬] 버블정렬,선택정렬,삽입정렬, 셸 정렬

1. 알고리즘이란? https://why-dev.tistory.com/6?category=917883 [컴퓨터 공학_복습] 알고리즘 정의, 검색과 정렬 알고리즘 ▼ 부스트 코스의 컴퓨터 공학 내용을 복습 & 요약한 내용입니다. https://www.boostcourse.org/cs112 부스트코스의 컴퓨터 공학을 수강 중인데, 알고리즘 부분 내용이 잘 이해가 가지 않아서ㅠㅠ 스스로 why-dev.tistory.com 2. 정렬 - 정의 : 이름,학번,키 등 핵심항목(key)의 대소관계에 따라 순서대로 값을 나열하는 것 - 안정성 : 키값이 같은 요소의 순서가 정렬 후에도 유지되는 것 (ex. 같은 점수를 지닌 두 학생에 대해 학번으로 순번을 지정) - 내부 정렬과 외부 정렬 : 정렬할 모든 데이터를 하나..