본문 바로가기
반응형

분류 전체보기565

[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.
[Leetcode] 448. Find All Numbers Disappeared in an Array 문제 : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ nums 배열 크기와 같은 크기의 나온 적 있는 숫자들을 확인하는 bool 형 배열을 하나 만들고 nums 배열을 탐색하며 존재 여부를 세팅한다. bool 형 배열을 다시 한 번 탐색하며 나온적 없는 숫자인 경우 정답 배열에 추가한다. 시간/공간 복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/448.%20Find%20All%20Numbers%20Disappeared%20in%20an%20Array.cpp 2021. 11. 18.
[Leetcode] 668. Kth Smallest Number in Multiplication Table 문제 : https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ m x n 크기의 2차원 배열(1-indexed)이 있다. 배열 값은 각 요소들의 행, 열 인덱스의 곱이다. m, n, k가 주어졌을 때, m x n 2차원 배열에서 k 번째로 작은 요소 값을 구해라. k 번째로 작은 요소 값은 완탐을 하지 않는 이상 구하기 어렵기 때문에, 정수 x 보다 작은 요소 값들이 몇 개인지 구해보자. m = 3, n = 3, k = 4을 예로 들어보자. 1 2 3 2 4 6 3 6 9 1 2 2 3 3 4 6 6 9 구하고자 하는 문제를 좀 더 분해해서 각 행에서 정수 x 보다 작은 요소 값들이 몇 개(let, cnt)인지를 먼저 구해보.. 2021. 11. 16.
반응형