GW LABS

이 문제를 두 번 풀면서 들었던 생각은 항상 내 접근방식이 규칙을 포착하고, 그 규칙을 코드로 구현하는 방식으로만 전개된다는 점이었다. 사실 입력이 크지 않다면 컴퓨팅 파워를 믿고 모든 경우의 수를 돌려보면 아주 간단한 방식으로 풀 수 있는 문제들이 많다. 항상 이 사실을 머리 속에 깊숙히 자리잡게 하도록 연습해야겠다. import sys if __name__ == "__main__": target = int(sys.stdin.readline()) index = 0 result = 0 for i in range(999999999): if "666" in str(i) : index += 1 if index == target: result = i break print(result)

그래프와 DFS, 위상정렬을 공부해볼 수 있는 아주 좋은 문제였다. 문제의 조건은 어떤 과목을 수강할 때 선수과목을 먼저 듣고 들어야한다. 주어진 강의 목록들을 모두 수강할 수 있다면 True를, 선수과목에 이상이 있어서 모두 수강할 수 없다면 False를 리턴하면 되는 문제이다. 접근방법은 우선 인접리스트 형태의 그래프를 만들고 깊이 우선 탐색을 하면서 위상정렬을 수행하는 것이다. 탐색 함수가 종료될 때마다 현재 위치를 기록하고, 탐색이 끝났다면 기록한 배열을 뒤집어주면 위상정렬이 수행된다. 위상정렬 배열을 보면서 수강목록들을 다시 보면서 이상이 있다면 False를 리턴하면 해결할 수 있다. from collections import deque class Solution: def canFinish(se..

세 번째 C++ 세 번째 포스팅은 해시맵이다. 해시맵은 실무에서도 다양하게 응용되는 친숙한 자료구조이다. 어떤 내부구조를 갖고 있는지 함께 알아보자! 1. Hashmap (해시 맵, 해시 테이블) 해시맵은 키를 통해 어떤 값을 찾기 위한 자료구조이다. 다양한 형태로 응용할 수 있고, 알고리즘 문제 뿐만 아니라 실무에서도 유용하게 사용한다. 해시맵은 읽기, 쓰기, 삭제 모두 평균적으로 O(1)에 수행할 수 있다. 어떻게 이런 시간복잡도가 가능할까? 2. Hasing 해시맵을 이해하기 위해선 먼저 해싱을 알아야한다. 해싱은 해쉬함수를 이용해서 키를 숫자로 변환하는 과정이다. 이렇게 생성된 키는 해쉬맵 내부에 있는 자료구조 방 번호가 된다. 얻어진 방 번호를 통해 값을 저장하고, 찾고, 삭제하면 되는 것이다...

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); } ..