전체 글 (68) 썸네일형 리스트형 [파이썬 알고리즘 인터뷰] 12. 팰린드롬 연결리스트 1. 문제 leetcode 234. palindrome linked list 한방향 연결리스트의 head가 주어지면, 주어진 연결리스트가 팰린드롬(뒤집어도 내용이 변하지 않음)이면 True를 리턴하여라. 주어진 한방향 연결리스트는 다음과 같다. 2. 연결리스트를 배열로 바꾸어 풀기 팰린드롬 여부를 확인하기 위해서는 양쪽에서 탐색을 동시에 진행할 수 있어야한다. 한반향 연결리스트는 양방향 탐색이 어렵기 때문에 연결리스트를 배열로 바꾸어 풀었다. 먼저 연결리스트의 값을 저장할 배열 arr을 만들었다. 그리고 연결리스트가 끝날때까지 head.next로 리스트를 탐색하며 head.val을 arr에 추가했다. 마지막으로는 arr을 뒤집은 arr[::-1]이 arr과 같은지 여부를 리턴한다. 3. 런너를 활용한 풀.. [파이썬 알고리즘 인터뷰] 11. 주식을 사고팔기 가장 좋을 때 https://github.com/onlybooks/algorithm-interview GitHub - onlybooks/algorithm-interview: 95가지 알고리즘 문제 풀이로 완성하는 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트. Contribute to onlybooks/algorithm-interview development by creating an account on GitHub. github.com 1. 문제 leetcode 121. Best time to buy and sell stock prices[i]가 i번째 날의 주식 가격인 배열 prices가 있다. 수익을 최대화시킬 수 있는 두 날짜를 골라 최대 수익을 리턴하여라. 만약 수익을 낼 수 없다면 0을 리턴하라. 2... [파이썬 알고리즘 인터뷰] 10. 자기자신을 제외한 배열의 곱 github.com/onlybooks/algorithm-interview 1. 문제 leetcode 238. Product of Array Except Self 정수형 배열 nums가 입력되면 answer[i]가 nums[i]를 제외한 nums의 모든 원소의 곱이 되는 배열 answer을 리턴하시오. 2. 내 풀이 answer[i + 1] = answer[i] * (nums[i +1]/nums[i])이 성립하는 것을 이용해서 문제를 풀었다. def productExceptSelf(self, nums: List[int]) -> List[int]: results = [] tmp = 1 # 0이 등장할 때 if 0 in nums: results = [0 for i in nums] zero = nums.inde.. [파이썬 알고리즘 인터뷰] 9. 세 수의 합 github.com/onlybooks/algorithm-interview 1. 문제 15. 3Sum nums 배열을 입력받으면 서로 다른 i, j, k에 대해 nums[i] + nums[j] +nums[k] == 0인 [nums[i], nums[j], nums[k]] 배열을 리턴하시오. 다만, 같은 세 수가 여러번 포함되면 안된다. 2. 딕셔너리를 이용한 내 풀이 리트코드 1번 문제 두 수의 합에서 사용했던 딕셔너리를 이용했다. 먼저 입력받은 배열을 숫자를 key, 개수를 value로 하는 딕셔너리를 만들어 저장한다. 그리고 딕셔너리의 모든 key에서 첫번째 수, 두번째 수를 찾는다. 중복을 막기 위해서 사용한 수는 value에서 1을 빼고, 첫번째 수는 두번째 수 이상, 두번째 수는 세번째 수 이상이여.. [파이썬 알고리즘 인터뷰] 8. 배열 파티션1 https://github.com/onlybooks/algorithm-interview 1. 문제 leetcode 561. Array Partition I 2n개의 숫자로 이루어진 정수형 배열 nums를 2개의 원소로 이루어진 n개의 부분 배열로 나눠야한다. 단, 각 배열의 최솟값의 합이 최대가 되도록 한다. 2. 내 풀이 부분 배열의 최솟값들이 커지기 위해서는 같은 부분 배열의 원소 크기가 최대한 비슷해야한다. 이를 위해서는 크기 순서대로 원소들을 묶어 부분 배열을 만들어야 한다. 문제를 풀기 위해 먼저 주어진 배열을 오름차순으로 정렬했다. 그리고 짝수번째에 위치한 숫자가 각 부분배열의 최솟값이기 때문에 해당 숫자들을 모두 더해서 결과를 구했다. def arrayPairSum(self, nums: Li.. [파이썬 알고리즘 인터뷰] 7. 빗물 트래핑 https://github.com/onlybooks/algorithm-interview 1. 문제 leetcode 42. trapping rain water 높이를 입력받아 비온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 2. 스택을 이용한 내 풀이 스택에 높이가 낮아지는 곳의 좌표를 저장하는 방법으로 문제를 풀었다. 먼저 주어진 배열의 왼쪽부터 높이를 확인하면서 높이가 낮아진다면 해당 지점의 좌표, 바닥의 높이를 스택에 저장한다. 그러던 중 높이가 높아지는 지점 a가 있다면 스택에서 a보다 높은 위치의 좌표가 나오기 전까지 좌표를 꺼낸다. 그리고 꺼낸 좌표와 a의 좌표, 바닥의 높이를 이용해 추가되는 물의 양을 계산하고 바닥의 높이를 업데이트 한다. 이 방법의 시간복잡도는 O(n)이고, 평균 실행.. [파이썬 알고리즘 인터뷰] 6. 두 수의 합 https://github.com/onlybooks/algorithm-interview GitHub - onlybooks/algorithm-interview: 95가지 알고리즘 문제 풀이로 완성하는 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트. Contribute to onlybooks/algorithm-interview development by creating an account on GitHub. github.com 1. 문제 leetcode 1. Two Sum 정수형 배열 nums와 정수 target을 입력받아 target을 만들 수 있는 배열의 두 인덱스 값을 리턴하라 2. brute force 가능한 모든 조합을 더해서 target과 일치하는지 확인하는 방법이다. O(n^2)의 시간복잡.. [파이썬 알고리즘 인터뷰] 5. 가장 긴 팰린드롬 부분 문자열 https://github.com/onlybooks/algorithm-interview GitHub - onlybooks/algorithm-interview: 95가지 알고리즘 문제 풀이로 완성하는 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트. Contribute to onlybooks/algorithm-interview development by creating an account on GitHub. github.com 1. 문제 5. Longest Palindromic Substring 가장 긴 팰린드롬 부분 문자열을 출력하라 팰린드롬: 뒤집어도 같은 내용인 것 ex) "aba", "aaaaa" 2. 내 풀이 def longestPalindrome(self, s: str) -> str: for.. 이전 1 ··· 4 5 6 7 8 9 다음
