알고리즘 문제를 풀 때에나 혹은 실무에서도 종종 데이터 내에서 순차적으로 대소 비교를 해야하는 경우는 있다.

이런 문제를 풀 때에는 디자인 적으로 단일 값에 대해 스트림 내에서 가장 가까운 최솟값 / 최댓값을 찾는 것 뿐 아니라 전체 데이터에서 그 다음 나오는 가장 가까운 작은값 / 큰값을 찾아야할 때가 있게 된다.

 

가령 다음과 같은 배열이 있다고 해보자.

 

이 때 스트림 내에서 각 배열의 요소들에 대해 다음에 나오는(가장 가까운) 작은 값은 다음과 같이 매핑된다

위의 배열에서는 가장 가까운 작은값이 없다면 -1 이라고 표시했다. 

배열 내에서 단일 요소에 대해서라면 가장 가까운 작은 값을 구하는건 어려운 일이 아니다.

하지만 전체 배열, 실무에서라면 전체 데이터 셋에서 가장 가까운 작은값 / 큰값을 찾는 데에는 시간 복잡도를 생각해야되게 된다.

 

가장 간단히 백트래킹으로 한다면 이는 O(n^2) 의 시간 복잡도로 해결할 수가 있다.

즉, 위의 그림에 색깔별 화살표 모양으로 나타난대로 각 요소별로 배열을 전체 순회하면서 나오는 첫번째 상대값을 찾아 배열에 저장하면 되는 것이다.

 

하지만 늘 그렇듯 O(n^2) 의 알고리즘은 데이터 사이즈가 커질수록 부담스러운 알고리즘이 된다.

 

스택을 이용한다면 이에 대해서 O(n) 의 시간복잡도를 갖는 최적 알고리즘을 설계할 수가 있다.

알고리즘은 다음과 같이 동작한다.

왼쪽에서 오른쪽으로 훑으면서 가장 가까운 작은/큰 값을 찾아야하기 때문에 반대로 오른쪽에서 왼쪽으로 스위핑하는 알고리즘을 설계하고, 각 요소를 스택에 담는다.

각 요소들을 검사하면서 스택에서 조건에 만족하지 않는 요소들은 Pop 해주고, 자기 자신을 Push 해준다.

다음 코드를 참고해본다.

public class Solution {
    private int[] nearestSmallerToRight(int[] nums) {
        // [4,5,2,10,8]
        // [2,2,-1,8,-1]
        int[] solve = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= nums[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                solve[i] = -1;
            } else {
                solve[i] = stack.peek();
            }
            stack.push(nums[i]);
        }
        return solve;
    }
}

이와 같은 알고리즘은 비단 데이터셋 내에서 가장 근사한 작은/큰 값을 찾는 것 뿐 아니라 조건에 맞는 근사값을 찾는 데에도 상당히 유용하게 쓸 수 있는 알고리즘이다.

 

실무에서도 생각 안하고 코딩을 할 뿐 데이터 셋에 따라 성능에 영향을 줄 수 있을만한 포인트이기 때문에 생각해보는 것이 좋다. :) 

특히 코딩 인터뷰를 준비하고 있다면, 국내에는 주로 BFS 나 DFS 와 같은 백트래킹 중심의 알고리즘이 면접에 나오지만, 외국계 기업들에서는 시간 복잡도와 밀접한 코드 설계를 물어보는 경우가 많다.

이 개념 역시 NSR / NSL 알고리즘 형태로 외국에서 알려진 테크닉이기 때문에 머릿 속에 담아두고 꺼내어 쓰면 좋을 것 같드.

 

 

보통 트리의 순회를 구현하게되면, 간단한 재귀함수의 호출 형태로 구현하게 되는데, 이 때 고려해야할 점은 재귀함수의 호출은 Stack 메모리의 희생을 요구한다는 점이다.

즉, 순회만으로도 노드의 갯수가 많아진다면 Stack Overflow 에러가 발생하게 된다.

의외로 Tree 의 Traversal 을 Recursion 이 아닌 Iteratation 로 구현하는데 어려움을 겪을 수 있어 정리해보았다.

 

public class Algorithm {

