S E P H ' S

최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a, b의 최소 공통 조상을 찾는 알고리즘이다. 예를 들어 아래의 트리에서 5번과 6번의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS 탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장한다. LCA 를 구하기 위한 a, b 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다. (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모 노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게 되면 엄청 많은 반복을 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 키포인트는 이진 트리를 이해하고 응용할 수 있는지와 트리의 성질을 이용해 답을 도출해나갈 수 있는지 두 가지로 보았다. 트리의 성질을 더욱 잘 이해하고 있어야 하는 이유가 있는 문제였다. 트리를 활용한 기본 문제들은 입력에서 자식 노드의 인덱스들을 parentIdx * 2 (왼쪽 자식 인덱스), parentIdx * 2 + 1 (오른쪽 자식 인덱스) 그대로를 주는 문제들이 대부분이었다. 다시 말하자면 부모 인덱스가 무조건 자식 인덱스보다 작았었다. 하지만 이 문제의 입력값을 보자면 부모 인덱스가 자식 인덱스보다 값이 큰 경우도 확인해볼 수 있다. 그래서 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 제한 사항에 n이 10의 7승까지 주어진다. 문제에 주어진 그대로 풀이를 하면 (10^7) * (10^7)의 2차원 배열이 되기 때문에 메모리 초과, 시간 초과가 난다. 2차원 배열의 행들을 잘라 하나의 1차원 배열로 만들때 left ~ right 까지의 수를 구하는 문제이다. 1차원 배열로 만든다는 구문에서 일정한 규칙을 찾아 그에 해당하는 값들만 뽑아낼 수 있겠다는 생각을 했다. 처음 주목했던 것은 left 값에 따라서 처음 시작하는 값이 변한다는 것이었다. (어차피 left 부터 right값까..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 비트를 다루는데 생소하다면 연습해볼 좋은 문제이다. 문제의 조건이 비트를 다룰줄 알아야만 이해할 수 있는 조건이기 때문이다. 문제의 조건은 x에 대해서 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수이다. 숫자를 2진수로 변환해본다면 짝수는 무조건 뒷자리가 0이다. 따라서 1만 더해준다면 짝수는 조건에 해당하는 수를 금방 찾을 수 있다. 문제는 홀수이다. 홀수일때 조건을 만족하는 수들의 규칙을 찾는것이 어려웠다. x = 15라고 예시로 들어보겠다. 15를 2진수로 변환하면 0111..