개발저장소 by 회창 개발저장소 by 회창

좌표 정보를 문제를 풀기위해 재정렬 하는 과정이라고 생각하면 편하다. 보통 일정 범위내의 수직선에서, 특정 구간내 점의 개수를 구하는 문제를 볼 수 있다. 이럴 때, 모든 점을 해당 수 범위내에 표기하기 위해서 점이 있다 없다를 기준으로 boolean 배열을 사용하곤 한다. 그렇지만 이는 index == 점위치 가 되기 때문에 점의 값이 사실상 억을 넘어서면 "메모리 초과" 를 당하거나 안당하더라도 순회하면서 점을 전처리하는데 시간 복잡도를 초과할 가능성이 크다. 여기서 볼 수 있는 관찰은, 전처리를 해야함을 인지하였으나 주어진 점들을 표기하는 방법에 있어서 문제가 있다. 일반적으로 숫자가 매우 큰 상황에서 해당 숫자를 인덱스로 사용해야 한다면 배열이 아닌 HashMap을 사용하면 좋다. 왜냐하면 Has..

DP문제는 다양하지만 2차원배열에서 한칸씩 전진하면서 그순간마다 최적의 선택을 통해 최종답을 구해나가는 DP가 있다. DP는 어디까지나 전체를 한번에 구한단 생각을 버리고 아주 작은구간 (예를들어 어떤 칸 하나 까지 오는 경우의수) 이런것부터 차곡차곡쌓아나가야 한다. 그러면 반복되는 수학식 즉, 점화식이 보이게 된다. 다음은 정수 사각형의 최소이자 최대 라는 문제인데 사실 문제제목만 보기에는 약간 이상하다. 왜냐하면 최소이자 최대라는게 무슨말일까? 최소이자 최대는 즉, 특정 도착지점까지의 경로들은 각각의 경로상의 최솟값이 있는데, 그들중 최대를 구하는것 여기서 서브프라블럼은 뭘까? 바로 특정칸까지 도달하기 전까지는 모두 어떤 특정경로의 최소일 것이다. 즉, 문제에서 주어진 방향대로 진행해 나가는것은 결국..

PQ를 써야하는 순간은 보통 자신이 정한 정렬기준을 통해 지속적으로 정렬상태를 특정 시점마다 유지하고 싶을때 사용한다. 생각해보면 PQ만 정렬을 보장해주는 자료구조가 있는것은 아니다. Java에는 PQ, TreeMap, TreeSet 이 있다. 각각 어떨때 쓰는것이 좋을까? TreeSet의 경우에는 PQ와 거의 동일하다. 오히려 TreeSet은 최대(first) 최소(last)를 관리하기 더 편하며, 특정 값 바로 이상(floor), 초과(higher), 이하(ceiling) 그리고 미만(lower)인 값을 꺼내는데 유용하다. 하지만 TreeSet은 어디까지나 Set을 기반으로 한 OrderedSet이라는것을 잊으면 안된다. 즉, 정렬의 대상이되는 원소에 대한 중복을 허용치 않는다는점이다. 예를들어서 어..

해시 셋은 보통 중복을 제거하여 고유의 값을 뽑아낼때 사용한다.  약간 돌려서 얘기하자면, 쓸데없는 값이 중복되어 연산되는걸 막아줄때 사용하기도 한다. 코드트리에 있는 "초대장과 번호표" 라는 문제가 있는데, 이는 백준의 "거짓말" 과 비슷하게 생겼다. 물론 백준의 "거짓말" 문제는 범위가 매우 작다( 코드트리 문제 기준으로 그룹이 50개고 각 그룹별 50명이다. ) 하지만 코드트리의 문제는 범위가 그룹은 최대 25만개에 인원또한 25만명으로 책정되어 있다. 이걸로 인해 시간복잡도 N^2의 완전탐색은 불가하다고 생각하겠지만 중요한 조건이 추가적으로 있다. 바로 " 모든 그룹 내 사람 수의 총합  이걸 해석해보면 그룹이 극단적으로 25만개 였다 하더라도, 그룹별 인원은 1명이 되는것이다. 즉, 그룹과 인원..

코드트리에 HashMap을 활용하는 문제에서 임의의 두 수의 합을 구하는 문제가 있다. 수가 중복해서 나올 수 있는점을 고려해야 하기에 문제가 까다롭지만, HashMap을 사용하면 상수시간에 가까운 시간복잡도로 문제를 해결할 수 있다. HashMap을 굳이 안쓰고 문제를 접근할 수도 있다 (투포인터, 합이 0에 가까운 또다른 수 찾기 (이분탐색)) 하지만 숫자가 매우 큰경우에는 일반적인 배열의 인덱스로 활용하기 힘들기에 해싱 자료구조를 채택하는것이 좋다. 문제중에 두 수의 합과 세 수의 합이 있는데, 초안으로는 이분탐색과 투포인터로 해결할 실마리가 보였지만 반례에 막혔고 중복된 수에 대한 경우의수 예외를 적절하게 처리해주면 된다. 이를 위해 미리 수에 대한 카운팅 Map을 만들어주고 현재 소모할 숫자를 ..