	/***
    	TreeMap 은 index 를 키값으로하는 Map 의 형식으로 저장된 n-Ary tree
        TreeValues 는 index 에 따라 트리의 Value 를 저장한 리스트
    **/
	public void postOrderTraversal(Map<Integer, List<Integer>> treeMap, List<Integer> treeValues) {
		Stack<Integer> returnStack = new Stack<>();		//순회할 노드들의 인덱스를 저장하는 스택
		Stack<Integer> resultStack = new Stack<>();		//순회하고 나온 Return 값을 저장하는 스택
		returnStack.push(0);					//0번 노드를 루트로 가정하고 루트부터 순회
		while (!returnStack.isEmpty()) {
			int next = returnStack.pop();
			resultStack.push(treeValues.get(next));
			if(treeMap.containsKey(next)) {
				List<Integer> children = treeMap.get(next);
				for(int child : children) {
					returnStack.push(child);
				}
			}
		}
		while (!resultStack.isEmpty()) {
			System.out.println(resultStack.pop());		//후위 순서대로 출력
		}
	}
}

 

귀찮아서 별도의 노드 클래스 없이 Map 과 List 를 활용해 트리 구조를 제공하였으나 ;;

위와 같이하면 저장된 비선형 트리를 재귀구조없이 후위 순회할 수 있다.

 

 

 

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) 의 성능을 가져올 수 있다.

 

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

 

 

 

다익스트라 알고리즘은 IT 개발자로 종사하는 사람이라면 모르는 사람이 없을 정도로 유명하면서도 기본적인 알고리즘이다.

 

이 알고리즘은 교통망이나 통신망과 같이 그래프로 나타내어질 수 있는 자료 구조에서 최단거리를 구할 수 있는 방법을 제시한다. 정확히는 한점으로부터 목적지까지의 최단경로트리를 만듦으로써 최단거리를 구한다.

 

다익스트라 알고리즘은 다음 아이디어에서 기반한다.

 

위와 같은 그림이 있고 간선 위의 숫자가 거리를 나타낸다고 하자.

위의 그림에서 1->4 까지 가는 최단 경로는 어떻게 직관적으로 계산할 수 있을까?

 

우리는 직관적으로 1->4 로 직접 향하는 1->4 경로의 비용(13) 보다 1->2->4 로 가는 경로의 비용(14) 이 더 크고, 1->3->4 로 가는 경로의 비용(12) 이 최적이라는 것을 알 수 있다.

우리가 직관적으로 파악할 수 있는 이 내용은, 바로 각 노드들까지의 경로는 "각경로의 최단거리의 합 중 가장 작은값" 이라는 걸 알 수 있다.

 

즉, A-B-C 로 연결된 리스트가 있을 때, A-C 로 가는 최단 경로는 반드시 A-B와 B-C 의 최단경로를 지나치게 된다는 점이다.

다익스트라 알고리즘은 이를 이용해서 최단경로를 저장하는 배열을 만들고, 노드들간의 최단경로를 계속해서 업데이트해주면서 최종적으로 출발지(src) 에서 목적지(dest) 까지의 최단경로를 만들어낸다.

 

다익스트라 알고리즘은 구현에 따라 Naive 하게 접근하는 방법과 Priority Queue 를 이용해 개선한 방법이 있다.

 

Naive 한 알고리즘은 노드의 갯수 N에 대하여 O(N^2) 만큼의 시간 복잡도를 가지며 다음과 같다.

 

	/**
	 * 다익스트라 알고리즘.
	 * @param dist 최단경로 배열
	 * @param n    노드의 갯수
	 * @param src  시작 노드 인덱스
	 * @param dest 도착 노드 인덱스
	 * @return
	 */
	private static int djikstra(int[][] dist, int n, int src, int dest) {
		int[] checkers = new int[n+1];
		int checkCount = 0;
		checkers[src] = 1;
		checkCount++;
		while (checkCount < n) {
			int minIdx = -1;
			int minDist = INF;
			//새로 갱신된 최단경로를 dist 배열에서 새로 읽어온다.
			for(int i=1; i<=n; i++) {
				if(checkers[i] == 0 && dist[src][i] < minDist) {
					minIdx = i;
					minDist = dist[src][i];
				}
			}
			if(minIdx < 0) {
				break;
			}
			checkers[minIdx] = 1;
			checkCount++;
			int nidx = minIdx;
			int ndist = minDist;
			//src에서 가장 가까운 점 nIdx 를 기점으로 최단경로 재갱신
			for (int i = 1; i <= n; i++) {
				if (dist[nidx][i] != INF && ndist + dist[nidx][i] < dist[src][i]) {
					dist[src][i] = ndist + dist[nidx][i];
				}
			}
		}
		return dist[src][dest];
	}

 

