java
-
4 - 2. Closing the Farm (Gold)CS/ProblemSolving 2022. 6. 5. 15:17
https://www.acmicpc.net/problem/12012 12012번: Closing the Farm (Gold) The output consists of \(N\) lines, each containing "YES" or "NO". The first line indicates whether the initial farm is fully connected, and line \(i+1\) indicates whether the farm is fully connected after the \(i\)th closing. www.acmicpc.net 완전 좋아하는 알고리즘 중 하나인 서로소 집합 문제인데, 거기에 오프라인 쿼리를 잘 곁들인 문제라 소개해볼까 가져왔습니다. USACO 우리의 주인공 농부..
-
7 - 1. 우체국CS/ProblemSolving 2022. 3. 6. 16:19
https://acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 최근에 푼 그리디 문제 중에, 코테에서도 종종 봤던 유형인 것 같아 이번 기회에 기억에 남길겸 정리해보려 합니다. 문제는 읽기 귀찮으니까 대충 그림으로 표현해서 보겠습니다. 아래와 같이 수직선 상 X 좌표에 마을이 존재하고, 각 마을에는 A명의 사람들이 살고 있습니다. 각 사람들의 거리의 합이 최소가 되는 위치에 우체국을 ..
-
Composition vs extendsCS/Java (with Effective) 2022. 3. 2. 15:08
해당 글은 Effective Java Item18을 기반으로 합니다. 상속보다는 컴포지션을 사용하라. 해당 글에서 상속은 인터페이스의 상속(implements)은 포함하지 않습니다. '상속(extends)은 메서드 호출과 달리 캡슐화를 깨트린다.' 즉, 상위 클래스가 어떻게 구현되는냐에 따라 하위 클래스가 오작동 할 수 있다는 뜻입니다. 상위 클래스 구현이 변경되는 경우 하위 클래스 또한 변경해야할 수도 있는 것이죠. 따라서, 이러한 문제점을 방지하기 위해 composition의 사용을 제안하고 있는데요. composition이 무엇인지 살펴보고, 상속시 발생할 수 있는 문제점, 그리고 어떤 경우에 composition 또는 extends를 사용하는지에 대해 알아보겠습니다. Composition 기존 클..
-
Map 그리고 merge()CS/DS & OOP 2022. 1. 29. 12:32
Java의 자료구조 중 Map에 대해 이야기 해보려합니다. HashMap, TreeMap 두가지에 모두 적용되는 이야기입니다. 간단히 두 맵에 대해 알아보고, 알아두면 좋을 내용들 그리고 마지막으로 merge에 대해 살펴보겠습니다. Map Key, Value로 내부 데이터를 구성하고 Key는 중복이 불가능하지만, Value 값은 중복 가능합니다. 중복이 가능하고 불가능 여부는 아래와 같습니다. Map map 로 선언한 경우 i) key 중복 map.put("apple", 1); map.put("apple", 2); => map.get("apple"); 호출 시 2의 값을 반환합니다. ii) value 중복 map.put("apple", 1); map.put("banana", 1); => map.get("..