룰루랄라 알고리즘

이 문제도 dp를 이용하기에 아주 좋은 문제인 것 같다. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 전략은 dp테이블을 2차원 배열로 다음과 같이 생성하는 것! dp[자릿수][n으로 끝나는 수] 배열은 0부터 시작하기 떄문에 dp[1][2]는 자릿수가 2개인 숫자 중에 2로 끝나는 수의 개수를 의미한다. 계단 수의 특징은 0과 9로 끝나는 수는 다음 자리수에 1과 8만 올 수 있으므로 해당 케이스는 따로 처리하고, 나머지 숫자들은 자신의 수 보다 +1, -1 한 dp[i][j+1] + dp[i][j-1]로 계산한다. 또한 수의 크기가 크므로 자료형을 l..

반년만에 문제를 풀기 때문에 근본문제인 DFS를 다시 한번 풀어보자 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 너무 오랜만에 풀어서 기억이 안났다. 특히 2차원 배열로 행렬 만들 때 가로 세로가 너무 헷갈린다. 행렬에서 상하좌우로 움직여 구역을 나누는건 DFS로 풀자. 아직도 헷갈리는데 X:가로, Y:세로 일 때 int [X][Y] 이렇게 선언해야 할 듯. matrix = new int [M+1][N+1]로 선언한 것은 사실 M, N으로 해도 되지만 ..

여태 실버문제는 풀지 않았지만 코테문제는 실버에서 골드 수준으로 나온다는 걸 알게 되고 앞으로는 적극 실버를 풀 생각이다. 마침 대학교 알고리즘 시간에 분할정복, DP의 차이점과 상황에 따른 우수성을 배운지 얼마 지나지 않았어서 해당 문제를 보고 바로 DP로 풀어야 한다는 생각이 났다. 감사합니다 프로페서 조. https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 해당 문제는 이미 재귀 분할정복으로 구현되어 있는 식을 DP로 바꾸는게 풀이였다. 해당 식..

열거한 값들이 주로 단독이 아닌 집합으로 사용될 경우, 예전에는 각 상수에 서로 다른 2의 거듭제곱 값을 할당한 정수 열거 패턴을 사용해 왔다. 비트 필드 비트 필드 열거 상수 아래처럼 비트별 OR를 사용해 여러 상수를 하나의 집합으로 모을 수 있으며, 이렇게 만들어진 집합을 비트 필드라 한다. text.applyStyles(STYLE_BOLD | STYLE_ITALIC); 비트 필드를 사용하면 비트별 연산을 사용해 합집합과 교집합 같은 집합 연산을 효율적으로 수행할 수 있다. 비트 필드는 정수 열거 상수의 단점을 그대로 지닌다. 비트 필드 값이 그대로 출력되면 단순한 정수 열거 상수를 출력할 때보다 해석하기 훨씬 어렵다. 비트 필드 하나에 녹아 있는 모든 원소를 순회하기도 까다롭다. 최대 몇 비트가 필..

가뭄에 단비 같은 아이템이구나.. 대부분의 열거 타입 상수는 자연스럽게 하나의 정숫값에 대응된다. 모든 열거 타입은 해당 상수가 그 열거 타입에서 몇 번째 위치인지를 반환하는 ordinal 메서드를 제공한다. 이런 이유로 열거 타입 상수와 연결된 정숫값이 필요하면 ordinal 메서드를 이용하고 싶은 생각이 들 수 있다. 하지만 ordinal 메서드는 많은 단점이 있다. 합주단 종류를 연주자가 1명인 SOLO 부터 10명인 DECTET까지 정의한 열거 타입 동작은 하지만 유지보수하기 힘들다. 상수 선언 순서를 바꾸면 numberOfMusicians가 오작동한다. 이미 사용 중인 정수와 값이 같은 상수는 추가할 수 없다. (8중주가 이미 있으므로 똑같이 8명이 연주하는 복4중주는 추가할 수 없다.) 값을 ..

정수 열거 패턴 자바에서 열거 타입을 지원하기 전에는 다음 코드처럼 정수 상수를 한 묶음으로 선언해서 사용했다. public static final int APPLE_FUJI = 0; public static final int APPLE_PIPPIN = 1; public static final int APPLE_GRANNY_SMITH = 2; public static final int ORANGE_NAVEL = 0; public static final int ORANGE_TEMPLE = 1; public static final int ORANGE_BLOOD = 2; 하지만 이 정수 열거 패턴은 상당히 취약하다. 1. 타입 안전을 보장할 방법이 없으며 표현력도 좋지 않다. 오렌지를 건네야 할 메서드에 사과..

