java
[백준] 2110번 : 공유기 설치 - JAVA [자바]
[백준] 2110번 : 공유기 설치 - JAVA [자바]
2021.12.08https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 문제를 정확히 파악만 한다면 매우 쉬운 문제다. 알고리즘 [접근 방법] 그동안 숫자 카드, 랜선 자르기, 나무 자르기를 순서대로 풀어왔다면, 이 번 문제는 그리 어렵지는 않았을 것이다. 그럼에도 정답률이 낮은 이유라 한다면, 아마 이분탐색 구현을 제대로 하지 않았기 때문일 가능성이 매우 높지 않을까 생각을 해본다만.. 그렇기 때문에 필자가 ..
자바 [JAVA] - 팀 정렬 (Tim Sort)
자바 [JAVA] - 팀 정렬 (Tim Sort)
2021.11.02[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge sort) 8. 퀵 정렬 (Quick Sort) 9.이진 삽입 정렬 (Binary Insertion Sort) 10. 팀 정렬 (Tim sort) - [현재 페이지] Tim Sort [팀 정렬] 이번 포스팅의 경우 병합 정렬과 삽입 정렬(그 중 이진 삽입 정렬) 메커니즘을 토대로 하기에 반드시 병합(합병) 정렬과 이진 삽입 정렬을 먼저 보고 오시기를 바란다. (참고로 여기서 다룰 병합 정렬은..
[백준] 2805번 : 나무 자르기 - JAVA [자바]
[백준] 2805번 : 나무 자르기 - JAVA [자바]
2021.09.12https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 이 전의 랜선 자르기 문제와 매우 유사한 문제다. 만약 직전 문제를 안풀어보셨다면 먼저 풀고오는 것을 추천한다. 그러면 이 문제도 자연스럽게 바로 풀릴 것이다. 알고리즘 [접근 방법] 이 번 문제는 앞서 언급했듯 랜선 자르기 문제와 풀이 방식이 거의 같은 문제다. 이 문제를 풀기 전에 되도록이면 아래 글을 먼저 보고 오시는 것을 추천한다. 모두 다 연계..
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
2021.08.31https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 이분 탐색의 응용 문제다. 알고리즘 [접근 방법] 일단, 이 번 문제를 풀기 전에 이분 탐색 중 Upper Bound 에 대해 이해하고 있어야 한다. 그러니, 해당 원리를 이해하기 위해 아래 포스팅을 먼저 보시고 오시기를 바란다. https://st-lab.tistory.com/267 [백준] 10816번 : 숫자 카드 2 - JAVA [자바] https://ww..
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
2021.08.06https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 직전 문제랑 비슷하지만, 이분 탐색을 활용해야 할 경우 조금 고려해야 할 부분이 있는 문제다. 알고리즘 [접근 방법] 이 문제 자체는 그리 어렵지 않다. 사실 이분 탐색을 쓰지 않고도 카운팅 정렬 형식을 사용하여 풀 수도 있다만, 그래도 이분 탐색 카테고리에 있는 만큼 한 번 이분 탐색 풀이 방식을 통해 풀이를 해보도록 하자. 일단, 이분 탐색의 경우 구간의..
자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort)
자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort)
2021.08.01[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge sort) 8. 퀵 정렬 (Quick Sort) 9. 이진 삽입 정렬 (Binary Insertion Sort) - [현재 페이지] 10. 팀 정렬 (Tim Sort) Binary Insertion Sort [이진 삽입 정렬] 이번 포스팅의 경우 삽입 정렬을 토대로 하기에 반드시 삽입 정렬을 먼저 보고 오시기를 바란다. 만약 필자의 정렬 알고리즘을 시리즈로 보았다면 왜 퀵 정렬 다음에 이진 ..
[백준] 1920번 : 수 찾기 - JAVA [자바]
[백준] 1920번 : 수 찾기 - JAVA [자바]
2021.07.16https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 새 카테고리인 이분 탐색의 첫 번째 문제인 수 찾기다. 알고리즘 [접근 방법] 일단, 풀이 방법을 알아보기 전에 이분 탐색(Binary Search)에 대해 알아보자. 이 전 문제까지 우리가 분할 정복을 살펴보았다. 분할 정복 방식의 경우에는 문제가 주어지면 해당 문제를 둘 이상으로 나누면서 나눠진 부분문제에 대해 풀렸다면 해당 부분은 끝내고,..
자바 [JAVA] - Linked Hash Set (연결 해시 셋) 구현하기
자바 [JAVA] - Linked Hash Set (연결 해시 셋) 구현하기
2021.07.02자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중 연결리스트 (Doubly LinkedList) 5. 스택 인터페이스 (Stack Interface) 6. 스택 (Stack) 7. 큐 인터페이스 (Queue Interface) 8. 배열 큐 (Array Queue) 9. 연결리스트 큐 (LinkedList Queue) 10. 배열 덱 (Array Deque) 11. 연결리스트 덱 (LinkedList Deque) 12. 배열 힙 (Heap) 13. 우선순위 큐 (Priority..
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
2021.06.26https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 문제 이 번 문제는 분할 정복 카테고리의 마지막 문제인만큼 조금 많이 어려운 문제다. 분할 정복 방식 자체는 이전 문제인 히스토그램에서 가장 큰 직사각형과 접근 방식은 유사하나 조금 더 신경써야할 부분들이 존재하므로 같이 알아보도록 하자. 알고리즘 [접근 방법] 이 번 문제의 경우 일반적인 분할 정복 방식과 스윕 라인 방식 이렇게 두 가지 풀이 방식이 존재한다. 일..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]
2021.06.18https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 히스토그램 내의 가장 큰 넓이를 구하는 문제는 엄청 유명한 문제라 알고리즘을 많이 접해보았다면 한 번쯤은 접해보았을 문제다. 알고리즘 [접근 방법] 이 번 문제의 경우 풀이 방법 자체는 대표적으로 두 가지 방식이 있다. 먼저 이 문제의 카테고리 처럼 분할정복으로 풀이하는 방식, 그리고 스택 자료구조를 이용한 풀이 방식이 있다. 이 번에..