위의 소스를 Priority Queue 를 통해 개선한다면 노드의 갯수 N 과 Edge 의 갯수 E 에 대하여 O(E + NlogN) 의 시간 복잡도로 개선할 수 있다.

 

		private static int INF = 1000000000;
	
		private static class Node implements Comparable<Node> {
			int idx;
			int val;
	
			int getIdx() {
				return idx;
			}
	
			int getVal() {
				return val;
			}
	
			Node(int idx, int val) {
				this.idx = idx;
				this.val = val;
			}
	
			@Override
			public int compareTo(Node o) {
				return this.getVal() - o.getVal();
			}
		}
	
		/**
		 * 다익스트라 알고리즘.
		 * @param dist 최단경로 배열
		 * @param n    노드의 갯수
		 * @param src  시작 노드 인덱스
		 * @param dest 도착 노드 인덱스
		 * @return
		 */
		private static int djikstra(int[][] dist, int n, int src, int dest) {
			PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
			for (int i = 1; i <= n; i++) {
				if (src != i && dist[src][i] < INF) {
					priorityQueue.offer(new Node(i, dist[src][i]));
				}
			}
			while (!priorityQueue.isEmpty()) {
				Node next = priorityQueue.poll();
				int nidx = next.getIdx();
				int ndist = next.getVal();
				for (int i = 1; i <= n; i++) {
					if (dist[nidx][i] != INF && ndist + dist[nidx][i] < dist[src][i]) {
						dist[src][i] = ndist + dist[nidx][i];
						priorityQueue.offer(new Node(i, dist[src][i]));
					}
				}
			}
			return dist[src][dest];
		}
	

 

가장 기본적이면서도 중요한 알고리즘의 하나이고, 여러가지 중요한 아이디어들이 알고리즘에 녹아있기 때문에 잘 알아두고 계속해서 연습해보는 것이 필요하다.

 

알고리즘은 다음 링크에서 연습해볼 수 있다.

 

https://www.acmicpc.net/problem/1916

 

 

다음읜 위의 문제에 대한 해답 코드이다.

 

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	private static int INF = 1000000000;

	private static class Node implements Comparable<Node> {
		int idx;
		int val;

		int getIdx() {
			return idx;
		}

		int getVal() {
			return val;
		}

		Node(int idx, int val) {
			this.idx = idx;
			this.val = val;
		}

		@Override
		public int compareTo(Node o) {
			return this.getVal() - o.getVal();
		}
	}

	private static int djikstra(int[][] dist, int n, int src, int dest) {
		PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
		for (int i = 1; i <= n; i++) {
			if (src != i && dist[src][i] < INF) {
				priorityQueue.offer(new Node(i, dist[src][i]));
			}
		}
		while (!priorityQueue.isEmpty()) {
			Node next = priorityQueue.poll();
			int nidx = next.getIdx();
			int ndist = next.getVal();
			for (int i = 1; i <= n; i++) {
				if (dist[nidx][i] != INF && ndist + dist[nidx][i] < dist[src][i]) {
					dist[src][i] = ndist + dist[nidx][i];
					priorityQueue.offer(new Node(i, dist[src][i]));
				}
			}
		}
		return dist[src][dest];
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int[][] dist = new int[1001][1001];
		for (int i = 0; i < 1001; i++) {
			for (int j = 0; j < 1001; j++) {
				dist[i][j] = INF;
			}
		}
		for (int i = 0; i < m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			int d = scanner.nextInt();
			dist[a][b] = Math.min(dist[a][b], d);
		}
		int src = scanner.nextInt();
		int dest = scanner.nextInt();
		System.out.println(djikstra(dist, n, src, dest));
	}
}

 

실무에서 bit 연산을 사용할 때에는 주로 플래그 값들을 미리 정의해놓고 마스킹 하는 용도로 사용하지만,

알고리즘 문제를 풀 때에는 조합을 만들어낼 때에나, check 배열 또는 인덱스 값을 값싸게 저장하기 위한 용도로 많이 사용하게 된다.

 

그래서 자주 사용하지 않으면 헷갈리기 쉬운 bit 연산들을 몇가지 정리해보았다.

 

주로 사용되는 연산은 위와 같고, 해당 연산만 이용해도 비트 연산을 이용한 알고리즘의 상당수는 해결할 수 있다.

 

자주 쓰지않는 내용이라 까먹기 쉽지만, 필요할 때 쓸 수 있도록 잘 익혀두자.

 

 

유클리드 알고리즘은 어렸을적부터 접하는 익숙한 알고리즘이지만, 수학적인 부분이 포함되어 있어 막상 구현하고자 한다면 기억해내기가 쉽지 않다.

 

