고양이 두 잔

Index 문제 두 전봇대 A와 B 사이에 하나둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구..

문제 수열 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를 제어하려면 그대로 스트림을..

목차 스택, 큐, 트리, 그래프에 대해선 지난번에 짧게 요약했다. 이번 글에선 자료구조 중 배열 + 컬렉션 프레임워크에 대해 가능한 짧게 요약한다. Array 배열은 한 마디로 말하면 같은 자료형과 길이가 정해진 행렬이라고 할 수 있다. 행렬이기 때문에 인덱스가 정의되어 있고, 메모리를 연속으로 사용할 것을 요구하기 때문에 각각의 값은 변경할 수 있으나 한 번 정해진 크기는 바꿀 수 없다. 또한 엄밀하게 말하면 자바의 배열은 기본적으로 제공하는 자료형이기 때문에 다양한 관련 함수가 정의되어 있으며, 별도의 호출 없이 손쉽게 정의할 수 있다. 배열은 자료형인가? 결론부터 말하자면 자바에서 배열은 자료형이며 동시에 자료구조로도 분류할 수 있다. 자료형은 변수의 타입을 가리키는 단어이며, 자료구조는 데이터의 ..