[Leet Code] 125. Valid Palindrome(유효한 팰린드롬)

이 글을 보러 들어오신 분들은 문제를 알고 오신 분들이기 때문에 팰린드롬에 대해 추가적인 설명을 하지는 않을게요! 주어진 문자열이 팰린드롬인지 확인하는 문제예요. 다만 주어진 문자열에서 대소문자는 구별하지 않고, 영문자와 숫자만 대상으로 해요. 즉, 특수문자나 공백 문자열 등은 대상에서 제외되겠죠? 📝 풀이 어떤 알고리즘을 사용하든 전처리 작업이 필요할 거예요. 책에서는 이것을 for문을 통해서 처리하거나 정규표현식을 통해 처리하는데 저는 조금 다르게 전 처리했어요. 우선 책에서 한 전처리 방법이에요. # 반복문 사용 strs = [] for char in s: if char.isalnum(): strs.append(char.lower()) # 정규표현식 사용 s = re.sub('[^a-z0-9]', ..
알고리즘 학습/파이썬 알고리즘 인터뷰 2021. 12. 5. 21:36
Swift - 에라토스테네스의 체(sieve of Eratosthenes) for 소수 판별

📎 간단한 소수 판별법 소수 판별에는 여러가지 방법이 있습니다. 사실 가장 간단한 방법은 Brute Force로 2보다 크고 소수 판별의 대상인 수보다 1 작은 모든 수를 탐색하며 나누어 떨어지는지 확인하는 것입니다. 예시를 통해 설명하면 아래와 같습니다. func isPrime(checkNumber: Int) -> Bool { let criterion = checkNumber - 1 for i in 2...criterion { if checkNumber % i == 0 { return false } } return true } 여기서 한단계 더 나아간다면 모든 수를 체크하는 것이 아니라 제곱근까지만 탐색해도 됩니다. 왜냐하면 소수가 아닌 수는 인수가 존재하고, 인수는 곱의 쌍으로 존재하기 때문에 제곱근..
알고리즘 학습/알고리즘 개념 2021. 8. 14. 22:55
[백준 알고리즘] - 명령 프롬프트(1032번) with Python