그 중에서도 알고리즘 문제 해결 시 심심치않게 등장하면서도 중요한 최대공약수(GCD) 와 최소공배수(LCM) 를 구하기 위한 유클리드 알고리즘을 정리해보았다.

 

가장 원시적인(Naive) 방법으로 GCD와 LCM을 구하는 방법으로는, 브루트포스(Bruteforce) 알고리즘이 있다.

 

이는 숫자 목록을 전부 순회하면서 해당 숫자가 주어진 숫자 세트의 최대공약수 / 최소공배수 인지를 판별하는 알고리즘이다.

 

이 방법 자체가 복잡하다거나 한 것은 아니지만, 불필요한 값들의 조회가 많이 일어나는 비효율적인 알고리즘이다.

 

유클리드 알고리즘은 "유클리드 호제법" 이라는 방식을 통해 최대공약수를 구해내고, 이를 바탕으로 최소공배수를 구해낸다.

 

이 원론은 숫자 A와 B에 대하여 A를 B로 나눈 나머지 R에 대해 A와 B의 최대공약수가 B와 R의 최대공약수와 같음을 이용하며, 이 나머지 연산을 나머지가 0이 될때까지 반복함으로써 최대공약수를 구해낸다.

 

최소공배수를 구하는 데 있어서는 다음 성질을 이용한다.

 

A와 B의 최대공약수 G에 대해서 최소공배수 L = A * B / G 를 만족한다.

 

이를 통해 알고리즘적으로 구현하면 다음과 같이 구해낼 수 있다.

 

 

좀 더 자세한 수학적 원리는 다음을 참고하자.

