전체 글65 시간 복잡도를 믿고, 나를 의심하기 알고리즘과 관련된 코딩을 하다보면, 시간 복잡도 O(n), O(n^2) 이런 것들을 고려해 접근하게 된다. 예시로 함께 해보자. 5x5의 격자에서 랜덤한 위치에 광물이 1개씩 놓여 있다 가정해보자. 이때 한번에 1x3의 크기만을 탐색할 수 있다면, 어떤 부분에서 최대의 광물 수를 확인할 수 있을까? 나는 뒤도 돌아보지 않고 2중 for문을 이용해 가능한 모든 직사각형을 탐색할 것이다. 물론 가로로 긴 직사각형만을 가정하자! 코드로 확인해본다면, for i in range(0, 5): for j in range(0, 3): //체크 세로는 위와 같이 j 인덱스는 5 끝까지 체크하지 않을 것이고, 가로로는 직사각형 가로의 길이 즉 길이 3이 벗어나지 않는 시작점인 2까지만 체크를 해볼 것이다. 이렇게 하는 .. 2024. 4. 7. equal의 동작 방식과 최적화 python에서 string 타입의 equal이 어떻게 동작하는지 궁금해 찾아보며 공부한 내용을 기록합니다. 파이썬은 문법은 파이썬을 따르지만, 그 내부 동작 원리는 C언어를 기본으로 합니다. 아래의 링크에서 모든 파이썬 API가 내부적으로는 C언어로 만들어져 있는 것을 확인할 수 있죠 https://github.com/python/cpython GitHub - python/cpython: The Python programming language The Python programming language. Contribute to python/cpython development by creating an account on GitHub. github.com 많고 많은 함수 중 제가 집중해본 함수는 unic.. 2024. 4. 1. [LeetCode] Container With Most Water 문제 https://leetcode.com/problems/container-with-most-water/description/ 해석 height배열에서 2개의 height를 골라 그 안에 가장 많은 양의 물을 저장하고 그 값을 구하는 것이다. 2가지 방법으로 풀어보겠습니다 1. 가장 Naive하게 떠오르는 방법으로는 모든 height의 index를 돌면서 최대값을 갱신하는 것입니다. for i in range(len(height)-1): for j in range(i+1, len(height)): ans = max(ans, min(height[i], height[j])*(j-i)) 이렇게 접근하면 문제는 너무 쉽게 풀리지만, Time Limit에 걸리게 됩니다. height의 길이가 10^5이기 때문이.. 2024. 3. 29. [LeetCode] Find All Duplicates in an Array 문제 https://leetcode.com/problems/find-all-duplicates-in-an-array/description/?envType=daily-question&envId=2024-03-25 파라미터로 주어진 nums에 중복된 수가 있으면 그 수를 찾아 return 하라는 간단한 문제입니다. 해석 3가지 방법으로 풀어보겠습니다. 1. 1 ~ N 까지의 체크할 수 있는 공간을 만들어두기 이 경우엔, 1 ~ N을 리스트로 만들어 1의 값으로 만들어 두고, nums를 돌며 나오는 값을 리스트에서 -1 해준다. arr = [1] * (N+1) for i in nums: arr[i] -= 1 for i in nums: if arr[i] < 0: ans.append(i) return ans 다만.. 2024. 3. 25. 이전 1 2 3 4 ··· 17 다음