📎 간략한 문제 정리 파일을 이름으로 검색할 때 하나의 검색어로 여러 파일을 검색해야 할 경우가 있습니다. 결과가 주어지고 이 결과를 얻기위해 입력해야하는 가장 짧은 검색어를 입력하는 문제입니다. 📈 문제 분석 파일 이름들의 길이가 모두 동일하고 정규표현식처럼 압축 표현 등 다양한 옵션이 없이 물음표만으로 표시합니다. 전체 순회를 통해 검색 가능합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 글자 압축의 옵션이 있다면 조금 더 복잡한 문제가 되겠지만 이 경우는 상대적으로 매우 쉬웠습니다. 특정 위치를 관찰할 때 모든 글자에서 같은 알파벳이라면 그 알파벳을 추가하고 아니면 물음표를 추가합니다. 💻 풀이한 코드 from sys import stdin input = stdin.readline N = int(in..
알고리즘 학습/백준 알고리즘 2021. 7. 12. 11:09
[Programmers] - 소수 만들기 (Summer/Winter Coding(~2018)) with Swift

📎 간략한 문제 정리 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구합니다. 📈 문제 분석 문제의 조건이 최대 50개이므로 3가지 요소를 정할 때 3중 for문으로 접근해도 속도 이슈가 발생하지 않습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 3중 for문을 통해 요소 3가지를 선택하고 isPrime 메소드를 통해 소수인지 판별합니다. 소수 판별 시 n-1까지 체크하는 것이 아니라 sqrt(n-1)까지 확인하면 됩니다. 💻 풀이한 코드 import Foundation func solution(_ nums:[Int]) -> Int { var numsSum: [Int] = [] for i in 0 ..< nums.count - 2 { for j in i+1 ..< nums.count -..
알고리즘 학습/with Swift 2021. 6. 22. 23:58
[백준 알고리즘] - 가장 긴 증가하는 부분 수열 2 (12015번) with Python

📎 간략한 문제 정리 주어진 수열에서 요소가 오름차순이 되는 부분 수열 중 가장 길이가 긴 부분 수열의 길이를 구합니다. 📈 문제 분석 DP에서 가장 유명한 문제 중 하나로 일반적으로 DP로 해결합니다. 하지만 이 문제는 DP로 풀 경우 속도 이슈가 발생합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 from sys import stdin input = stdin.readline N = int(input()) A = list(map(int, input().split())) dp = [1 for _ in range(N)] for i in range(1, N): for j in range(i): if A[j] < A[i]: dp[i] = max(dp[j]+1, dp[i]) print(max(dp)) 💻 풀이한..
알고리즘 학습/백준 알고리즘 2021. 6. 16. 22:56
[Programmers] - 불량 사용자 (2019 카카오 개발자 겨울 인턴십) with Python

📎 간략한 문제 정리 입력된 사용자 목록에서 불량 사용자 목록에 등록된 아이디를 제거합니다. 불량 사용자 목록에 있는 아이디는 정확한 아이디가 아니라 *를 사용한 아이디로 *에는 어떠한 문자가 들어가든 다른 문자가 매칭되면 제거합니다. 이렇게 제거 가능한 아이디 조합의 종류를 찾는 문제입니다. 📈 문제 분석 문제가 어렵지 않아 보이지만 보기보다 난이도가 있는 문제입니다. 계속 가능성을 제외하는 좋은 로직을 생각하는 함정에 빠지면 구현에서 문제가 생깁니다. 한번에 모든 문제를 해결하려는 로직을 구현할 수 있다면 이상적이지만 언제나 완전 탐색의 가능성을 배제하면 안됩니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 수학적으로 계산하려고 했습니다. 가능성이 있는 모든 경우를 찾아 교집합 부분을 제거하려고 했는데 이..
알고리즘 학습/프로그래머스 2021. 5. 8. 12:31
[Programmers] - 보석 찾기 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리 전체 배열의 모든 요소를 가진 set이 있을 때, 이 set의 모든 요소를 가진 배열의 부분 배열 중 최소의 길이를 가진 구간을 찾는 문제입니다. 📈 문제 분석 단순히 전체 순회를 하면 속도 이슈가 발생할 수 밖에 없습니다. 범위가 100,000 이므로 O(N^2)이면 바로 속도 이슈가 발생합니다(100번 연산). 아주 단순한 생각으로는 for문을 2차원으로 돌려 i와 j를 정하고, [i:j] 구간에서 모든 요소를 갖는지 검색해보면 되겠지만 이 검색 역시도 cost가 발생하는데다가 검색 자체에서 이미 속도를 넘어서므로 더 효율적인 방법이 필요합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 저는 슬라이딩 윈도우를 생각했고, 이 슬라이딩 윈도우의 크기를 이분탐색을 통해 찾는 방식을 생각했..
알고리즘 학습/프로그래머스 2021. 5. 5. 11:30
[Programmers] - 수식 최대화 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리 기존 사칙연산의 연산자 우선순위가 아니라 임의로 연산자 우선순위를 정해 주어진 expression의 연산을 합니다. 연산 결과의 절대값 중 가장 큰 값을 반환합니다. 📈 문제 분석 이 경우 모든 경우를 탐색하는 Brute-Force(완전 탐색)을 통해 최적의 결과를 찾아냅니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 기존의 제 풀이는 연산자 우선순위대로 탐색하며 연산을 진행하고, 다음 연산자를 검색하며 다음 연산을 진행하는 방식으로 결과를 찾았습니다. 하지만 공부를 위해 이 문제를 새로 풀며 중위 표기를 후위 표기로 바꾸는 과정에 연산자 우선순위가 있음을 기억했고 그 연산자 우선순위 표만 바꾸는 구조로 작성하면 되므로 중위를 후위로 바꾸는 메소드 한개, 후위 연산을 계산하는 메소드 한..
알고리즘 학습/프로그래머스 2021. 5. 4. 21:53
1 2 3 4 5 ··· 22