본문 바로가기
728x90
반응형

전체 글190

두 수의 합 문제 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. target 을 보고 nums 라는 리스트에 들어있는 원소 중 두 개를 더하여 target 이 될 수 있는 인덱스를 리턴하는 문제이다. 풀이 1) 브루트 포스로 계산. 브루트 포스(Brute-Force) 방식은 이 배열을 2번 반복하면서 즉, for 문을 두 번 돌려서 모든 가능한 두 쌍을 꾸리는 단순한 방식이다. 아래처럼 두번의 for 문 반복으로 인덱스를 출력할 수 있게 쉽게 작성할 수 있다. def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(0,len(nums)-1): for j in range(i+1,len(nums)): ans = nums[i] .. 2021. 4. 4.
가장 긴 팰린드롬 부분 문자열 문제 문제: "가장 긴 팰린드롬 부분 문자열을 출력하라." 팰린드롬 문자는 순서를 거꾸로 읽어도 똑같은 단어였다. 하지만 부분적으로 팰린드롬이 가능한 것들중 가장 긴 것을 찾으라니 머리를 굴리자. 팰린드롬의 작은 예를 살펴보면 한글자는 당연히 가능하고, 그 외에는 'aa' 또는 'aba' 에서 시작해나간다. 즉 두글자 'aa'에서 또는 세글자 'aba' 에서 양쪽으로 한칸씩 동일한지 확인해나가면 된다. 이게 투포인터를 사용해서 풀이가 나와있다. 이 투포인터는 두칸짜리와 세칸짜리로 되어 있고 양쪽 끝에 글자가 동일하면 포인터를 좌우로 하나씩 확장시켜주는 역할을 한다. 중첩함수를 사용한다. expand 가 그것인데 for 문에서 i 가 0 인 경우를 생각해보자. expand 안에 left 와 right에다가 0과.. 2021. 3. 28.
그룹 애너그램 문제 문제는 간단하다. 포함된 알파벳 구성이 동일한 것끼리 리스트로 묶어주면 된다. 어렵지 않은 문제이다. 이 문제가 애너그램 단위로 그룹핑하는 문제이다. 아래의 코드는 정답을 맞추기 위해서 짰던 코드이다. 가장 핵심적인 것만 요약해보면, input 으로 들어오는 strs 속의 모든 단어들에게 정렬 시킨 단어와 pairwise 하게 짝을 지어준다. 그게 아래의 answer 인데 [('abc', 'abc'),('bca', 'abc'), ('cba', 'abc')] 이런식으로 쌍을 만들어주고, answer_d 딕셔너리를 만들고, 원래 단어의 정렬한 것인 key 값을 비교해보면서 동일한 key 값인 경우에는 append 를 시켜주는 식으로 진행하였다. def groupAnagrams(self, strs: List[.. 2021. 3. 28.
가장 흔한 단어 문제 문제는 문자열에 단어 중 금지된 단어를 제외하고 가장 빈도가 높은 단어를 출력하라.! paragraph 을 우선 전처리를 한다. 문자를 제외한 나머지는 공백으로 메꾸는 유용한 코드 한 줄. words = [word for word in re.sub('[^\w]',' ',paragraph).lower().split()] 그리고 banned 금지된 단어에 포함이 되면 안되므로 아래의 코드를 실행한다. 위의 코드의 끝자락에 if 문을 추가해주는 것을 따로 떼어서 적은 것 뿐이다. words2 = [word for word in words if word not in banned] 그리고 collections 모듈의 Counter 함수를 사용한다. 포함된 원소들의 빈도를 알려주는 함수이다. Counter 안에 들.. 2021. 3. 28.
로그파일 재정렬 문제 6장의 문자열 조작 중 로그파일 재정렬이라는 실용적인 문제를 접해보도록 하자. 로그를 재정렬하는 기준은 다음과 같다. 1. 로그의 가장 앞부분은 식별자다. 2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다. 4. 숫자 로그는 입력 순서대로 한다. 예시는 아래와 같다. 코드를 보고 바로 이해를 해보자. 먼저 각 로그들은 숫자로 구성되어 있거나 문자로 구성되어 있으니, 각 로그의 두번째 인덱스에 해당하는 부분이 숫자인지 문자인지를 파악해주는 isdigit() 을 사용한다. 그리고 문자로 구성된 로그와 숫자로 구성된 로그를 나누어 준 후, 문자로 구성된 로그들에 대한 정렬을 시작한다. 이 때 사용된 것이 sort 함수이고,.. 2021. 3. 28.
유효한 펠린드롬 문제 코딩 책을 샀다. "파이썬 알고리즘 인터뷰" 이 책을 시작으로 반드시 기필코 코딩테스트라는 것을 꼭 붙고 말겠다. 책의 6장까지는 기초적인 그리고 개념적인 부분들이 많다. 본격적인 알고리즘에 대한 내용은 7장부터 시작이다. 먼저 6장에서는 문자열 처리에 대한 문제로 첫 스타트를 끊는다. 리트코드의 문제들로 이뤄진 만큼 피드백 받기 좋고, 효율성에 대한 부분을 체크하기 좋아서 추천할만하다. 저자 역시 무료로도 충분히 학습이 가능하다고 하니 책을 끝내고 나서 자유롭게 또 풀어보는 시간이 왔으면 좋겠다. 문제: " 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다." 아래의 예시 처럼 input 이 주어지면 영문자, 숫자를 제외하고 우선적으로 전처리가 필요하다.. 2021. 3. 28.
딥러닝과 추천시스템 딥러닝은 여러개의 은닉층을 쌓아 놓은 다층 신경망 구조라고 개략적으로 볼 수 있다. 여기서 추천시스템에 딥러닝을 적용하려면 다소 까다롭게 느껴진다. 왜냐하면 rating matrix를 자주 보지도 않았을 뿐더러 더군다나 null 값이 상당히 많이 존재하기 때문이다. 그리고 기존의 우리가 딥러닝 input 으로 넣어주는 값은 대게 M x N 이라는 case by fearuse 형태의 독립변수 행렬이었고, loss 값 계산을 위해서는 M x 1 이라는 종속변수 벡터를 사용했기 때문이다. 그래서 추천시스템에서는 앞서 스터디 했던 MF 알고리즘에서 본 것 처럼 user x latent factor, item x latent factor 두 행렬을 input으로 넣는 작업으로 시작한다. 이 방법만 있는 것은 아니.. 2021. 3. 18.
프로그래머스 Lv3 여행경로 DFS, BFS 를 배우고 나서 프로그래머스의 문제를 접하게 되었다. 문제는 아래와 같다. 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방.. 2021. 3. 13.
탐색 알고리즘 BFS(Breath-first search)와 DFS(Depth-first search) 알고리즘 중에서 가능한 모든 데이터를 다 탐색해야 하는 문제를 해결할 때, 효율적으로 탐색하기 위한 알고리즘이 BFS(Breath-first search), DFS(Depth-first search) 이다. BFS는 Breath 가 의미하는 것처럼 넒게 보면서 탐색해나가는 것이고, DFS는 Depth가 의미하는 것처럼 하나를 끝까지 탐색한 후 직전으로 돌아와 다시 끝까지 탐색해 나간다라고 우선 받아들여보자.. 우선 쉬운 예제를 통해서 어떤 것을 하고 싶은건지 알아보도록 하자. 먼저 DFS에 대해서 살펴보자. 기본적으로 주어지는 데이터의 형태는 각양각색이다. 그래서 어떻게 위의 그림처럼 네트워크의 형태로 꾸리는 것이 가장 먼저 할 일이다. 아래의 코드에서 network1, network2 는 위의 그림에서.. 2021. 3. 13.
728x90
반응형

티스토리툴바