Jins' Dev Inside

Binary Search Tree란, 검색과 삽입을 모두 O(logN) 이라는 빠른 시간 내에 수행할 수 있는 매우 효과적인 비선형 자료구조(Non-Linear Data Structure) 이다.

Binary Search Tree 를 구현하는 건 어렵지않지만, 의외로 만들어져있는 트리가 BST 인지 아닌지 판별하는 알고리즘은 애를 먹는 개발자들이 많다.

만들어져있는 트리가 BST 인지 파악하려면 다음을 고려해야 한다.

1. 왼쪽 자식 노드가 루트보다 작고, 오른쪽 자식 노드가 루트보다 큰지

2. 왼쪽 서브트리의 최댓값이 루트보다 작고, 오른쪽 서브트리의 최솟값이 루트보다 작은지

문제에서 정의하는 바의 판별을 위해 간단히 재귀(Recursion) 를 이용해서 문제를 해결할 수 있다.

재귀적으로 트리를 Preorder Search 하면서 lower bound 와 upper bound 를 잡고, 해당 노드의 값이 그 사이에 포함되는 지를 확인해주면 된다.

   private boolean checkValidBST(TreeNode root, long low, long high) {
      if (root.val <= low || root.val >= high) {
         return false;
      }
      boolean result = true;
      if (root.left != null) {
         result &= checkValidBST(root.left, low, Math.min(high, root.val));
      }
      if (root.right != null) {
         result &= checkValidBST(root.right, Math.max(low, root.val), high);
      }
      return result;
   }

   public boolean isValidBST(TreeNode root) {
      if(root == null) {
         return true;
      }
      return checkValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
   }

위의 알고리즘을 통해 O(N) 의 복잡도에 해결해낼 수 있다.

Cache 알고리즘 중에 가장 유명한 알고리즘 중 하나로 LRU 알고리즘 이라는 것이 있다.

LRU 알고리즘이란 Least Recently Used Algorithm 의 약자로, 캐시에서 메모리를 다루기 위해 사용되는 알고리즘이다.

캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.

이를 위해 LRU 알고리즘은 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.

알고리즘의 주요 동작은 다음과 같다.

가장 최근에 사용된 항목은 리스트의 맨 앞에 위치하고 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다.

LRU 알고리즘의 구현은 위의 그림에서도 볼 수 있듯이 Linked List 를 이용한 Queue 로 이루어지고, 접근의 성능 개선을 위해 Map 을 같이 사용한다.

다음 예제코드를 참조하자.

public class LRUCacheImpl {

	private class ListNode {
		private int key;
		private int val;
		private ListNode prev;
		private ListNode next;

		public ListNode(int key, int val) {
			this.key = key;
			this.val = val;
			this.prev = null;
			this.next = null;
		}
	}

	private Map<Integer, ListNode> nodeMap;
	private int capacity;
	private ListNode head;
	private ListNode tail;

	public LRUCacheImpl(int capacity) {
		this.nodeMap = new HashMap<>();
		this.capacity = capacity;
		head = new ListNode(0, 0);
		tail = new ListNode(0, 0);
		head.next = tail;
		tail.prev = head;
	}

	private void remove(ListNode node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
		nodeMap.remove(node.key);
	}

	private void insertToHead(ListNode node) {
		this.head.next.prev = node;
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next = node;
		nodeMap.put(node.key, node);
	}

	public int get(int key) {
		if (!nodeMap.containsKey(key)) {
			return -1;
		}
		ListNode node = nodeMap.get(key);
		remove(node);
		insertToHead(node);
		return node.val;
	}

	public void put(int key, int value) {
		ListNode newNode = new ListNode(key, value);
		if (nodeMap.containsKey(key)) {
			ListNode oldNode = nodeMap.get(key);
			remove(oldNode);
		} else {
			if (nodeMap.size() >= capacity) {
				ListNode tailNode = tail.prev;
				remove(tailNode);
			}
		}
		insertToHead(newNode);
	}
}

여기서 테크닉적으로 중요한 부분은, Linked List 처리의 효율성과 코딩상의 이점을 위해 Head 와 Tail 을 단순히 포인터로만 둔 상태에서 중간에 노드들을 배치시키는 더블 링크드리스트 형태를 취한다는 점이다.

즉, Head 가 가리키는 head.next 값이 실제 리스트의 첫 원소가 되고, Tail 이 가리키는 Tail.prev 값이 실제 리스트의 마지막 원소가 된다.

이렇게 Linked List 와 Map 을 이용해서 구현 시, Get 연산에 O(1), Put 연산에도 O(1) 의 성능을 가져올 수 있다.

쉬우면서도 효과적인 알고리즘이자 자료구조이므로 잘 익혀두자.

Spring AOP(Aspect Of Control) 란, DI(Dependency Injection), PSA(Portable Service Abstraction) 와 같이 Spring Framework 의 주요 Feature 이다.

AOP 란 공통된 관심사(Aspect)로 구분된 로직을 필요한 위치에 동적으로 삽입할 수 있게 해주는 기술로,

Advice, JoinPoint, PointCut, Advisor 등의 용어가 사용되며, 비즈니스 로직과 연계되어 공통적으로 사용하는 부분(Transaction 이나 Filter, Security 등의 Layer)을 코드를 특정시점에 코드에 삽입하는 기술이다.

이러한 핵심 로직 코드에의 적용을 Weaving 이라 하며 Compile 시, Class Loading 시, Runtime 시 AOP의 구현이 가능하다.

다음은 몇가지 AOP 에 사용되는 용어들에 대한 정리이다.

- Aspect : 핵심기능에 부가될 수 있는 모듈을 말한다. 재사용 가능하며 핵심적인 기능에 부가되어 의미를 가질 수 있는 모듈이다.

- Advice : Aspect 에 대한 구현체가 된다. 주로 어느시점에 어떤 동작을 할지가 기술된다.

- Point Cut : 핵심 모듈을 분리할 선이자, 어드바이스를 적용할 시점(Join Point)을 정의하는 모듈이 된다.

- Proxy : 타겟은 프록시를 통해 호출되며 타겟 메서드 실행에 대한 전처리 후처리를 담당해줌과 동시에 AOP 추상화에 있어서 인터페이스를 제공한다.

- Weaving : 핵심 로직 코드에의 적용을 말하며, Aspect 가 적용됨으로써 새로운 Proxy 객체가 생성된다.

- Cross Cut : 공통 로직을 비즈니스 로직에서 추출해내는 것을 Cross Cutting 이라 한다.

하지만 위의 내용들은 사실 용어와 사용하는 기술들에 대한 내용으로 실제 Spring 에서 추구하는 AOP 의 개념 그 자체는 서버의 기능을 비즈니스 기능과 공통 기능으로 나누고, 공통 기능을 코드 밖에서 필요한 시점에 재사용 가능하도록 적용시켜 주겠다는 개념이다.

결국 공통 기능을 따로 분리해서 재사용하겠다는 관점을 말하는 것이다.