알고리즘 문제를 풀며 최적화를 하기 위해 자료 구조의 형식을 고민했던 적이 있다.그 대상은 바로 LinkedList와 ArrayList이다. 오늘은 그 고민을 하면서 알게 된 지식들을 정리하고, 어떤 상황에 어떤 자료 구조가 어울리는지(합리적인지) 논하여 보고자 한다.ArrayList와 LinkedList의 차이를 이해하기 위해서는 java collections 프레임워크에 대해서 먼저 논해야 한다.둘 다 Collections interface를 implement 하였기 때문이다.CollectionsCollections는 데이터를 효율적으로 저장하고 조작하는 java 표준 라이브러리다.주요 인터페이스로는 List, Set, Queue, Map이 있다. 이 라이브러리는 우리가 코딩을 하면서 상황과 의도에 ..

주어진 과목을 조합해서 N~2N사이의 학점을 맞추면 되는 문제이다.문제 해결 전략가장 먼저 생각한 것은 그리디 알고리즘이였다. 하나씩 더해보면서 N~2N 사이의 학점의 합을 만들어내면 바로 조그 조합을 출력하도록 하였다.문제를 푸는 알고리즘은 다음과 같다.1. 강의를 점수가 높은 순서대로 정렬한다.2. 높은 점수부터 하나씩 선택하며 합계를 관리한다.3. 만약 sum + 현재 강의 점수가 require 이상이면서 require * 2 이하라면 선택 후 종료한다.4. 그렇지 않다면, require * 2를 넘지 않는 한 계속 강의를 선택한다.5. 선택한 강의의 개수와 번호를 출력한다.reverse order로 정렬한 이유는 만약 오름차순으로 정렬했을 때 예외가 생기기 때문이다.만약..

문제 해결 전략숫자를 이어붙이는 문제였다.처음에는 문제를 잘못 이해해서 각 집에 붙어 있는 수를 반대로도 뒤집을 수 있는 줄 알았는데, 그냥 순차적으로 이어붙이는 문제이다.BFS를 통해 각 집을 방문한다면 어렵지 않게 이어 붙인 수를 구할 수 있다.그러나 이 문제의 킥은 그게 아니였다.집에 붙어 있는 숫자가 1,000,000,000일 수 있기 때문에 long을 사용해도 String → Long에서도 NumberFormatException이 날 수 있다.그냥 수를 계속 더하는 것이면 Modular의 분배 법칙을 사용할 수 있다.근데 이 문제는 수를 이어 붙이는 것이다. 이를 위해서는 곱셈에 대한 분배법칙도 사용하여야 한다.이를 이용하면 두 수를 붙일 때도 모듈러 연산을 할 수 있고 오버플로우를 방지할 수 ..

게임 판을 움직여서 구슬을 탈출시켜야 하는 그래프 문제이다.문제 해결 전략이 문제는 판을 기울여 공을 굴러가게 하여 빨간 구슬만 구멍을 빼는 것이다.판을 움직인다는 것은, 공이 끝까지 굴러가서 벽에 부딛히거나 or 구멍에 빠지거나 라는 결론을 맞이하게 된다.그래서 move라는 함수를 두어 공이 어디까지 굴러갈 것인지 구하였고,두 공이 움직일 때 독립적으로 계산하면 같은 위치에서 멈출 가능성이 있다. 이런 경우에는 더 많이 굴러온(멀리서 굴러온)공이 가까이서 굴러온 공에 의해 멈출 것임으로 이동방향을 한번 빼 주었다.또한, 빨간 공이 구멍을 통해 나왔는데 파란 공도 구멍을 통해 나오는 경우가 있고, 파란 공만 나오는 경우가 있다.이런 경우는 유효한 경우가 아니기 때문에, 먼저 파란 공이 구멍을 통해 나오는..

열쇠를 찾고, 문을 열어서 문서를 가져와야 하는 심화 BFS 문제이다.문제 해결 전략다른 그래프 문제보다 까다롭고 어렵게 만드는 요소는 문과 열쇠다.열쇠를 찾고 문을 열어야 하기 때문이다.문제를 보고 가장 먼저 고안한 로직은 다음과 같다.입구를 찾는다(벽이면 입구로 사용할 수 없음)열쇠를 찾는다.문이 나오면 문을 연다.(만약 열쇠가 있을 시)문서를 찾고 ans++을 수행한다.하지만 다시 생각을 해보니 열쇠를 찾기 위하여 문을 열어야 할 수 있다.따라서 다시 고안한 로직은 다음과 같다.입구를 찾는다(벽이면 입구로 사용할 수 없음)bfs를 수행한다.문이 나오면 열쇠가 있는지 확인하고 있다면 연다.문이 나왔는데 열쇠가 없다면 문의 위치를 기록한다.(Map사용)만약 열쇠가 나오면 열쇠를 저장한다.(Set사용)그..

문제 해결 전략백준 12015랑 이어지는 문제이다. 다른 점은 수열의 숫자가 음수가 포함되며, 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력해야 한다. [Java] 백준 12015 가장 긴 증가하는 부분 수열 2 (G2)문제 해결 전략이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.dp를 이용하여 모든 요소를 비교하면서 가장 긴 증가하는 부분 수열을 찾을 수도 있지만, 이는hyogu.tistory.com 이 문제를 참고하면 기본적으로 가장 긴 증가하는 부분 수열의 길이을 구하는 방법을 알 수 있다.이 문제는 길이뿐만이 아니라 어떻게 하면 가장 긴 증가하는 부분 수열을 찾을 수 있을 것인가 에 포커싱 한다고 생각한다. 그래서 도입한 로직은 original 수열의 숫..

문제 해결 전략이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.dp를 이용하여 모든 요소를 비교하면서 가장 긴 증가하는 부분 수열을 찾을 수도 있지만, 이는 시간복잡도가 O(n^2)로 수열의 길이가 1,000,000이기 때문에 timeout이 날 것이다. 이 문제를 풀 때는 길이를 강조하고 싶었다. 주어진 수열을 모두 순환하면서 만나는 값이 현재 가장 긴 증가하는 수열의 max value보다 크다면 append하고 그렇지 않다면 수열 중 가장 가장 가까우면서 크지 않은 값으로 교체하는 방법을 사용했다.가장 가까우면서 크지 않은 값으로 교체하는 이유는 뒤에 올 수 있는 수의 범위를 넓혀주기 위해서다.  예를 들어 특정 수열을 기반으로 가장 긴 증가하는 부분 수열을 만들어간다..

문제 해결 전략이 문제를 푸는 데는 두 가지 아이디어가 필요했다. 1) 외적을 이용하여 선분의 교차를 판별외적을 하게 되면 외적하는 벡터에 따라서 외적의 결과의 방향이 평면을 나오는 방향과 평면을 뚫고 들어가는 방향이 나오게 된다. 이 방향의 차이를 이용하여 선분의 교차를 판단하게 된다.위 문제는 2차원 평면의 점이 주어지므로 외적 공식은 다음과 같다. 즉, k union vector의 방향(부호)이 외적 결괏값의 방향인 것이다.선분들이 놓일 수 있는 방향에 대한 일반화를 해보면 다음과 같다. 1번 경우 : 두 선분이 교차하는 경우 : 벡터AB를 기준으로 벡터 AD와 벡터 AC를 각각 외적 하였을 때 부호가 다르다.2번 경우 : 두 선분이 교차하지 않는 경우 : 벡터 CD를 기준으로 벡터CB와 벡터 CA..