GW LABS

LeetCode에 "Top 100 liked" 리스트에 수록되어 있는 문제이다. DFS 문제로 분류되는데 국내 기준으로는 구현 문제로 분류될 것 같다. 문제 풀이에 엄청난 시간이 들었는데, 그 만큼 구현 문제에 대한 연습과 대비가 안되어 있다는 걸 느꼈다. 알고리즘을 설계하기 전에 재귀적으로 접근하면 풀이가 가능할 것으로 예상하고, 재귀적으로 설계를 해나가면서 어려웠던 점은 문자열의 인덱스를 적절히 잘라주는 계산과 예외에 대한 처리였다. 다음에 이 문제를 복습할 때에는 재귀적 접근 뿐만 아니라 스택을 사용해서 접근하는 방법도 고려해봐야겠다. class Solution: def decodeString(self, s: str) -> str: return self.decode(s) def decode(self..

Palindrome string은 뒤집었을 때에도 같은 순서를 갖고 있는 문자열이다. 우리말로는 '회문'이라고 한다. palindrome을 가지고 다양한 문제를 만들어낼 수 있는데, 문자열 뿐만 아니라 연결리스트 등 다양한 자료구조의 기본지식을 판단할 수 있는 문제이다. 해당 문제는 부분 문자열에서 palindrome을 찾는 문제였다. class Solution: def countSubstrings(self, s: str) -> int: result = 0 for length in range(1, len(s) + 1): idx_start = 0 idx_end = length while idx_end

두번째 포스팅은 대표적인 선형 자료구조인 연결리스트이다. 알고리즘과 자료구조를 공부하면서 장벽이었던 녀석이기도 하다. 구현과 더불어 연결리스트를 알고리즘 문제에서 다룰 때 하지 말아야할 실수를 정리한다. 1. LinkedList (연결리스트) 연결리스트는 자료를 저장하고 포인터를 이용해서 다음 자료를 가르키는 형식으로 구성된 선형 자료구조이다. 처음 연결리스트를 공부할 때 동적배열과 차이점을 파악하지 못했다. 가장 큰 차이점은 바로 메모리에 저장방식에 있다. 배열 혹은 동적배열의 경우 메모리에 자료를 저장할때 순서대로 저장된다. 연결리스트는 현재 메모리에 비어있는 곳에 랜덤하게 저장되고 자료를 접근할 때에는 포인터로만 접근을 한다. 2. 연결리스트를 다룰 때 주의할 점 연결리스트를 다룰 때 주의할 점은 ..

나는 C++와 같은 unmanaged 언어를 실무에서 다뤄볼 수 있는 기회가 지금까지 없었다. 컴퓨터 공학의 기본기를 익히기 위해서 C/C++같은 언어를 꾸준히 수련하는 것이 필요하다고 생각되어 이 포스팅을 시작해보려고 한다. C++로 기본적인 자료구조를 구현해보면서 컴퓨터 공학의 기본기를 수련해보자! 1. ArrayList (동적배열) 오늘의 주제는 동적배열이다. 동적배열은 크기가 가변적으로 늘어나는 배열이다. 초기화한 배열의 크기가 모자르게 되면 현재 배열보다 2배 큰 배열을 할당하고, 기존에 있던 값을 복사한다. 이렇게 배열크기를 조정하면 삽입과 인덱스 접근에서 시간복잡도 O(1)을 보장할 수 있다. 여기서 중요하게 볼 점은 동적배열의 크기가 입력에 비례해서 커진다는 점이다. 그렇기 때문에 입력과 ..

해당 문제는 이진 탐색을 연습할 수 있는 문제였다. 재귀함수를 이용해서 이진 탐색을 구현했지만 한 번에 구현하진 못했다. 탐색 범위를 잘 지정해주는 것이 이진 탐색 구현의 핵심인 것 같다. #include using namespace std; int container[1000000]; int question[100000]; int binarySearch(int startIdx, int endIdx, int target) { if (startIdx > endIdx) return -1; int middle = (startIdx + endIdx) / 2; if (target < container[middle]) { return binarySearch(startIdx, middle - 1, target); } ..

지난 포스팅 Text Summarization (1) - TextRank 알고리즘 지난 포스팅에서는 TextRank 알고리즘을 통해 머신러닝을 사용하지 않고 텍스트를 요약할 수 있는 방법을 알아봤다. 이번 포스팅에서는 딥러닝을 사용해서 문서를 요약하는 방법을 알아볼 것이다. 완전한 이해를 위해서는 방대한 선행지식이 필요하지만, 여기에서는 코드를 실행시켜보면서 어떤 방식으로 동작하는지 흐름을 파악해보자. 선행지식들을 배울 수 있는 곳들은 링크를 통해 남겨두겠다. 1. RNN(Recurrent Neural Network) 순환신경망(Recurrent Neural Network)는 인공신경망의 일종으로, 일렬로 늘어선 데이터, 시퀀스 데이터의 패턴을 학습하기 위해 고안되었다. 일렬로 늘어선 데이터들엔 어떤 것..

문서를 요약하는 작업은 사람에게도 꾀 벅찬 작업이다. 문서의 정보손실을 최소화하면서 텍스트의 길이를 줄여야하기 때문에 우리는 문서를 요약할 때 문서에 없던 단어를 사용하기도하고, 자신만의 문체가 들어가기도 한다. 이런 문서요약 작업을 컴퓨터에게 시킬순 없을까? 시리즈로 문서요약 작업에 대해 알아보자! 1. 문서 요약의 종류 자동으로 문서를 요약할 때 보통 두 가지의 접근방법이 있다. 하나는 추출적 요약(extractive summarization)과 다른 하나는 추상적 요약(abstractive summarization)이다. 추출적 요약의 경우에는 본문에 존재하는 문장 중에서 중요한 문장을 추출하여 문서를 요약하는 기법이다. 추상적 요약은 사람이 문서를 요약하듯이 요약하는 방법이다. 따라서 문서에 없던..

자료구조에 익숙해지기 위해 HackerRank 문제들을 공부중이다. 그 중 미디움 난이도 트리문제를 보면서 재미있었던 문제가 바로 이 문제이다. 허프만 디코딩 문제는 트리를 순회하면서 이진 문자열을 디코딩하는 문제이다. 문제를 접근한 전략은 간단했다. 이진 문자열을 부분으로 자르면서 대응되는 문자가 있는지 없는지 찾아보는 것이다. 부분 문자열의 길이를 늘려가면서 트리를 순회하면 비교적 간단하게 풀이할 수 있는 문제였다. void decode(String s, Node root) { String answer = ""; String target = ""; while (s.length() > 0) { for (int idx = 1; idx