절취선 블로그

목표 앞뒤가 똑같은 숫자를 확인해보자 Palindrome 변수 타입에 상관없이 변수를 역전후 초기값과 비교하면된다. 반복문을 사용하여 ex) x =123; int temp => 3 -> 30 + 2 -> 300 + 20 + 1 요런식으로 계산하면 된다. class Solution { public boolean isPalindrome(int x) { if(xnum){ num=num*10+temp%10; temp/=10; } // System.out.println(ans); return ((num==temp) || (num/10)==temp); } } Linked List 문제는 어떻게 접근할까? Linked List 문제의 경우에는 내부 변수가 Integer 타입이며 만일 Integer 범위에서 벗어나는 ..

목표 이건 공부해도 모르겠더라 BackTracking 백트래킹 알고리즘이 모든 경우의 수 brute force와 비슷해서 이해를 못하는 듯 하다. 누가 정리한 백D브 차이 백트래킹 vs DFS 백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법으로, 반드시 DFS만으로 가능하지 않고 BFS등으로도 가능한 기법이다. 즉, 정리를 하자면 백트레킹은 하나의 문제 해결 방법론이고 이러한 백트레킹을 구현하는 방법론 중 하나가 DFS이다. 백트래킹 vs 브루트포스 브루트 포스는 모든 경우의 수를 탐색하는 문제 해결 방법론이다. 이와 달리, 백트래킹은 단계마다 조건을 충족하는지 검사하여 조건을 충족하는 경우에만 계속해서 탐색한다. 즉, 정리를 하자면 브루트포스 모든 가지를 탐색하는..

최대 부분 합 구하기 SSAFY 7기 CT 문제에 출제되었던 문제로 1차원 배열에서 가장 큰 값을 가질 수 있는 연속적인 부분 배열을 찾는 문제에 사용되는 알고리즘이다. 많은 문제들이 시간, 공간 복잡성이 적은 카디안 알고리즘을 적용한 문제풀이를 선호한다. 카디안 알고리즘에서는 시,공간 복잡성이 O(n) 으로 다음과 같이 구현한다. LeetCode 53. Maximum Subarray 문제 링크 public int maxSubArray(int[] nums) { int sum = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++){ sum+= nums[i]; max = Math.max(sum, max); if (sum < 0) sum..

Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미 n개의 정점을 가지는 그래프의 간선의 수 (n-1)로 이루어져 있다. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있으며 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 최소 신장트리 (MST) Spanning Tree 내에서 노드간의 간선의 합이 값이 최소인 트리를 의미한다. MST Algorithm 을 구현하는 방법은 4가지가 존재한다. 크루스칼 알고리즘 위상 정렬 알고리즘 다익스트라 알고리..

Longest Increasing Subsequence(LIS) 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열 문제는 입력 수열의 길이가 n일 때 O(N^2)의 시간에 풀이가 가능하다. 구현 1. 개념 증가 부분 수열을 만들기 위해서는 2중 loop 문(i, j)으로 순회하면서 하나의 i 이전까지 순열중에서 가장 긴 배열을 선택하면 된다. 모든 index를 순회하면서 각 인덱스의 LIS는 다음과 같다. 최종적으로 위 배열에서 LIS 값은 4 이다. Index(i) arr Index(i) arr i=0 {1} i=4 {..