타입 안전 이종 컨테이너란, 제네릭을 이용하여 서로 다른 타입의 객체를 담을 수 있는 컨테이너를 말한다. 즉, 컨테이너 내부에 저장된 객체들이 모두 같은 타입일 필요가 없으며, 다양한 타입의 객체들을 함께 보관하면서도 타입 안정성을 보장할 수 있다. 컨테이너(Container) 컨테이너란 객체를 담는 역할을 하는 클래스를 의미한다. 일반적으로 다수의 객체를 담을 수 있는 객체를 말하며, 주로 배열(Array)과 컬렉션(Collection)이 포함된다. 타입 안전 이종 컨테이너 패턴 컨테이너 대신 키를 매개변수화한 다음, 컨테이너에 값을 넣거나 뺄 때 매개변수화한 키를 함께 제공하면 제네릭 타입 시스템이 값의 타입이 키와 같음을 보장해 준다. 타입별로 즐겨 찾는 인스턴스를 저장하고 검색할 수 있는 Favo..

가변인수(varags) 메서드와 제네릭은 서로 잘 어우러지지 않는다. 1. 가변인수 메서드를 호출하면 가변인수를 담기 위한 배열이 자동으로 하나 만들어지는데 만약 varargs 매개변수에 제네릭이나 매개변수화 타입이 포함되면 컴파일러는 타입 안전하지 않다고 생각하여 컴파일 경고를한다. 2. 모든 제네릭과 매개변수화 타입은 실체화되지 않는데, 메서드를 선언할 때 실체화 불가 타입으로 varargs 매개변수를 선언하면 컴파일러가 경고를 보낸다. 3. 매개변수화 타입의 변수가 타입이 다른 객체를 참조하면 힙 오염이 발생한다. 다른 타입 객체를 참조하는 상황에서 컴파일러가 자동 생성한 형변환이 실패할 수 있어 제네릭의 타입 안전이 실패한다. 힙 오염 제네릭과 varargs를 혼용하면 타입 안정성이 깨진다. 마지..

매개변수화 타입은 불공변이다. List은 List의 하위 타입이 아니다. 이러한 문제로 인해 발생하는 오류를 해결하기 위해 한정적 와일드카드를 사용한다. 한정적 와일드카드 매개변수화 타입 T 생산자 : 이므로 null 외에는 어떤 값도 넣을 수 없다. 따라서 와일드카드 타입의 실제 타입을 알려주는 private 도우미 메서드를 따로 작성하자. swapHelper 메서드는 리스트가 List 임을 알고 있기 때문에 리스트에서 꺼낸 값의 타입이 항상 E이고, E 타입의 값이라면 리스트에 넣어도 안전함을 알고 있다. 완성된 swap 메서드 swap 메서드 내부에서는 복잡한 제네릭 메서드를 이용했지만, 덕분에 외부에서는 와일드카드 기반의 멋진 선언을 유지할 수 있다. 요약 조금 복잡하더라도 와일드카드 타입을 적용..

클래스와 마찬가지로 메서드도 제네릭으로 만들 수 있다. 형변환이 필요한 기존 메서드를 제네릭 메서드로 만들자. Union 메서드 로 타입 로 타입을 사용해 구현한 Union 메서드 컴파일은 되지만 타입 안정성을 보장하지 못한다. 제네릭 메서드 로 타입으로 구현한 Union을 제네릭 메서드로 변경해 보자. 메서드 선언에 세 집합 (입력 2개, 반환 1개)의 원소 타입을 타입 매개변수로 명시 메서드 안에서 이 타입 매개변수만 사용하도록 수정 타입 매개변수 목록 ()은 메서드의 제한자와 반환 타입 사이에 위치 타입 매개변수 목록 : 반환 타입 : Set 경고 없이 컴파일되며, 타입 안전하고, 직접 형변환 하지 않아도 된다. 제네릭 싱글턴 팩터리 때때로 불변 객체를 여러 타입으로 활용할 수 있게 만들어야 할 때..