Computer Science

[자료구조] 큐(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. 같은 점수를 지닌 두 학생에 대해 학번으로 순번을 지정) - 내부 정렬과 외부 정렬 : 정렬할 모든 데이터를 하나..