TIL) 프로그래밍과 알고리즘

오늘 방통대에서 데이터베이스를 공부하는 와중에 제대로 데이터 베이스에 대해 알고 있는지 확인해보려고 합니다.

학습 목표

• 코틀린을 다루는 기술 ~ 2.3장 정리
• 방통대 알고리즘 교재 정리

정리

프로그래밍의 함정과 안전한 코드 작성법

프로그래밍은 작업의 순서를 정의하는 과정입니다.

회원 정보를 조회하고 업데이트하는 코드는 데이터 조회, 로직 터리, 저장 같은 단계로 나뉘게 됩니다.

하지만 잘못 설계하면 예측 불가능하고 유지보수가 어렵습니다.

상태 변화와 의사결정의 위험

코드는 상태 변화(변수 수정)와 의사결정(조건문)을 포함하게 됩니다.

이런 요소가 많아진다면 코드는 결정적이지 않고 추론이 안됩니다.

• 회원 오브젝트가 처음 조회가 되고 비스니스 로직이 진행되면서 마지막 저장할 때에는 어떤 상태를 가지고 있는지 알 수 없습니다.

상태 변화를 최소화하고, 변수를 수정하는 대신 새로운 오브젝트를 반환하는 방식을 사용하는 것이 좋다

가변 참조와 루프의 함정

가변 변수는 여러 곳에서 바뀔 수 있어서 어디서 변수가 잘못 할당 되었는지 추적이 어렵습니다.

루프는 내부 로직이 노출되서 코드가 길어지게 되면, 중복 코드가 발생되거나 루프 동작에 처음 설계와 다른 방향으로 바뀔 수 있습니다.

불변 객체를 사용하여 기존 오브젝트를 수정하는 게 아닌 새 오브젝트를 반환하는 방법이 있습니다.

스트림 API를 활용하여: 로직을 추상화할 수 있습니다. 내부 동작이 함수 값으로 숨겨지게 되어 반복이나 조건에 대한 로직이 단일 책임을 지게 됩니다.

// 위험한 코드: 가변 리스트와 루프
List<String> names = new ArrayList<>();
for (Member member : memberRepository.findAll()) {
    if (member.getAge() > 18) {
        names.add(member.getName()); // 리스트 수정
    }
}

// 안전한 코드: 스트림과 불변성
List<String> names = memberRepository.findAll()
    .stream()
    .filter(member -> member.getAge() > 18)
    .map(Member::getName)
    .collect(Collectors.toUnmodifiableList()); // 불변 리스트

외부 세계와 상호작용

프로그램이 외부 세계(예 : 데이터베이스, 네트워크 , 파일)와 여러 계층에서 상호작용하면 외부의 불안정성 때문에 버그가 생길 가능성이 큽니다.

서비스 로직이나 컨트롤러 로직이 API를 직접 호출하거나 의존한다면, 문제 사항이 생길경우 외부 문제가 코드 전체에 영향을 끼치게 됩니다.

예외

예외를 던진다는 것은 상위 계층의 조건문과 분기문을 나타낸 형태입니다.

지나치게 사용하면 제어 흐름을 복잡하게 만들고 유지보수가어 어려워집니다.

정말 필요한게 아니라면 예외를 내보내는 최소화하고, 예외를 내보내야하는 상황이라면 명확하게 작성합니다.

부수효과

메서드는 코드 블록에 영역이 있습니다.

영역은 코드 내부에서 외부는 볼수 있으며 수정도 가능하게 됩니다.

메서드 영역에서 외부 영역에 대해 상태 변이가 발생하거나 SRP(단일책임 원칙)이 지켜지지 않는다면 부수효과(사이드 이펙트)가 발생할 확률이 높습니다.

외부 세계의 상호작용 과 나머지를 분리

외부 세계에 접근하고 수정해야하는 영역과 나머지 비즈니스 영역 코드를 분리하여 외부 세계에서 발생할 수 있는 문제를 최소화 해봅니다.

참조 투명성

참조 투명성은 자신의 외부 세계를 수정하지 않고, 반대로 외부 세계가 변경사항이 내부 코드에 영향이 없다는 의미입니다.

