0과 1의 쉼터

LCA, (Lowest Common Ancestor, 최소 공통 조상)

트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다...

재귀 호출(Recursive Call)자기 자신을 호출하는 방식왜 Recursive Call이 필요할까요?미로를 탈출한다고 생각해봅시다. 막다른 길에 도달하면 이전 갈림길로 돌아가 다른 경로를 시도해야 합니다.이처럼 여러 선택지를 모두 시도해야 할 때, 실패한 경우 이전 상태로 되돌아가는(backtracking) 과정이 필요합니다.재귀 호출은 함수가 종료되기 전까지 상태를 유지하므로, 각 단계의 상태를(스택 구조로) 자동으로 기억합니다.💡하나의 선택지가 끝나면 이전 상태로 돌아가 다른 선택지를 시도할 수 있습니다.💡하나의 큰 문제를 여러 작은 문제로 분리하거나, 반복문보다 직관적이고 간결한 코드 작성이 가능합니다. 🔄 동작 원리피보나치 수열을 통해 재귀 호출의 동작 원리를 살펴봅시다.피보나치 수열이..

Java에서 문자열 결합 시 많이 사용하는 + 연산은 직관적이고 간단하지만, 성능 측면에서 적절하지 않은 경우가 있습니다. 이번 글에서는 문자열 결합의 효율적인 방법과 이유에 대해 설명하겠습니다.Java에서의 + 연산Java의 String은 immutable(불변)한 객체입니다. 따라서 String 간의 + 연산은 기존 객체를 수정하지 않고, 새로운 String 객체를 생성하게 됩니다. 이는 다음과 같은 코드에서 성능 문제가 발생할 수 있습니다.// 비효율적인 코드 예시String res = "";for (int i = 0; i  위 코드는 for 문이 실행될 때마다 새로운 String 객체를 생성하여 성능 저하를 유발합니다.  + 연산이 효율적인 경우단일 라인의 +연산에서는 Java 컴파일러가 내부적으..

연습문제 1. 종이컵을 스택에 넣는 동작과 거리가 먼 것은? (4) 종이컵은 가장 먼저 들어간 것이 가장 먼저 나온다. 2. 다음 중 스택의 삽입과 추출에서 사용되는 용어 세 가지를 고르시오. top, push, pop 3. 스택에서 데이터를 (1)은 삽입하는 코드고, (2)는 추출하는 코드다. 모두 top과 관련된 코드다. (1)~(2)를 채우시오. (1) top += 0 (2) top -= 1 4. 스택이 꽉 찼는지 확인하는 함수다. (1)에 적합한 코드는? (2) top == SIZE - 1 5. 스택이 비었는지 체크하는 함수다. (1)에 적합한 코드는? (2) top == -1 6. 스택에서 다음에 나올 데이터를 확인만 하는 함수다. (1)~(2)에 적합한 코드는? (1) return None (..

연습문제 1. 원형 연결 리스트의 특징과 거리가 먼 것을 두가지 고르시오. (4) 마지막 노드의 링크는 비어있다. 2. 그림과 같은 워형 연결 리스트를 만드는 코드의 (1)을 채우시오. (1) node1.link = node1 3. 원형 연결 리스트를 삭제하는 그림이다. 정연 노드를 node2,쯔위 노드를 node3, 사나 노드를 node4라고 했을 때 다음 (1) ~ (3)을 노드 이름으로 채우시오. (1) node2 (2) node3 (3) node3 4. 원형 연결 리스트의 마지막 노드가 참이 되는 조건은? (1) current.link != head 5. 원형 연결 리스트의 첫 번째 노드를 삭제하는 코드다. (1) ~ (3)에 적합한 코드를 다음 중 고르시오. current = head last...

연습 문제 1. (1)과 (2)에 알맞는 용어를 각각 채우시오 (1) 선형 리스트는(은) 배열에 데이터를 차례대로 저장하므로 데이터의 실제 위치 순서로 데이터가 구성된다. (2) 단순 연결 리스트 에서는 데이터를 노드 단위로 삽입/삭제한다. 2. 선형 리스트와 비교한 단순 연결 리스트에 대한 설명이다. 거리가 먼 것은? (3) 중간에 새로운 데이터를 삽입할 때는 비효율적이다. → 앞뒤 노드와 연결만 하면되므로 효율적이다. 3. 노드 구조에서 (a)와 (b)를 무엇이라고 하는지 다음 중에서 고르시오 리스트, 링크, 헤드, 배열, 주소, 번지, 데이터 (a) 데이터 (b) 링크 4. 그림과 같이 노드를 생성하고 연결하는 코드를 차례대로 올바르게 나열한 것은? (2) (c) node1 = Node() (a) ..

연습문제 선형리스트는(은) 데이터를 일정한 순서로 나열한 자료구조로, 입력 순서대로 저장하는 데이터에 적당하다 다음은 선형 리스트에 데이터를 삽입하는 과정이다. 거리가 먼 것은? 맨 앞에 공간을 하나 추가해야 한다. → 맨 뒤에 마지막 위치에 바로 앞 위치의 데이터를 이동시킨다. 삽입할 위치까지 (2)를 반복한다. 삽입할 위치에 데이터를 삽입한다 다음은 선형 리스트에 데이터를 삭제하는 과정이다. 순서대로 나열하시오. 4 → 2 → 3 → 1 맨 마지막 칸을 제거한다. 삭제된 위치의 다음 데이터를 삭제한 위치로 이동시킨다. 마지막 위치까지 (2)를 반복한다. 삭제할 위치의 데이터를 삭제한다. 다음은 선형 리스트에 맨 마지막에 빈칸을 추가하는 코드다. (1) 을 채우시오. katok.append(None)​..

목차 Disjoint Set (서로소 집합, 분리 집합) - Time Complexity 구현 - MakeSet(n) - find(x) - union(x, y) 최적화 - Path Compression - Path Halving - Path Splitting - Union by Rank - Union by Size Disjoint Set (서로소 집합, 분리 집합) 원소들의 모임을 표현하는 자료구조로, 각각의 집합은 공통된 원소가 없다. 주로 서로 다른 원소들이 동일한 집합에 속하는지 여부를 판별하는데 사용된다. Time Complexity 경로 압축과 트리 깊이 제어를 하는 로직이 없다면 선형 구조와 같은 예시에서 하나의 작업이 최대 O(N)이 될 수 있다. 하지만, 최적화를 위한 로직을 적용했다면, ..