본문 바로가기

📚 Coding Test9

[LeetCode] 704. Binary Search 보호되어 있는 글 입니다. 2022. 8. 15.

[LeetCode] 724. Find Pivot Index pivot 인덱스란 인텍스의 모든 왼쪽 요소의 합과 오른쪽의 모든 요소의 합이 같은 지점의 인덱스 class Solution { func pivotIndex(_ nums: [Int]) -> Int { var rightSum = nums.reduce(0, +) - nums[0] var leftSum = 0 if rightSum == leftSum { return 0 } for index in 1.. 피봇 인덱스 기준 왼쪽 합, 오른 쪽 합을 구해야 하므로 전체 하에서 현재 인덱스 값을 빼줌 if rightSum == leftSum { return 0 } 첫 번째 인덱스에서 왼쪽 합, 오른 쪽 합이 같은 경우 첫 번째 인덱스가 피봇 인덱스 이므로 0을 리턴함 (인덱스 0이 피봇 인덱스) 전체 합 S에서 현재.. 2022. 8. 1.

[LeetCode] 1480 Running Sum of 1d Array 보호되어 있는 글 입니다. 2022. 7. 29.

[leetCode] 13. 3Sum (알고리즘, 원리) with Swift leetCode submit 통과하면 다른 분들이 짜 놓으신 환상적인 알고리즘 볼 수 있습니다. 제껀 참고와 통과용으로 봐주세요 ㅠㅠ 효율성 갖다버린 코드입니다. 허헣 다른 글에서 얼핏 노가다 코드라고 적힌 걸 봤어요 ㅎㅎ 아마 다른 방법으로 탐색하는 것도 있겠지만 어떻게든 탐색 범위를 줄이는 것이 이 문제에서 time 복잡도를 줄일 수 있는 방법이 아닐까 싶습니다. 👇광고 붙이고 문제랑 예시 올리면 안된다고 들어서 문제는 링크로 대신합니다 👇 https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowl.. 2020. 11. 4.

[프로그래머스] 완주하지 못한 선수 with python (feat. hash) 해시 테이블 Key & Values - 해시 테이블은 value와 key를 가짐 - 딕셔너리와 다른 점은 key가 계산된 숫자 시퀀스 혹은 char - 배열을 사용해서 연속적이지 않은 buckets라고 불리는 구조에 저장 - 각 값의 위치는 해시 함수에 의해 계산 해시 충돌(collisions) 다른 값을 input 했지만 같은 hash값을 가지는 경우(다른 값이라도 같은 해시를 가질 수 있지만 같은 해시 값이라 해서 같은 인스턴스는 아님 -> 단방향) 해시의 장점 중복을 허용하지 않기 때문에 중복되지 않는 데이터 값을 가져야 하는 구조에서 사용할 수 있다. 특히 그 크기가 어떻든 간에 값을 찾는 시간 복잡도가 O(1)이기 때문에 크기가 큰 데이터에서 값을 효과적으로 찾을 수 있다. 딕셔너리를 사용한 이.. 2020. 10. 13.

[leetCode] 152. Maximum Product Subarray 카단 알고리즘의 변형 저번 leetCode에서 풀었던 Maximum Subarray와 비슷한 문제이다. 때문에 기존에 익혔던 카단 알고리즘을 사용하면 되지만 변수가 존재한다. Product는 곱으로서 음수와 음수의 곱은 양수가 되고 양수에 음수를 곱하게 되면 음수가 되기 때문에 이 경우의 수를 대비하여 최대 값을 구해 주어야 한다. 카단 알고리즘은 쉽게 말하면 현재 값으로만 이루어진 어레이와 이전 어레이+현재값으로 이루어진 서브 어레이의 비교라고 할 수 있다. class Solution { func maxProduct(_ nums: [Int]) -> Int { var num = nums var maxP = num[0] var minP = num[0] var answer = num[0] for i in 1.. 2020. 10. 12.

[leetCode] 53. Maximum Subarray with Swift 카단 알고리즘으로 쉽게 구하기 leetCode 53은 모든 원소의 값의 합이 최대값을 가지는 서브 어레이를 구하는 것이 목표입니다. 이때 서브 어레이는 연속성을 가져야 하는데, 이 뜻은 중간 인덱스를 뛰어 넘지 않고 인덱스 순서대로 되어 있는 어레이입니다. 그렇기 때문에 배열에서 최대값들의 조합만을 찾아 구하는 것이 아니며 어떤 서브 어레이가 가장 최고의 값을 가지고 있는지 구하는 것이 이 문제에 포인트 입니다. 서브 어레이의 최대값을 구하는 문제에서 많이 언급되는 알고리즘은 Kadane 알고리즘입니다. reference Youtube video here 👇 우선 문제에서 주어진 [-2, 1, -3, 4, -1, 2, 1, -5, 4]를 봅시다. 여기서 첫번째 4를 중점으로 보겠습니다. 현재 인덱스는 3이고 그 인덱스의 값은 4입니다.. 2020. 10. 6.

[LeetCode] 217. Contains Duplicate with Swift 배열에서 반복되는 수 찾기 Contains Duplicate - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 217번 문제는 nums는 int형 숫자의 배열이고 이 배열에서 반복되는 값이 있을 때 true를 반환 그렇지 않은 경우 false를 반환하는 것입니다. 언뜻 보기에 배열의 모든 수를 탐색해야 할 것 같지만 그렇게 하면 시간 효율성 측면에서 낮은 점수를 받을 수 밖에 없습니다. 차근차근 배열에서 중복된 값을 찾기 위해서 어떤 알고리즘과 함수를 써야 할지 알아봅시다. 1. 순수한 .. 2020. 9. 17.

스코빌 지수 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 프로그래머스의 코딩테스트 연습에서 카테고리를 잘 보면 사용해야 하는 자료 구조가 적혀 있다. 이번에 하게 된 것은 힙(Heap) > 더 맵게 이다. 작은 수와 그 다음 작은 수를 사용해서 연산을 하고 다시 리스트에 넣어서 최소값 기준에 대한 조건만 맞추면 되겠다 싶었으나 효율성에서 과감히 아웃당했다. 그렇다면 왜 여기서 '힙'을 제시한 걸까? 스택 구조를 사용하면 안되는 걸까? def solution(scovile, k): answer = 0 w.. 2020. 8. 3.

이전 1 다음

달력

최근글

인기글

최근댓글

전체 방문자

Today :

Yesterday :

티스토리툴바