(http://staff.www.ltu.se/~larserik/applmath/chap10en/part3.html)



행렬의 곱셈을 수행할 때에는 특별한 법칙이 있다.


곱하고자 하는 앞 행렬의 Column 수와 뒷 행렬의 Row 수가 일치해야 하며, 계산 결과로 앞 행렬의 Row X 뒷 행렬의 Column 크기를 갖는 행렬 결과가 나타난다.


그렇기 때문에 여러 개의 행렬을 곱할 때, 행렬의 곱셈 순서에 따라 곱셈 연산의 순서가 달라진다. 


앞 행렬의 Column 과 뒷 행렬의 Row 가 넓은 범위에서 공통될 수록 연산의 비용이 커지게 된다.


행렬의 곱셈은 CS에서도 많이 사용되는 연산이기 때문에 이 문제는 알고리즘적으로도 유명한 행렬 곱셈(Matrix Multiplication) 문제이다.


이 문제의 일반적인 솔루션은 DP를 이용한 방식으로 O(n^3) 만큼의 시간복잡도와 O(n^2)의 공간복잡도를 갖는다.


간단하고 직관적이므로 DP를 입문할 때 대표적인 예제로 많이 언급된다.


각각 r[i]개의 행(row)과 c[i]개의 열(column) 을 가진 행렬 n개를 순차적으로 곱셈한다고 가정해보자.


여기서 순차적이라 함은 가령 (AB)C 와 A(BC) 처럼 A, B, C 행렬 3개의 곱의 순서가 보장되어야 한다는 것이다.


이 때 알고리즘은 다음과 같다.


(정의)

dp[i][j] => 행렬i부터 행렬j 까지를 곱할 때 필요한 곱셈의 최소횟수


dp[i][j] = dp[i][k] + dp[k+1][j] + 곱셈 비용 의 최솟값.


간단히 설명하면 구간 i ~ j까지 행렬곱셈을 수행시, i~k 까지의 행렬곱셈 X k+1~j 까지의 행렬곱셈 을 순차적으로 수행하는데 추가로 k~k+1 두 곱셈 결과 행렬의 연산 비용을 추가해주는 것이다.


다음 예제와 해답 코드로 공부해보도록 하자.


예제 : https://www.acmicpc.net/problem/11049 



#include <iostream>
using namespace std;

int n = 0;
int r[501] = { 0, };
int c[501] = { 0, };
int dp[501][501] = { 0, };
int min(int a, int b)
{
    return (a > b) ? b : a;
}

int main()
{
    cin >> n;
    for (int i = 0; i < 501; i++)
    {
        for (int j = 0; j < 501; j++)
        {
            dp[i][j] = 0xfffffff;
        }
    }
    for (int i = 0; i < n; i++){
        cin >> r[i] >> c[i];
        dp[i][i] = 0;
    }
    int cnt = 0;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j+i < n; j++)
        {
            for (int k = 1; j + k < n; k++)
            {
                int left = dp[j][j + k - 1];
                int down = dp[j + k][j + i];
//곱셈 결과
                int val = (c[j + k - 1] == r[j + k]) ? r[j] * c[j + k - 1] * c[j + i] : 0xfffffff;
                dp[j][j + i] = min(dp[j][j + i], left + down + val);
            }
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}



Matrix Multiplication 알고리즘은 Strassen Algorithm 을 통해 O(n^2)에 가깝게 튜닝이 가능하다. 

다소 수학적인 이해가 필요하므로 다음 링크를 참조한다.

(https://en.wikipedia.org/wiki/Matrix_multiplication)



알고리즘을 구현하다보면 2차원 배열에서 분할 탐색을 적용하고 싶을 때가 있다.


특히 알고리즘 문제를 풀 때 이런 경우를 종종 마주치게 되는데, 구현에 익숙하지 않다면 상당히 당황스럽다.


2차원 배열에서 Binary Search 를 적용하기 위해선 몇가지 방법이 있는데, 가장 간단한 방법은 2차원을 1차원으로 축소시켜서 Binary Search 를 적용하는 방법이다.


m개의 행과 n개의 열을 가진 2차원 Matrix 가 있다고 가정해보자.


이를 1차원으로 이해한다면 0~m*n 까지의 Element 가 포함되어 있다고 이해할 수 있다.


그리고 행과 열의 정보는 n 으로 나눈값과 n으로 나눈 나머지를 통해 알 수 있다.


코드를 통해 이해해보자.



public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;

int start = 0;
int end = m*n-1;

while(start<=end) {
int mid = (start+end)/2;
int midX = mid/n;
int midY = mid%n;
if(matrix[midX][midY] == target) {
return true;
}
if(matrix[midX][midY] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}


일반 Binary Search 와 동일한 로직이면서 좌표값만 변경하면서 똑같이 구현한 내용이다.


이진탐색 및 분할정복이 익숙하지 않다면 익혀두고 사용하는 것도 괜찮은 방법이다.



Counting Sort 는 O(n+k) 의 시간 복잡도와 O(n+k) 의 공간복잡도를 이용해서 정렬을 할 수 있는 알고리즘이다. 여기서 k는 가장 큰 키 값을 나타낸다.

일반적으로 "비교 기반" 의 정렬 알고리즘은 O(n log N) 이 가장 효율적인 알고리즘인 것이 수학적으로 증명되었으나, 

Counting Sort 는 비슷한 종류의 Radix Sort 와 마찬가지로 비교 기반의 알고리즘이 아니기 때문에 정렬에 있어 O(n) 의 시간 복잡도를 가질 수 있다.


단, Counting sort 는 비교 기반의 정렬 알고리즘이 아니기 때문에 다소 제약 사항이 존재한다.


Counting sort 는 간단하게 설명해서는 구별되는 키(Distinct Key) 와 해당 키를 Counting 함으로써 이루어지기 때문에, 해당 키값(일반적으로 정수)을 저장할 수 있을 만큼의 Hash table 을 요한다.


말이 Hash table 이지, 키 값을 구별할 수 있는 index table 을 counting array 형태로 사용해도 무방하다.


아래는 Counting sort에 대한 간단한 로직과 구현이다.



(1) Element 의 빈도수(Frequency)를 카운팅(Count)한다.


(2) 카운팅한 빈도수들을 누적합 형태로 정리한다.


(3) Input array 를 순회하며 해당 요소들의 카운트를 차감시키면서 Index 에 배치한다.



    public static int[] countingSort(int[] arr, int noMax) {
        int n = arr.length;
        int[] counts = new int[noMax + 1];
        int[] results = new int[n];
        for (int i = 0; i < n; i++) {
            counts[arr[i]]++;
        }
        for (int i = 1; i <= noMax; i++) {
            counts[i] += counts[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            results[counts[arr[i]] - 1] = arr[i];
            --counts[arr[i]];
        }
        return results;
    }



Counting Sort 는 위와 같이 Element 의 크기에 영향을 받으며, 만약 정렬하고자 하는 요소들 간에 데이터 간격이 Sparse 하다면 불필요한 메모리 사용을 야기한다.


만약 n이 작은 상황이지만 k값이 크다면 당연히 일반 비교 기반 정렬 알고리즘 보다 느리게 된다.


데이터를 잘 분석해서 사용할 만한 경우에 사용하는 것이 필요하다.


+ Recent posts