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..
programmers. 순위 어려운 문제였습니다. 저도 어제 조금 생각하다가 방향이 잘 안잡혀서 답안을 봤는데 더 모르겠더라구요. 그래서 오늘 다시 도전해봤는데 오늘은 이 방법이 맞을지 안 맞을지 모르지만 일단 해보자는 생각으로 도전을 했습니다. 결국 답은 틀렸지만 시도한 가치가 있었습니다. 왜냐하면 마지막에 답을 산출하는 과정만 틀렸을 뿐 그 전에 데이터를 가공하는 과정은 의미가 있었거든요. 그럼 처음에 제가 시도한 방법부터 설명해보겠습니다. 답안에는 '플로이드-워셜'알고리즘으로 푸는 방법으로 풀려있습니다. 하지만 저는 bfs를 n번 도는 방법을 통해 데이터를 가공하였습니다(실제 답안에도 이렇게 2가지로 풀 수 있다고 가이드되어 있습니다). bfs를 n번 도는 이유는 다음과 같습니다. 만..
programmers. 가장 먼 노드 그래프 문제이지만 bfs의 개념을 알면 쉽게 풀 수 있는 문제였습니다. 다만 기초적인 bfs에서 조금 더 나아가 length를 따로 표시해줘야한다는 점에서 좀 더 추가적으로 구현해야 합니다. 왜냐하면 length가 몇이냐에 따라서 answer값이 계속 갱신되어야 하기 때문입니다. 기본적인 아이디어는 bfs로 풀면서 최단 거리를 찾아나갑니다. 그리고 Queue에서 Node(해당 노드의 수, length 상태값을 가짐)를 꺼낼 때 count하고 있는 length의 값과 같으면(같은 길이의 노드일때) answer을 증가시키고, count하고 있는 length가 아니면(더 큰 길이의 노드일때) answer = 1 로 초기화시킵니다. class Solution { public..
