Algorithm

💡 투 포인터가 필요한 이유? 아래와 같은, 1부터 5까지의 수가 담겨있는 배열에서 합이 5인 부분 연속 수열의 개수를 구하는 방법을 생각해봅시다. 투 포인터를 모른다고 가정했을 때, 생각해낼 수 있는 가장 간단한 방법은 반복문을 이용해 하나하나 구하는 건데요, 1부터 차례대로 합을 구해가며 합이 5가 되면 count를 증가시켜주고, 다음으로는 2부터 시작해서 차례대로 합을 구해가며 합이 5가 되면 count를 증가, 이렇게 3, 4, 5 배열이 끝날 때까지 반복하는 겁니다. 이것을 코드로 작성하면 다음과 같습니다. numbers = [1, 2, 3, 4, 5] count = 1 # 부분수열의 합이 5가 되는 경우의 수를 저장하는 변수 for i in range(5): sum = numbers[i] fo..

💡 구간 합 알고리즘이란? 일반적으로 일정 범위의 합을 구하는 시간 복잡도는 O(N)입니다. 한 번 합을 구하는 거야 그냥 하던대로 합을 구하면 되겠지만, 아주 여러번 그 합을 구해야 한다면 시간복잡도가 펑펑펑 늘어나겠죠?? 이런 경우에 시간 복잡도를 줄이기 위해 합 배열을 구현해놓고 인덱스로 접근하여 O(1)의 시간복잡도로 빠르게 합을 구하는 것이 바로 구간 합 알고리즘입니다. 💡 합 배열 정의하기 합 배열을 그림으로 살펴봅시다. 그림에서 알 수 있듯, 합 배열은 i번째까지의 합을 저장해둔 배열입니다. S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] 입니다. 예를 들어, S[2]는 A[0] + A[1] + A[2] = 15 + 13 + 10 = 38이 되겠죠. 이것..

재귀를 배울 때 빼놓지 않고 꼭 배우는 하노이의 탑. 애기 때 머리 좋아진다고 학교에서 많이 했었는데.. 그땐 나중에 이걸 코드로 구현하고 있을지 알았을까요?..🙄 암튼 이번 포스팅에서는 하노이의 탑을 파이썬으로 구현해보겠습니다! 🗼 하노이의 탑이란? 사진에서 볼 수 있듯이 세 개의 기둥이 있어요. 첫 번째 기둥에는 크기가 다른 여러개의 원판이 쌓여있고요. 원판은 반경이 큰 순서대로 쌓여있습니다. 이걸 순서가 변하지 않게 세 번째 기둥으로 옮겨주어야 하는 게 바로 하노이의 탑 문제입니다. 하노이의 탑에는 규칙이 있는데요, 한 번에 한 개의 원판만을 다른 기둥으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. (크기 순서여야 한다.) * 한 개의 원판만 있다면 넘 당연하게 ..

Summary) 시간 복잡도가 무엇인지, 시간 복잡도를 고려하여 '좋은' 알고리즘을 짜는 방법은 무엇인지에 대해 알아본다. ⚡ Time Complexity(시간 복잡도)란? 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 파이썬 프로그램에서는 2,000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있습니다. 💡 시간 복잡도를 정의하는 2가지 유형 실제로 시간 복잡도를 정의하는 유형은 다음과 같습니다. (빅-세타 유형도 있지만 생략!!) 빅-오메가 : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법. 이렇게만 봐서는 느낌이 잘 안 오죠? 예시를 통해 알아봐요! i..

문제 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 입출력 예 풀이 1 : 이중 for문 문제를 처음 봤을 때 딱 생각나는 가장 간단하고 쉬운 방법은 이중for문을 돌리는 것이다. 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] 이 경우, 시간 복잡도는 O(n^2). 풀이 2 : enumerate, in 이용 이 문제를 풀면서 처음 enumerate에 대해 알게되었다. enumerate는 인덱스와 원소의 쌍을 돌려..

문제 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표) 또한 무시한다. 입출력 예 입력 paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] 출력 >> "ball" 풀이 re.sub(패턴(정규식), 바꿀 문자열, 문자열, 바꿀 횟수) 바꿀 횟수가 생략이면 찾은 문자열을 모두 치환 정규식에서 ^는 not, \w는 단어 문자를 뜻함. 따라서 re.sub(r'[^\w]', ' ', paragraph) 위의 코드는 단어 문자가 아닌 모든 문자를 공백으로 치환하는 것을 말한다. 문자가 아닌 것을 모두 공백으로 치환한 뒤에는, 공백을 기준으로 spli..

문제 로그를 재정렬하라. 기준은 다음과 같다. 1. 로그의 가장 앞 부분은 식별자다. 2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다. 4. 숫자 로그는 입력 순서대로 한다. 입출력 예시 입력 logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] 출력 >> ['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 8 1 5 1', 'dig2 3 6'] 풀이 문자로 구성된 로그가 숫자로 구성된 로그보다 앞에 온다. 숫자로 구성된 로그는 입력 순서대로 둬야한다. 이 ..

문제 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. 팰린드롬이란 앞뒤가 똑같은 단어나 문장을 말한다. 입출력 예제 1. 입력 "A man, a plan, a canal: Panama" 출력 >> True 2. 입력 "race a car" 출력 >> False 풀이 이 문제에서는 눈에 띄는 조건이 두 개 있다. 1. 대소문자를 구분하지 않는다. 2. 영문자와 숫자만을 대상으로 한다. 예를 들어 입력 예제1에서 공백을 포함한 모든 특수문자를 제거한 상태에서, 소문자형태인 amanaplanacanalpanama를 거꾸로 뒤집은 것과 비교를 해야할 것이다. (대문자로 바꾸어 해도 상관 없다.) 내 풀이는 다음과 같다. 입력받은 문자열을 s라고 할 때, s에..