전체 글
-
7 - 2. 행사 준비CS/ProblemSolving 2023. 9. 23. 15:03
https://www.acmicpc.net/problem/30022 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 그리디 문제중에 기본적이면서도 알면 좋을만한 기법을 쓸 수 있는 문제입니다. 행사 준비하는데 물품 N개가 필요하고, 이를 휴먼1이 A개 휴먼2가 B개를 준비하기로 합니다. 이때 상점 2개가 존재하는데, 각 상점은 물품 x, y, ...에 대해 서로 다른 가격으로 판매하고 있습니다. 이럴땐 담합 좀 하면 ..
-
4 - 3. Xayahh-Rakann at Moloco (Hard)CS/ProblemSolving 2023. 3. 11. 18:25
https://www.acmicpc.net/problem/15509 15509번: Xayahh-Rakann at Moloco (Hard)The first line contains three integers n, m, and k where 1 ≤ n, k, ≤ 1,000 and 1 ≤ m ≤ 1,000,000. The following m lines contain two integers per line where each line describes an inseparable pair of jars (the two integers in the same line are dwww.acmicpc.net 서로소 집합을 만드는 문제입니다. 영문으로 써져있어서 풀기가 너무 귀찮은데, 전 이 정도로 물러날 코더가 아니죠..
-
Factory Method pattern & Abstract Factory PatternCS/Design Pattern 2022. 8. 27. 18:03
팩토리 메서드 패턴과 추상 팩토리 패턴의 구조와 두 패턴에 대해 정리합니다. Factory Method? 어떤 인스턴스를 생성하는 책임을 구체적인 클래스가 아닌 추상적인 인터페이스의 메서드로 감싸는 방식 필요성 객체를 생성할 때, 동일한 객체에 대한 요구사항이 추가되어도 기본 로직이 변화하지 않도록 방지 (OCP) Factory Method 적용 전 Ship.java (생성할 객체에 대한 정보) public class Ship { private String name; private String color; private String logo; // getter, setter } ShipFactory.java (주문에 맞춰 생성) public class ShipFactory { public static S..
-
SingletonCS/Design Pattern 2022. 8. 6. 18:15
해당 글은 Singleton 객체가 무엇인지, 필요성, 생성 방법, Singleton을 깨트리는 요소들과 이를 대응하는 방법에 대해 기술합니다. Singleton? 인스턴스를 오직 하나만 만드는 클래스 (public, global 접근 가능한) 필요성 어떤 서비스에서 유일하게 존재하는 기능인 경우 ex) 사용자마다 필요한 설정 기능 사용자 개인이 해둔 설정은 수정하지 않는 이상 변함이 없어야 한다. - 만약 설정 화면을 들어 갈 때마다, 인스턴스를 새로 생성한다면? -> 사용자는 매번 설정을 다시 해야함. public class Singleton { } Singleton class가 존재할 때, 외부 클래스에서 호출해 사용하는 경우 아래와 같다. public class Main { public stati..
-
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 우리의 주인공 농부..
-
Generic과 raw-type 그리고 비검사 경고CS/Java (with Effective) 2022. 4. 28. 16:25
해당 글은 Effective Java item26, item27을 기반으로 합니다. 로 타입은 사용하지 말라. 비검사 경고를 제거하라. Generic 파트는 엄청 긴 것도 아니거니와.. 객체를 선언하고 Generic을 통해 타입 선언 등에 있어서 주의할 점이 많을 것 같아 웬만하면 싹다 훑고 가려합니다. item 26. raw 타입은 사용하지 말라. 우선 Generic class, Generic Interface란, 아래와 같이 선언에 있어 타입 매개 변수를 사용한 경우를 의미합니다. public interface List extends Collection { ... } 해당 코드는 대표적인 제네릭 인터페이스 List의 선언부입니다. 원래는 List로 표현하는게 맞지만, 단순히 List라고도 선언할 수 ..
-
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 기존 클..