고양이 두 잔

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 동적계획법의 유명한 문제라고 알려진 가장 긴 증가하는 부분수열(LIS - Longest Increasing Subsequence) 문제이다. 예전에 한 번 풀었던 풀이를 보니 탑다운 방식으로 구성..

알고리즘 문제를 이리저리 돌려가며 풀다가 Map을 스트림으로 다룰 때의 자료형이 필요했다. 일단 인텔리제이에서 알려주는 대로 사용해서 문제를 풀고, 따라가며 공부하기. Map.Entry 소개부터 하자면 Map.Entry는 자바 컬렉션 프레임워크의 Map 인터페이스의 내부 인터페이스이다. Map과 마찬가지로 키-값의 데이터를 저장하며, Map에서 .entrySet() 연산자를 호출하면 생성할 수 있다. 정확하게 말하자면 .entrySet()의 경우 이름 그대로 아래와 같은 Set을 생성하며, Map integerMap = new HashMap(); Set set = integerMap.entrySet(); 위 Set에 모든 엔트리 객체가 담겨있기 때문에 개별 Map.Entry를 제어하려면 그대로 스트림을..

Hash 배열은 빠른 검색 속도를 가지고 있으나 삽입/삭제 시 많은 비용이 소모된다. 이를 극복한 LinkedList는 삽입/삭제의 비용이 적지만 데이터가 많아질수록 검색에 비용이 많이 든다. 해시는 이를 극복하기 위해 도입된 개념이다. 해시, 해시 함수(Hash Function)란 임의의 길이를 갖는 임의의 데이터를 받아 고정된 길이의 데이터를 리턴하는 단방향 함수를 말한다. 가장 쉬운 예로는 나머지 연산자(%)가 있을 수 있겠다. 해시 함수의 특징은 아래와 같으며, 비교적 간단한 알고리즘으로 시스템 자원을 덜 소모한다, 즉 해시값 생성에 많은 시간이 들지 않는다. 해시값을 해독할 때는 많은 시간이 든다. 같은 입력 값에 대해선 같은 출력 값이 보장되며, 출력 값은 고르게 분포한다. 입력값이 아주 조금..

문제 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 각 문자열은 입력 순서대로 1부터 시작하는 번호를 부여받는다. 입력으로 주어지는 문자와 번호에 대해 대응하는 값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 문제의 개수 M (1 ≤ N, M ≤ 100,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열과 번호들이 주어진다. 입력으로 주어지는 문자열은 알파벳 대문자와 소문자로 이루어져 있으며, 길이는 최소 2, 최대 20이다. 또한 입력으로 주어지는 숫자는 1과 N 사이의 숫자이다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄부터 차례대로 M개의 주에 문제에 대한 답을 출력..