![[이분 탐색] 백준 1920번 : 수 찾기 - Java](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdaFf3j%2FbtsNxwddhU3%2FyfzsSQbieUCiohCHQ4SiDK%2Fimg.png)
✅ 문제https://www.acmicpc.net/problem/1920✅ 분류이분탐색✅ 공부한 내용N의 최대범위가 10만이므로, 단순 반복문으로는 풀 수 없다.이분탐색을 적용하면 O(nlogn) 시간 복잡도로 해결할 수 있다. 이분 탐색은 데이터가 정렬되어있는 상태에서 원하는 값을 찾아내는 알고리즘이다.대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.[이진 탐색 과정] - 오름차순으로 정렬된 데이터인 경우 (내림차순이면 조건 반대)현재 데이터셋의 중앙값을 선택한다중앙값 > 타깃데이터일때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.중앙값 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.✅ 풀이import java.util.*;import..
![[큐] 백준 10845번 큐 - Java](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbTnO8e%2FbtsNdyBy7tj%2FyXZLqxbmrqVXdU5jdYOoGk%2Fimg.png)
https://www.acmicpc.net/problem/10845✅ 문제🔑 풀이import java.io.*;import java.util.*;// deque 활용public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); Deque..
![[스택] 백준 3986번 좋은단어- Java](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbPWk2N%2FbtsNcWCM0mG%2Fo7WdwGhT5qysxWqP86XCu1%2Fimg.png)
https://www.acmicpc.net/problem/3986✅ 문제📌 접근방법처음에 문제를 한 번에 이해를 못했지만, 알고리즘 분류에 스택이라는 힌트를 보고 다시 생각해보니 어떻게 접근할 지 이해가 되었다.ABAB는 선이 교차해서 좋은 단어가 될 수 없다. ABBA와 AABB는 선끼리 교차하지 않고, 각 글자가 다른 위치에 있는 같은 글자와 짝 지을 수 있어 좋은 단어가 될 수 있다.스택을 만들어 스택이 비어있는 상태가 되면 좋은 단어가 된다.🔑 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReade..
![12. [Java] 투 포인터 (2-Pointer)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcBBw3P%2FbtsMTF8gTTa%2FvnNkZzFuEnATA8NVk64yQ0%2Fimg.png)
일반적으로 배열에서 2개의 인덱스(포인터)를 움직이면서 문제를 해결하는 방법보통 왼쪽(left), 오른쪽(right) 혹은 시작(start), 종료(end) 쌍으로 포인터를 표현한다.외워야 할 알고리즘이라기 보다는 이렇게도 문제를 풀 수 있구나 정도로 알아두면 된다.2개의 포인터를 동시에 +1씩 움직이면서 답을 구하는 알고리즘은 [슬라이딩 윈도우] 라고 부르기도 한다. Referencehttps://www.acmicpc.net/problem/2559https://school.programmers.co.kr/learn/courses/30/lessons/42885https://school.programmers.co.kr/learn/courses/30/lessons/67258