전체 글657 [Leetcode] 952. Largest Component Size by Common Factor 문제 : https://leetcode.com/problems/largest-component-size-by-common-factor/ 고유한 양의 정수 배열 nums가 주어진다. nums[i], nums[j] (i != j)는 1보다 큰 공약수를 공유할 때서로의 노드는 연결되어있다. 그래프에서 가장 큰 연결 컴포넌트의 크기를 구하라. 동일한 약수를 가지는 노드를 연결해야 한다. -> Union-Find 를 사용하자. nums 배열 중 가장 큰 정수를 구한 뒤 그 크기만큼의 부모 배열을 만든다. nums 배열을 차례대로 탐색(let, num)하면서 1보다 큰 약수를 구해야하므로 2부터 탐색중인 정수의 루트까지(let, i) 2중 for 문으로 탐색한다. 만일 num이 i로 나누어떨어진다면 i와 num/i.. 2021. 11. 23. [Leetcode] 289. Game of Life 문제 : https://leetcode.com/problems/game-of-life/ m x n 2차원 배열이 있다. 배열은 1(live) 혹은 0(dead) 로 채워져 있다. 배열의 다음 상태는 각 셀의 8개의 이웃(수직, 수평, 대각선) 의 생사와 관련이 있다. 살아있는 상태의 셀의 살아있는 이웃 수가 2, 3개라면 다음에도 살아있을 수 있다. 하지만 이웃수가 너무적거나(0, 1) 너무 많으면(3초과) 인구과다로 죽게된다. 죽은 상태의 셀의 살아있는 이웃 수가 3개라면 번식한것처럼 되살아난다. 초기 생사 정보를 담은 배열이 입력으로 주어질 때 다음 상태를 반환하라. m x n 배열을 하나 만들어서 모든 셀을 탐색하며 각 셀의 살아있는 이웃들의 수를 저장한다. 다시한번 입력 배열을 탐색하며 만일 살아.. 2021. 11. 23. [Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal 문제 : https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 이진 트리의 중위 순회, 후위 순회 결과 배열들이 주어졌을 때 이진 트리를 구하라. 루트노드는 후위순회의 가장 뒤에 있는 노드이다. 후위순회 배열에서 루트 노드를 구한 뒤 중위 순회에서 루트노드의 왼쪽에 있는 값들이 왼쪽 자식 노드들, 오른쪽에 있는 값들이 오른쪽 자식 노드들이 된다. 중위 순회, 후위 순회 배열들의 범위를 위와 같은 방법으로 줄여나가며 재귀함수로 서브트리들의 루트노드, 왼쪽 오른쪽 자식 노드들을 구하며 트리를 만들어나간다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorith.. 2021. 11. 21. [Leetcode] 240. Search a 2D Matrix II 문제 : https://leetcode.com/problems/search-a-2d-matrix-ii/ m x n 정수형 배열에서 target 이 존재하는지 유무를 반환하라. 배열은 각 행, 열에서 오름차순 정렬되어 있다. 가장 쉽게 생각할 수 있는건 각 행, 혹은 열마다 차례대로 이분탐색을 돌려서 target 값이 있는지 확인한다. 시간복잡도는 O(N logM) or O(M logN). 각 행, 열에서 오름차순 정렬되어 있다는 특징을 독립적으로 보지 않고 탐색조건에 같이 사용할 수 있을지 생각해보았다. 예제 1번의 배열모습이다. x = 1, y = 1 일 때, matrix[x][y]는 5이다. 이때 matrix[x~][y~] 배열을 한 번 보자. 각 행, 열들은 오름차순 정렬되어있으므로 항상 최상단좌측.. 2021. 11. 20. [Spring] 배치 실행 시 'BATCH_JOB_INSTANCE.PRIMARY' 중복 에러 mysql 서버에 스프링 배치를 위한 테이블을 기존 다른 서버에 있던 테이블들의 create 쿼리를 따와서 해당 쿼리로 테이블들을 생성 후 배치를 실행해봤다. 데이터가 아무것도 없었던 첫 번째 실행의 경우엔 정상적으로 실행되나 두 번째 실행부터 아래와 같은 에러가 발생했다. java.sql.SQLIntegrityConstraintViolationException: Duplicate entry '0' for key 'BATCH_JOB_INSTANCE.PRIMARY' 그래서 생성했던 배치 관련 테이블을 다 삭제하고 스프링에서 제공해주는 쿼리로 테이블을 생성했다. spring batch core 4.3.3 version 기준, schema-mysql.sql 파일에 있는 쿼리이다. (링크) use '데이터베이스.. 2021. 11. 19. [Leetcode] 461. Hamming Distance 문제 : https://leetcode.com/problems/hamming-distance/ Hamming distance 는 두 정수의 서로 다른 비트의 개수이다. 두 개의 정수 x, y가 주어지면 이들의 Hamming distance를 구하라. 서로 다른 비트들을 구하기 위해 x, y를 XOR 연산을 한다. XOR = 입력값이 같으면 0, 다르면 1. 연산 후 2로 나눠가면서 2의 나머지가 1인 경우(탐색중인 자리의 비트가 1인 경우) 정답 + 1을 한다. 시간복잡도는 O(logN) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/461.%20Hamming%20Distance.cpp 2021. 11. 19. 이전 1 ··· 15 16 17 18 19 20 21 ··· 110 다음
