기억보다 로그를

투포인터를 이용한 문제를 풀어보자. 투포인터를 구현하는 방식에는 여러가지가 있지만, 대개는 시작점과 끝점 또는 왼쪽/오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략을 말한다. 범위를 좁혀가기 위해서는 대체로 배열이 정렬되어 있어야 한다. 투 포인터또한 배열을 순차적으로 접근한다는 점에서 브루트 포스와 비슷한거 아닌가? 라는 생각을 잠깐 했지만, 브루트 포스가 2중 포문으로 타임아웃 땅땅 내려준다면 투포인터는 훨씬 향상된 시간복잡도를 보여준다. 모든 원소에 접근하긴 하지만, On^3 의 브루트포스 결과를 On^2 으로 개선할 수 있는 것이다. 1. Trapping rain water 리트코드의 빗물트래핑 문제로, 파이썬 알고리즘 인터뷰 책을 참고했다. 처음 봤을 때 브루트포스 방식은 쉽게 이해갔지만..

two sum은 많은 사람들이 리트코드를 입문하며 처음 푸는 문제같다. 알고리즘 책에서 이 문제를 다양한 방식으로 풀어보는데, 이 중 내가 알고있으면 좋을 풀이 (==나누면 좋을 지식)을 정리하려 한다. 투포인터 사용에 대한 이야기가 나오는데, 이 문제는 인덱스 값을 리턴하기에 투포인터 자체를 사용하여 풀 수는 없다. (투포인터 관련 문제는 이 포스팅 바로 다음에 이어질 예정이라 만약 투포인터를 사용한 알고리즘 풀이가 궁금하다면 다음 포스팅을 참고해주세요👍) 그래서 1) Brute force로 풀이 2) in 을 사용한 풀이 3) 시간 복잡도를 개선해 속도를 높인 딕셔너리 사용 풀이 4) 3의 코드를 좀 더 간결하게 정리한 풀이 네가지를 공유할까 한다. 문제는 다음과 같다. Given an array o..

출처 https://leetcode.com/problems/number-of-islands/ 문제 Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. 입출력 예시 Input: grid = [ ["1","1","1","1","0"], [..

[Compare the Tripliets] Alice and Bob each created one problem for HackerRank. A reviewer rates the two challenges, awarding points on a scale from 1 to 100 for three categories: problem clarity, originality, and difficulty. .. 문제 상세 : https://www.hackerrank.com/challenges/compare-the-triplets/problem?isFullScreen=true Compare the Triplets | HackerRank Compare the elements in two triplets. www...

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Constraints: m == grid.length n == grid[i].length 1

source: https://leetcode.com/problems/most-common-word/ Q. Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique. The words in paragraph are case-insensitive and the answer should be returned in lowercase. Idea: 문자열을 공백으로 split 하여 새로운 배..

Q. You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier. There are two types of logs: Letter-logs: All words (except the identifier) consist of lowercase English letters. Digit-logs: All words (except the identifier) consist of digits. Reorder these logs so that: The letter-logs come before all digit-logs. The letter-logs are sorte..

Q. A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise. 1. 리턴타입 boolean 2. 회문을 돌면서 모두 체크할 것인지, 정규 표현식을 쓸 것인지 고민할 필요가 있습니다. 만약 회문을 돈다면 .isalnum()(영문자..

배열 뒤집기는 1. sorted(list_name, reverse=True) 2.list_name.reverse / return list_name 3.list_name[::-1] 세가지 방법으로 할 수 있습니다. 1번 정렬은 뒤집으면서 내림차순으로 정렬하기 때문에 순수하게 배열을 뒤집기를 바라면 2,3을 사용해야합니다 def solution(num_list): num_list.reverse() return num_list

Q. 약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요. Source: https://school.programmers.co.kr/learn/courses/30/lessons/120846 처음 직관적으로 생각한 방법은 n에서 소수의 개수를 빼는 것이었다 -> 전체를 순회하기보다 제곱근+1의 값까지 체크하여 소수여부를 판별한뒤 (성능,속도면에서 전체를 체크하는 것보다 제곱근까지만 체크하는 것이 빠르기 때문) -> 전체개수에서 소수의 개수를 빼서 리턴하자 import math def solution(n): isPrime = 0 for i in range (1, int(math.sqrt(n)) ..