![]()
주어진 Linked List가 순환한다면 True, 순환하지 않는다면 False를 반환하는 문제이다.풀이def hasCycle(self, head: Optional[ListNode]) -> bool: if not head or not head.next: return False slow = head fast = head.next while slow != fast: if fast is None or fast.next is None: return False slow = slow.next fast = fast.next.next return Trueslow, fast 포인터를 사용하였다.가장 먼저 head가 없거나 노..
![]()
정렬 알고리즘이란?목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 것을 말한다.주어진 문제를 해결하기 위해 최선의 알고리즘을 선택해야 하는데 그때 고려해야 할 것이 시간복잡도, 공간복잡도이다.시간복잡도는 결과를 도출하는 데 걸리는 시간을 말하며, 공간복잡도는 결과를 도출하는데 필요한 공간의 값이다.즉, 문제를 해결하기 위해 선택해야 할 알고리즘은 적은 시간과 적은 공간을 사용하는 알고리즘이다.빅오(Big O) 표기법과 시간복잡도알고리즘에 대해 공부하다 보면 시간복잡도가 O(n), 혹은 O(n^2)이라는 표시를 본 적이 있을 것이다.위와 같이 표시하는 것을 빅오 표기법이라고 한다.O(n)이 함수는 n만큼의 데이터가 주어졌을 때, "최악"의 경우 n만큼의 리소스를 소모한다자주 나오는 것들은 O(1), ..
![]()
주어진 LinkedList를 뒤집은 후에 반환하는 문제이다.풀이나의 풀이def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None array = [] while head.next: array.append(head.val) head = head.next array.append(head.val) array.reverse() answer = temp = ListNode(0) for i in array: temp.next = ListNode(i) temp = ..
![]()
두 개의 LinkedList가 있는데 이 두 개를 하나로 합쳐서 정렬하는 문제이다.풀이나의 풀이class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1 and not list2: return None elif not list1 or not list2: return list2 or list1 else: answer = temp = ListNode(0) while list1 and list2: ..
![]()
팰린드롬의 LinkedList 버전이다.팰린드롬이 맞다면 True, 아니라면 False를 반환한다.풀이나의 풀이class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: if not head: return True list = [] sample = head while sample: list.append(sample.val) sample = sample.next while len(list) > 1: if list.pop(0) != list.pop(): return..
![]()
주식을 사고팔 때의 최대 수익을 계산하는 문제이다.[7, 1, 5, 3, 6, 4]의 예제에서는 가장 낮은 가격인 1에 사고 높은 가격인 6에 팔면 최대 수익이 5가 된다.이때 판매한 날의 가격 인덱스는 구매한 날의 가격보다 무조건 높아야 하며, 만약 배열의 원소들이 점점 줄어드는 형태의 가격정보라면(ex. [5, 4, 3, 2, 1]) 최대 수익은 0이다.풀이나의 풀이class Solution: def maxProfit(self, prices: List[int]) -> int: buy = prices[0] profit = 0 for price in prices[1:]: if buy > price: buy = pri..
![]()
자기 자신을 제외한 나머지 수들의 곱을 배열로 출력하는 문제이다.[1, 2, 3, 4]가 주어진다면 정답은 [(1을 제외한 2, 3, 4의 곱인 24), (2를 제외한 1, 3, 4의 곱인 12), ...] = [24, 12, 8, 6]이다.풀이나의 풀이 (오답)class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: answer = [] for i in nums: list = nums.copy() list.remove(i) mul = prod(list) // from math import prod : 배열 원소들의 곱 ..
![]()
배열 안의 숫자들 중 페어의 최솟값을 합한 수가 가장 큰 수를 구하는 문제이다.[1, 3, 4, 2] 에서 2개씩 묶었을 때 가장 큰 수가 나오려면 (1, 2), (3, 4) 이고 이 쌍의 최솟값의 합 중 최댓값은 1 + 3 = 4 이다풀이나의 풀이class Solution: def arrayPairSum(self, nums: List[int]) -> int: nums.sort() answer = 0 for i in range(len(nums)//2): answer += nums[i*2] // min을 하지 않는 이유는 이미 정렬된 것이기 때문에 retrun answer일단 배열 안의 숫자를 정렬(오름차순)을 하는 것이 가장 먼..
![]()
높이가 각각 다른 벽에 물이 얼마큼 차있는지 구하는 문제이다.풀이투 포인터 사용투포인터를 사용해서 왼쪽과 오른쪽에서 각각 물을 채우면서 오고, 가장 높은 곳에서 만난다... 라는 사실은 알았지만어떻게 구현을 해야 할지 감이 안 잡혀서 풀이를 참고하였다.class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 water = 0 n = len(height) left, right = 0, n - 1 left_max, right_max = height[left], height[right] while left 먼저 left, right라는 포인터..
![]()
배열 안의 두 수를 더해서 target 숫자를 만들 수 있는 두 수의 인덱스를 반환하는 문제이다.풀이나의 풀이class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j]이중 for 문을 사용하였다.첫 번째 숫자부터 그 뒤에 오는 숫자들을 계속 확인하며 더해서 target 숫자가 되는지 확인하고, target 숫자가 되었다면 return을 하는 ..
![]()
Open Authorization인터넷 사용자들이 비밀번호를 제공하지 않고, 다른 웹사이트 상의 자신들의 정보에 대해 웹사이트나 애플리케이션의 접근 권한을 부여할 수 있는 개방형 표준 방법이다. 이러한 메커니즘은 구글, 네이버, 카카오 등이 사용하고 있으며 타사 애플리케이션 및 웹사이트의 계정에 대한 정보를 공유할 수 있도록 허용해 준다. OAuth 프로토콜웹 서비스를 개발할 때 인증 과정을 구현할 것인가는 가장 중요한 문제이다.인증은 보안에 있어서 가장 핵심적인 문제이며, 잘못하면 사용자의 소중한 개인 정보가 유출될 수 있는 위험도 있기 때문에 개발자는 굉장히 신중히 설계를 해야 한다. 하지만 OAuth는 개발자가 직접 인증 과정을 구현하는 것이 아니기 때문에 개발자의 고민을 덜어주며 인증 구현을 간편..
![]()
애너그램은 일종의 말장난으로 어떻나 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 말한다.예를들면, "eat", "tea", "ate"는 같은 철자를 포함하지만 다 다른 의미를 가지는 단어이다.풀이class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagrams = collections.defaultdict(list) for word in strs: anagrams[''.join(sorted(word))].append(word) return list(anagrams.values())딕셔너리를 사용하여 각 단어들을 분류 및 재배열하는 것..
![]()
문자열로 이루어진 배열을 뒤집는 문제풀이나의 풀이class Soloution: def reverseString(self, s: List[str]) -> None: for i in range(len(s)//2): k = len(s) - 1 s[i], s[k - i] = s[k - i], s[i]맨 앞과 뒤의 값을 바꿔줘야 하기 때문에 range()의 범위를 배열 길이의 절반만큼 선언하였다.(몫을 구하기 위해서 // 를 사용) Java에서는 s[i], s[k - i] = s[k - i], s[i] 과 같은 방법을 쓸 수 없지만, Python은 가능하다.(Java에서는 temp 변수를 이용하여 옮겨주고 옮겨주고 옮겨주고...의 방식을 사용해야 됨)Pyt..
![]()
Palindrome(팰린드롬)이란 어느 한 문자열을 반대로 읽어도 같은 문자열을 말한다.풀이배열로 변환class Solution: def isPalindrome(self, s: str) -> bool: strs = [] for char in s : if char.isalnum(): # isalnum() : 해당 문자열이 영문자, 숫자 여부를 판별하는 함수 strs.append(char.lower()) # 함수를 통과한다면 소문자로 변환하여 strs에 추가 while len(strs) > 1: if strs.pop(0) != strs.pop(): # 0을 지정하면 맨 ..
지금까지는 하루에 하나씩 꾸준히 포스팅을 했었다.처음에는 하루도 빠지지 않는 것을 목표로 공부를 하다 보니까 어떻게든 하루에 하나는 완성하기 위해,내가 이미 알고 있는 내용, 간단하게 공부할 수 있는 내용 등등 쉬운 방법으로 계속 포스팅을 해나갔다. 그러다가 지금 브레이크가 걸렸다.일단 첫 번째 이유는 알바를 끝내고 나에게 남은 시간 동안 공부해야 할 양이 부족하다.시간이 없다는 핑계가 아니라, 새로운 개념을 이해하기에 시간이 짧다는 것이다.이번에 버츄얼쓰레드에 대해서 공부하고 포스팅을 하려고 준비하였다.하지만 출퇴근 길, 알바 중 틈나는 시간 등등 여러 번 공부를 했음에도 월요일에 포스팅하기에는 나의 머리가 아직 제대로 따라와 주지 않았다.그런데 '하루에 하나'라는 목표는 세워놨기에 굉장한 갈등이 생겼..
