본문 바로가기

algorithm64

Leetcode 930.BinarySubarraysWithSum 소스코드 문제 930.BinarySubarraysWithSum 풀이 (brute-force) for loop 2번 돌아서 sum 이 goal 과 일치할 경우 output 을 계산해줬습니다. 시간 복잡도 : O(n²) , 공간 복잡도 : 1 fun numSubarraysWithSum1(nums: IntArray, goal: Int): Int { var output = 0 var sum = 0 for (i in 0 until nums.size) { sum += nums[i] if (sum == goal) { output++ } for (j in i + 1 until nums.size) { sum += nums[j] if (sum == goal) { output++ } } sum = 0 } return out.. 2024. 3. 26.
[Codility] CountSemiPrime 풀이 정리 (Java) source 는 Github 에 있습니다. 문제 문제 풀이 첫번째 풀이 전체적인 concept 은 P 의 최소 값을 구한 후, P~N 까지 SemiPrime 을 구해서 cache 에 저장합니다. cache[P+2] 라는 것은 P+2 까지 위치에서 SemiPrime 이 몇 개인지를 나타내는 것입니다. 예를 들면, P가 4 이고 N 이 10이면, cache[4] = 1 이고, cache[10] = 4 입니다. P, Q 를 순회하면서 cache[Q[i]] - cache[P[i]] 를 구합니다. 이 수식이 의미하는 바는 Q[i] 에서의 SemiPrime 의 개수에서 P[i] SemiPrime 수를 빼서 구하겠다는 것입니다. 주의할 것은 cache[Q[i]] - cache[P[i]] 를 구할 때, P[i] 가 S.. 2022. 6. 9.
[Codility] CountNonDivisible 풀이 정리 (Java) source 는 Github 에 있습니다. 문제 문제 풀이 첫번째 풀이 문제 풀이의 concept 을 array element 끼리 나눌 수 없는지 확인하도록 했습니다. int[] A = new int[] {3,1,2,3,6}; 라면 3/1, 3/2, ... 이런식으로 concept 을 잡았습니다. array element 끼리 나누면서 발생하는 중복 계산은 cache 로 저장해서 중복 계산을 피했습니다. 시간복잡도는 O(n제곱) 이였고, 실행해본 결과 정확도 100%, performance 0% 두번째 풀이 문제 풀이의 concept 은 다음과 같습니다. array 에서 발생하는 숫자 빈도수를 계산해서 메모리에 저장합니다. array 를 순회하면서 1부터 element 까지 약분하도록 했습니다. 이 때.. 2022. 6. 9.
[leetcode] Number of Islands 정리 source 는 Github 에 있습니다. 문제 (Number of Islands) 문제 풀이 연결된 섬들은 1개로 count 합니다. for 문을 2번 돌려서 순회를 하면 연결된 섬에 대해서 찾을 수 없습니다. 전체 grid 를 순회하면서 방문한 곳은 순회하지 않도록 구현해서 처리했습니다. 순회할 때, DFS 를 써서 연결된 것들을 순회하게 했습니다. 순회할 때는 상하좌우로 순회하게 했습니다. source public int numIslands(char[][] grid) { int m = grid.length; int n = grid[0].length; visited = new boolean[m][n]; int count = 0; for (int i = 0 ; i < m ; i++) { for (int.. 2022. 1. 28.

티스토리툴바