코딩개발로 물장구치는 개발자

안녕하세요 Dibrary입니다. Trie 자료구조는 트리 형태의 자료구조인데, '문자열' 검색을 용이하게 하기 위한 자료구조 입니다. 먼저 구글에 Trie python를 검색해보면 여러 이미지들이 나옵니다. 그 중에 한 개를 살펴 보죠. 이게 뭘 의미하는거냐면, to와 tea와 ten이라는 단어는 똑같이 t로 시작하죠? 그래서 t라는 노드 밑에 위치합니다. to에서 o는 tea와 ten에 없으므로 t 노드 밑에 o가 있음으로써, 해당 경로로 검색을 하게 되면 to가 나오는 것이죠. tea와 ten은 t도 똑같고, e도 똑같습니다. 따라서 t노드 밑에 e노드가 있고, e노드 밑에 a와 n으로 나뉘는 것이죠. 이런식으로 문자열을 저장해두고, 찾을 때는 금방 찾게 만든 자료구조가 Trie 입니다. 파이썬으로 ..

안녕하세요 Dibrary입니다. 이번에는 leetcode의 821번 문제를 정리하겠습니다. c로 주어진 문자를 기준으로 좌우 거리마다 1씩 증가하되, c문자를 또 만나면 좌우가 대칭으로 숫자가 들어가야 합니다. 제일 먼저 든 생각은 이랬습니다. c로 입력된 문자를 뽑아내어서 index를 찾는다. 그 index 주위로 +-를 계산한다. 이렇게 하면 맨 앞부분, 맨 뒷부분은 해결이 되는데, 좌 우가 같은 경우는 도저히 해결이 안 되는 겁니다. 예를 들면, 아래 처럼 한 후에, index에 해당되는 값부터 다음 index까지를 - 해 나갈 생각이었죠, 근데 그러려면 5는 -4를 해야 하고, 4는 -2를 해야하고, 3은 -1을 해야하니까, 규칙성이 없네요? 이래서 이 문제를 풀려고 온갖 방법을 헤메고 다녔답니다..