Today's Algorithm(2019-02-14) 며칠 전에 푼 문제인데 최근에 좀 바빠서 바로 정리하지 못했네요. 빠르게 정리해볼게요! 추석 트래픽 이번에 푼 문제는 문제 자체를 이해하는 것이 참 힘들었습니다. 문제를 제대로 이해하는 것에서부터 해결방법을 고려해야하는데 문제 이해에서만 20~30분이 걸린 것이죠. 이 문제에서 날짜 데이터를 처음엔 Date 를 이용해서 푸려고 했습니다. 하지만 이 값을 이용해야하는데 Date 타입으로는 어떻게 해야할지 잘 모르겠더라구요. 그래서 getTime() 을 이용하여 다시 ms 단위로 바꾸었습니다. 결론적으로 이렇게 푸는 것이 더 낫다는 생각이 들었습니다. 그 이유는 초가 소수점 3자리까지 표현되기 때문에 ms로 나타내는 것이 소수점 계산을 하지 않아도 된다는..
Today's Algorithm(2019-02-10) programmers. 뉴스 클러스터링(소요시간 : 80분) 풀면 그렇게 어렵지 않았는데 시간이 조금 오래걸린게 아쉽습니다. 문제 이해하고 분석하여 코드를 짜기전까지 20 ~ 30분 정도 걸린 것 같습니다. 아마도 문제에 '자카드 유사도'와 같은 겁먹게 하는 용어가 있어서 그런 것 같기도 합니다. 문제는 다음 3단계로 나누어 풀었습니다. 문제열을 쪼개 집합 2개를 만듭니다. 이때 각 집합에 대한 자료형은 Map 로 합니다. 처음에 이를 List으로 하려했는데 중복 계산이 복잡할 것 같아 Map 으로 바꾸었습니다. 이를 바꾼게 탁월한 선택이었습니다. 두 집합의 합집합, 교집합을 구합니다. 중복처리에 유념합니다. map1 의 반복문을 돌려 map2에 있는..
programmers. 가장 큰 정사각형 찾기 dp를 이용하는 문제였습니다. 처음엔 하나하나 들러서 갈 수 있는 최대길이를 반복문을 통해 찾아 해결하려고 했었습니다. 그런데 효율성 테스트까지 있는 것보니 이렇게 해서는 복잡도가 커서 통과하지 않을 것 같더라구요. 고민하다 다른 사람의 블로그를 참고하였습니다. 역시나 좀 더 쉽게 해결할 수 있는 방법이 있더라구요. dp 문제는 알고나면 딱 그렇게 푸는게 보이는데 모르는 상태에선 dp문제라는 것을 아직은 감잡기가 힘든 것 같아요. 전략은 1일 때 위, 왼쪽, 좌측위 중에서 가장 작은 값에 +1을 해가면서 표시를 해두고 나중에 가장 큰 값을 찾아 제곱하는 것입니다. 처음엔 위, 왼쪽만으로 제대로 계산이 될 줄 알았는데요. 생각해보니 위, 왼쪽이 예를들어 1이 ..
programmers. 프렌즈4블록 이런 구체적인 상황이 있는 문제를 좋아하는데 시간은 꽤 오래걸렸습니다.. 그 이유를 생각해보면 다음과 같습니다. 새로운 클래스를 새로 만들어야할지, 여기에 어떤 상태값을 만들어야할지 충분히 고려하지 않고 문제를 푼 바람에 우왕좌앙 했습니다. 그러다보니 이를 담는 자료구조도 몇번 바꾸고, 또 막상 만들어놓고 필요없는 경우도 있었습니다. 좀더 고민하고 문제를 푸는 것이 더 시간 절약에 효과적일 것 같습니다. 블록을 담는 자료구조에 순서를 잘못 담았습니다. 밑에부터 담아야하는데 위로부터 담았네요. List를 여러개 다루면서 각각의 인덱스가 무엇을 의미하는지, 제가 의도하는 인덱스를 정확하게 파악하는데 조금 시간이 걸렸습니다. 이 문제에서 가장 고민되었던 부분은 '동시..
programmers. 캐시 문제를 푸는 조건 중 하나인 LRU를 알면 크게 어렵지 않은 문제입니다. LRU는 사실 운영체제에서 나오는 개념인데요. 이에 대해서 간략하게 설명드려볼게요. 음.. 컴퓨터 내 처리 작업에서 가장 시간 많이 사용하는 작업이 입출력 작업입니다. 그렇기 때문에 그 시간을 줄이고자 데이터를 처리하는 곳과 데이터가 저장된 곳 사이에 캐시라는 저장소를 두어 자주 사용되는 데이터들을 저장해둡니다. 하지만 캐시라는 저장소는 유한한 공간이 아니기 때문에(만약 중간에 있다고 공간을 늘려버리면 결국 데이터가 저장된 곳과 같은 곳이 되어버릴 것입니다) 어떠한 규칙에 의해 새로 보관되는 데이터, 버려지는 데이터가 구분되어야 할 것입니다. LRU는 그러한 규칙 중 하나로 Least Recently U..
트리란? 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져있는 유향 그래프를 의미합니다. 트리는 그래프에 속합니다. 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf node/leaf/terminal node): 자식이 없는 노드 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서 길이(length): 출발 노드에서 도착 노드까지 거치는 ..
