XOR / AND 연산자 문제를 다시 풀어본 후 아침에 어제 밤 대회에 참석하여 풀지 못한 XOR과 관련된 4번 문제를 다시 천천히 풀어보고 많은 생각을 하게 되었다. 특히 가끔 기회가 있을 때마다 고등학생들의 수학을 가르치면서 (초등학생 때 배워야 하는 더하기/곱하기의 교환/결합 법칙을 잘 모르는 학생들에게) 교만하지 않았나 하는 반성도 했다. 내가 짠 코드가 O(N * N)의 속도로 for-loop 의 순환을 돌면서 메모리 초과와 TLE(Time Limit Exceeded)에 걸려서 결국은 대회가 끝나고 다른 사람의 코드들을 분석하면서 나의 실수와 부족한 점들을 찾았다. 어제 대회 직후에는 reduce / xor 과 같은 간단한 함수를 못 찾아서 놓쳤다고 생각했는데, 오늘 아침에서야 reduce 를 ..

이제는 한국 사람들도 많이 알게되었고, 나 역시 자주 참여하는 코딩 대회 사이트로 leetcode 가 있다. 개인적으로는 꽤 초창기에 알게 되었는데 본격적으로 이 사이트들의 코딩 문제를 풀게 된 것은 2020년 가을 부터였다. 사실 Job searching 으로 유명한 linkedin 에서는 이 사이트를 통하여 인터뷰 질문에 대비를 하라고 공식적으로 추천을 하고 있는데, 근래 우연히 한 사이트에서 아래와 같은 기사를 흥미롭게 읽었다. 요약하면, 1) 알고리듬과 자료 구조의 중요성을 알게 된다. 2) 언제나 나보다 많이 알고 있는 사람이 있다는 것을 깨닫는다. 3) 프로그램을 짤 때 edge-case 에 대한 연습을 할 수 있다. 4) 열심히 하는 것이 재능보다 중요하다는 것을 깨닫는다. 5) 계획을 세우..

어제 저녁 DP(Dynamic Programming) 에 관련된 흥미로운 주제로 세미나를 하고 오늘 아침 강아지 산책하면서.. 조금 더 큰 그림이 이해되었다. 어제 같은 주제에 대해서 나와 나누어 발표를 했던 J가 설명한 부분과 내가 설명한 내용이 완전히 다른 방법이 아니라..DP 문제를 해결하기 위한 Top-down 과 bottom-up 방식의 차이 같다라는 사실이다. 사실 Dynamic Programming 에 관하여 여전히 많은 사람들이 많은 문제들을 중심으로 다양한 연구가 진행되고 있는 것으로 이해하고 있다. 간단한 동전 교환에서 계단 오르는 문제에서 피보나치 순열을 중심으로 시작을 하게 된다. 하지만 실제 알고리듬 문제나 대회에서 나오는 수많은 다양한 문제들을 볼 때마다 상급자와 초급자의 실력의..

Leetcode 의 225회 주간 대회 (Weekly Contest 225, Q2) 2번 문제이다. leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/ 개인적으로 아마추어의 수학 실력을 가지고 소프트웨어 엔지니어로 먹고산 지 20년이 되었다. 20년이 되고 나니.. 알고리듬과 수학의 유사한 부분과 차이.. 그리고 어떻게 하면 알고리듬 실력을 향상 시킬 수 있을 지 이해하는 것 같다. 특히 이러한 문제를 보고... 주어진 제한 시간 내에서 이런 아이디어를 만들어서 코드까지 돌려서 통과할 수 있는 사람은 몇 안된다고 생각한다. 왜냐하면.. 이러한 높은 난이도의 문제를 쉽게 해결하는 많은 고수들의 답안들을 자세히..

이 문제는 214 주간 대회의 2번째 문제이다. 문제의 요구사항 문제의 요구사항은 그다지 좋은 편이 아니고, 설명도 친절하지 않다. 하지만 문제를 푸는 과정에서 필요한 아이디어는 매우 참신한 착안이 필요한 편이다. 하나의 문자열에 있는 알파벳 문자 별로 나타나는 회수 중 같은 회수가 없도록 제거해야 한다. 이때 제거해야하는 문자 수를 최소화 하는 회수를 출력하는 문제이다. 1647. Minimum Deletions to Make Character Frequencies Unique A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return ..

Index 추적 예제 (2) 앞에서 설명한 이진수 계산 절차 방법이 충분히 익숙하지 않을 것이라 생각하여 조금 더 연습을 해보자. 위의 예는 각각 다른 index를 변경한 경우이다. 좌측의 트리에서는 3번 (원래 배열 원소 2번)이 6에서 10으로 바뀐 경우이고, 우측의 트리는 1번 (원래 배열 원소 0번)이 3에서 4로 변경된 경우이다. 첫번째의 예는 3번에서 시작하여 4번을 정확하게 변경하고 8번에서 끝나야 하는 경우(3번 -> 4번 -> 8번)이다. 우측의 두번째 예는 1번 -> 2번 -> 4번 -> 8번으로 변경이 완료되면 된다. 우리가 정확하게 이해를 해야하는 부분은 "(같은 부모 노드에 해당하는 4번 인덱스 아래 각각 분리되어 존재하는) 2번과 3번 인덱스가 어떻게 (동일한) 부모 노드 4번을..