그래서 어디서든 실행될 수 있는 자기 완결적이며 결정적입니다. 그리고 예외를 던지지 않습니다.

알고리즘

오늘 알고리즘은 탐색 - 1편이였습니다.

• 순차 탐색
• 이진 탐색
• 이진 탐색 트리
• 2-3-4 트리

순차탐색

배열이나 연결리스트 자료구조에 찾으려는 데이터를 처음부터 찾을 때까지 끝까지 순차적으로 반복하여 조회하는 방식입니다.

1개면 1번, 100개면 100번 , n번이면 n번의 순차적 탐색이 필요합니다

성능은 O(n)이 됩니다.

모든 리스트 형태의 입력에 적용이 가능합니다. 특히 비정렬 데이터 탐색에 적합하며 데이터 크기에 속도가 반비례하므로 데이터가 큰 경우에는 부적합이다.

데이터 삭제시하면 맨 뒷자리인 애를 삭제된 애 자리에 넣는다.

이진탐색

정렬된 배열만 가능하며, 연결 리스트는 구현이 안됩니다.

탐색 방식은 배열의 중간값 인덱스에 저장된 값과 비교합니다. 예를 들어 [1,2,3,4,5] 라고 정렬된 배열이 있습니다.

숫자 4를 찾으려고 한다면 배열 인덱스 0~4 중간 값인 3과 비교하여 크면 오른쪽, 작으면 왼쪽 그리고 다시 인덱스 2~4 사이의 중간값을 비교하는 방식입니다.

성능은 절반씩 줄여가며 조회를 하는 방식이기에 탐색은 O(logN)이며, 초기화는 O(nlogN), 삽입 삭제는 O(n)입니다.

삽입 삭제가 시간이 오래 걸리는 이유는 리스트의 정렬 상태를 유지해야하므로 데이터 크기만큼 데이터 이동이 필요하게 됩니다.

이진탐색트리

이진 트리의 일종으로 각 노드의 왼쪽 서브트리의 모든 값은 노드 값보다 작고, 오른쪽 서브트리의 모든 값은 노듸 값보다 크다.

이진 탐색의 원리를 트리 구조를 적용하여 데이터를 동적으로 삽입, 삭제 , 탐색할 수 있다.

탐색 연산 - 루트 노드로부터 시작해서 값을 비교하면서 좌우 이동한다

삽입 연산 - 삽입할 값을 탐색하고 없으면 해당 위치에 새 노드를 추가한다.

삭제 연산 - 삭제는 자식이 없는 경우, 자식이 하나 인경우, 자식이 두개 인 경우

자식 노드가 없는 경우 그대로 삭제 된다.

자식 노드가 하나인 경우에는 그 자식 노드를 삭제되는 위치로 이동하고, 서브 트리도 따라서 움직인다.

자식 노드가 두개인 경우에는 후속자 노드를 삭제되는 위치로 이동하고, 후속자 노드를 삭제되는 노드로 생각 하여 자식 노드의 개수에 따라 다시 처리한다.

삽입이나 삭제시 기존 노드의 이동이 거의 없다

원소의 삽입/삭제 과정에서 경사 트리 형태가 되면 높이만 높아지는 모습이 나온다

트리의 성능은 트리의 높이와 비례하므로 평균 O(logN) , 경사 트리는 O(N) 이 된다.

2-3-4 트리

2-노드, 3-노드, 4-노드 로 구성된 균형 탐색 트리

이진 탐색트리의 한계인 경사트리를 노드의 개수가 일정 늘어나거나 삭제되면 트리 구조가 변경되면서 트리 높이를 균일하게 만드는 게 목적

그러면 자연스럽게 성능도 최악이 아니라 평균 속도를 유지하는 게 목적인 트리

예를 들어 4노드를 가지면 부모는 3개의 키를 가진다.

먼저 삽입하려는 과정에서 [ 2 , 3 , 4] 에서 노드가 탐색되어 4노드(3키)가 되면 분할로 중앙에 있는 노드가 상위로 간다.

그리고 탐색후 자리에 없으면 해당 위치에 추가되는 방식이다.

성능은 O(logN) 이 나온다. 그런데 실제 구현하면 삽입과 삭제 로직이 복잡하여 이진 탐색보다 더 느려질 수 있다.