SW 공부노트

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제를 보고 바로 우선순위 큐를 사용하면 되겠구나! 하고 생각했다. 하지만 우선순위 큐는 인덱싱 기능이 없어서 가운데 값을 어떻게 구해야 되나 헤매다 우선순위 큐를 빌 때까지 poll 해 temp 우선순위 큐에 넣고, 이를 List로 변환 후 인덱스를 통해 가운데 값을 구했다. 답은 제대로 출력됐지만 메모리 초과 때문에 실패했다😢 풀면서도 더 나은 방식이 있을 것 같아서 검색해 본..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net Union Find의 기초문제이다. 이 문제를 통해 처음으로 Union Find 알고리즘을 공부하였다. 예시 코드가 자바는 아니지만 다음 글이 큰 도움이 되었다 👍 https://4legs-study.tistory.com/94 분리 집합 (Disjoint Set) : Union-Find 서론 다음과 같은 메신저 프로그램이 있다. "A와 B가 친구 관계이고, 내..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택을 활용한 문제이다. push하는 순서가 오름차순이므로 1부터 n까지 차례대로 push 한다고 생각하면 된다. 내가 생각한 풀이 방안은 다음과 같다. 현재까지 넣은 수가 현재 차례의 배열값보다 작거나 같다면 push -> 크다면 바로 top과 비교 push 작업이 끝난 후 스택의 top 값이 현재 배열값과 같다면..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net x좌표를 오름차순으로 정렬하고, x좌표가 같으면 y좌표가 증가하는 순으로 정렬하는 문제이다. 좌표를 2차원 배열에 저장하고, Arrays.sort와 Comparator의 compare 함수를 오버라이딩해 정렬 조건을 걸어주면 된다. compare 함수는 람다함수를 사용해 더 편리하게 작성할 수 있다. 정렬 코드는 다음과 같다. 정렬 알고리즘 상..