전체 글 (201) 썸네일형 리스트형 [LeetCode] 754. Reach a Number leetcode.com/problems/reach-a-number/ Reach a Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 이 문제를 전체 탐색을 한다고 생각하면, 2의 지수승이 되므로 전체 탐색은 무조건 TLE를 받는다고 생각하면 된다. 처음 순간에 +1, -1 이후에 +2, -2를 선택하는 과정을 쭉 생각해보면, 탐색해야 하는 노드의 수는 2 * 2 * 2 * 2...가 될 것이다. target만큼 접근하기 위해서, 어떻게.. TSP 외판원 문제 2-Opt, 3-Opt(TSP Problem) 2-Opt 및 TSP 기본 개념 외판원 문제는 NP-Hard 문제로 유명하다, 모든 경로를 확인할 경우 최선의 방법으로 메모이제이션과 비트마스크를 통해서 풀 수 있다. 하지만, 노드의 수가 증가하면 모든 경로를 방문하는 것은 불가능하게 된다. 따라서, 노드의 수가 엄청 많아질 경우에는 정확한 해를 구하는 것이 불가능해진다. 이 경우에 생각할 수 있는 것이, 지역 탐색 알고리즘인 2-Opt이다. 2-Opt를 사용하기전에 출발점에서 모든 노드를 거쳐서 출발점으로 돌아오는 임의의 경로를 구한다. 위의 그림을 떠올려 보자, 연결된 A와 B, C와 D를 잇는 방식을 변경해서 거리가 더 감소된다면, 해당 경로를 선택하는 것이 2-Opt의 기본이다. 2-Opt의 '2'는 2개의 연결된 선분을 변경한다는 의미이다. 이.. [LeetCode] 139. Word Break (Java) leetcode.com/problems/word-break/ Word Break - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 어떤 문자열이, 단어들의 조합으로 만들어졌는지 확인하는 문제다. 문자열을 재귀적으로 함수를 단순하게 호출한다면, 시간초과가 발생한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { HashSet hs = new HashSet(); pu.. [LeetCode] 77. Combinations (Java, 조합) leetcode.com/problems/combinations/ Combinations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 이 문제는 흔히 나오는 조합 문제이다. 지금까지 코드를 작성할 때, 단순히 재귀함수로 코드를 작성하도록 구현했었다. 시간이 20ms가 나와서, 다른 코드들을 참고해봤다. 다른 코드들을 보니, 지금가진 개수와 남은 개수들을 모두 써도 원하는 조합의 길이를 만들지 못한다면 탐색할 필요가 없다는 사실을 이용했다. 이 .. [LeetCode] 43. Multiply Strings(Java, Multiply) leetcode.com/problems/multiply-strings/ Multiply Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 대부분의 수학문제들은 수학적 풀이 사고가 있다면 쉽게 해결할 수 있다. 곱셈을 배웠을 때를 기억해보자. 여러 자리 수의 곱셈을 할 때, 위에 길이가 긴 수를 두고 아래에 길이가 짧은 수를 두고 연산을 시작한다. 아래의 길이가 짧은 수를, 위의 수와 자릿수에 맞게끔 곱셈을 하고, 모든 과정에서 나온 .. [leetcode] 199. Binary Tree Right Side View(Java, BFS) leetcode.com/problems/binary-tree-right-side-view/ Binary Tree Right Side View - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 처음에 문제를 해석하다가, Right Side라고 해서 트리노드의 오른쪽 노드들을 출력하는줄 알았다 ㅠ... 하지만 그게 아니라, 트리를 오른쪽에서 바라봤을때 보이는 노드들을 출력하는 것이다. 즉, 같은 레벨에서 가장 오른쪽에 있는 노드들을 출력하면 된다. 우.. [leetcode] 33. Search in Rotated Sorted Array(Java, LogN, Binary Search) leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 이 문제는 시간 복잡도가 logN이 되도록 문제를 풀어야 한다, 단순 선형 탐색으로 문제를 풀어도 정답은 되지만, 출제의도가 아니다. 우선 피벗을 기준으로, 정렬된 배열들이 섞이게 된다. 중요한 점은, 피벗을 기준으로 각자 정렬을 유지하고 있다는 것.. [HackerRank] Components in a graph(Java, union-find) ## 접근방법 우선 이 문제는 처음 접근 방법으로는 런타임 에러를 받았다. 런타임 에러는 인덱스 초과, 스택 오버 플로우 등의 이유로 발생한다. 스택 오버 플로우에 접근했었던 접근 방법에 대해서 알아보자. 스택 오버 플로우가 발생했던 접근 방법은 노드들을 전체 탐색하는 것이다. 물론 방문했던 노드들을 다시는 방문안하도록 체크하는 배열을 사용해도 스택 오버 플로우가 발생한다. 각 노드들에서 나머지 노드들을 모두 방문할 수 있으므로 시간복잡도는 N * N이 된다. 우선, 스택 오버 플로우가 발생하지 않으려면 함수의 재귀적 호출을 줄이거나 없애야 한다. 함수의 재귀적 호출을 없애는 것으로 문제를 풀어보자. 그래프에서 Union-Find라는 개념은 그래프에서 흔히 사용된다. 두 그래프를 합치고, 각 그래프의 부.. 이전 1 2 3 4 5 6 ··· 26 다음
