[PCCP 교육] 3일차

블로그 정리 미루다가 2일차랑 3일차 한번에 쓰려니까 죠큼 힘들ㄷr..🫠

조금씩 꾸준히가 왜 중요한지 알 것 같군..

 

 

📌 스택(Stack)

: 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조.

 

📌 스택의 연산

✔️ push()

✔️ pop()

✔️ peek() : 가장 위에 있는 데이터 반환(삭제X)

✔️ empty() ← isEmpty()도 가능! (Vector 클래스로부터 상속받아서) 

❕ 스택에서 pop(), peek()를 하기 전에 empty()를 먼저 확인해야 함!

❕ 스택을 쓰면 보통 while(!stack.empty())를 많이 사용! 

 

🔍 스택 공식 문서

https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html

Stack (Java Platform SE 8 )

💁🏻‍♀️ 스택을 언제 쓸 수 있을까?!

✔️ 짝꿍(페어)의 개념으로 자신의 짝을 찾을 때 (ex. 이웃한 게 충돌해서 사라짐)

✔️ 입력에 (괄호)가 있을 때

 

 

📌 큐(Queue)

: 한 쪽 끝에서 자료가 삽입되고, 반대쪽 끝에서 자료가 삭제되는 FIFO(First In First Out) 형식의 자료구조.

 

📌 큐의 연산

✔️ offer() : 삽입

✔️ poll() : 가장 앞에 있는 값반환 + 삭제

→ add(), remove()는 에러를 발생시킬 수도!

 

❕ 자바에서 큐는 LinkedList로 구현!

Queue<Integer> queue = new LinkedList<>();

 

🔍 큐 공식 문서

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

Queue (Java Platform SE 8 )

💁🏻‍♀️ 큐는 언제 쓸 수 있을까?!

✔️ BFS에 많이 사용! (단독으로 나오면 난이도가 상당함❗)

✔️ 자료가 원형(순환)을 이룰 때

 

 

📌 정렬

1️⃣ 오름차순 정렬

Arrays.sort(nums);

→ 정수형 배열(ex. int[]), char[], T[] 모두 정렬 가능!

 

2️⃣ 내림차순 정렬

Integer[] boxedNums = Arrays.stream(nums).boxed().toArray(Integer[]::new); //외우기
Arrays.sort(boxedNums, (a, b) -> b - a);

💁🏻‍♀️ Integer[]을 다시 int[]로 어떻게 바꾸죠?

Arrays.stream(boxedNums).mapToInt(i->i).toArray();

❕ 정렬 기준을 추가하고 싶으면 람다식에서 삼항연산자 이용!

Arrays.sort(nums, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]); / nums는 int[][]

 

3️⃣ ArrayList 정렬

list.sort((a, b) -> a[0] - b[0]); //list는 ArrayList<int[]>
Collections.sort(list, (a, b) -> a[0] - b[0]);

 

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html

Arrays (Java Platform SE 8 )

 

 

📌 그리디 알고리즘

: 선택의 순간마다 당장 눈앞에 보이는 최고의 상황만을 쫓아 최종적인 해답에 도달하는 알고리즘.

 

💁🏻‍♀️ 그래서, 그리디 알고리즘을 언제 쓰나요?

✔️ 최적해(최대, 최솟값)을 구할 때 그리디로 풀수도 있음

✔️ 입력이 정렬되어 있으면 그리디 문제일 확률↑ (정렬과 자주 연관)

✔️ 그리디 문제인 것 같아도 반례를 찾아보는 연습을 해봐야 함!

 

💡 알고리즘 문제 Tip

❕ 학생번호 등이 나올 때, 0부터 시작인지 1부터 시작인지 체크! (이것에 따라 index를 바로 이용하거나 index+1을 해주어야 함)

 

 

✍🏻 새롭게 알게 된 JAVA (ex. 클래스, 라이브러리, 메서드)

✔️ StringBuilder reverse()

✔️ 동적배열을 만들 때는 ArrayList<>() 사용!

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

ArrayList (Java Platform SE 8 )

✔️ new ArrayList<>(hash.values()) ← 이렇게 값을 넣어서 ArrayList를 초기화할 수도 있음