기억하고싶은것들

요즘 대부분의 it 회사의 채용 프로세스에는 코딩 테스트가 포함되어있습니다.

그렇기 때문에 이직을 준비한다면 기본적으로 알고리즘 문제를 푸는 연습을 해야 합니다.

짧은 시간에 효과적으로 알고리즘 문제를 푸는 학습을 하고 싶다면

돈을 투자해서 알고리즘 관련된 강의를 보는 것도 좋은 방법입니다.

저 같은 경우에는 유료 강의를 수강하지는 않고

알고리즘 문제들을 제공해주는 사이트에 다양한 문제를 풀고

이론적으로는 유튜브에 영상을 참고하였습니다.

제가 참고한 내역들을 공유 차원에서 정리해 보도록 하겠습니다.

다양한 문제 풀어보기

알고리즘 문제를 풀 수 있는 사이트는 다양합니다.

그중에 유명한 사이트를 몇 개 나열해 보도록 하겠습니다.

링크에 들어가서 맘에 드시는 사이트를 선택하셔서 코딩 테스트 연습을 하면 됩니다.

• https://leetcode.com/problemset/all/
• https://school.programmers.co.kr/learn/challenges
• https://www.acmicpc.net/problemset

대표적인 문제 유형별로 학습

무작정 많은 문제를 푸는 것보다는 전략적으로 특정 유형의 문제들을 몰아서 풀면서

이런 문제는 어떠한 알고리즘 문제에 속한다라는 개념을 익히는 것이 중요하다고 생각합니다.

저는 코딩 테스트 연습을 위한 사이트는 leetcode를 선택하였습니다.

leetcode에는  알고리즘 문제 이외에도 게시판 기능이 존재하여서 해당 게시판에 다양한 글들이 공유됩니다.

그중에 leetcode에서 제공하는 문제들을 알고리즘 유형에 맞게 먼저 풀면 좋은 문제들을 모아놓은 게시글들이 존재합니다.

https://leetcode.com/discuss/general-discussion/665604/Important-and-Useful-links-from-all-over-the-LeetCode

이러한 게시글들을 참고하여서 유형별로 전략적으로 학습하는 것도 좋은 방법이라고 생각합니다.

유용한 유튜브 영상

다음으로는 제가 참고했던 유용한 유튜브 영상들을 공유하도록 하겠습니다.

• https://www.youtube.com/c/NeetCode/playlists
  • leetcode 문제 해법, 접근 방식 등을 알려주는 영상 위주
  • 재생목록을 알고리즘 유형별로 나눠두었음
• https://www.youtube.com/channel/UCHcG02L6TSS-StkSbqVy6Fg/playlists
  • 알고리즘에 대한 개념을 소개하는 영상 존재
  • 개념을 소개한 이후에 관련 알고리즘 유형 문제 해결법 설명

동기부여

이직을 준비하는 과정에서 매일매일 꾸준하게 알고리즘 문제를 푸는 것은 매우 힘든 일입이다.

하지만 문제 유형에 익숙해지고 적응하기 위해서는 반드시 필요한 과정이라고 생각합니다.

이러한 힘든 일을 조금이라도 동기를 부여하기 위해서는 목표를 정하는 것이 좋습니다.

저 같은 경우에는 leetcode에 문제를 풀어서 개인 github에 해당 내용을 커밋하면서

github 계정에 푸시 잔디를 심는 것을 목표로 했었습니다.

제가 달성하는 내용이 눈으로 보이면서, 조금이라도 더 동기 부여가 되었습니다.

또한, leetcode에 문제 푼 내용들을 블로그에 정리하면서 

문제를 풀면서 했던 생각들을 글로 남기는 것도 좋은 방법이라고 생각합니다.

위상 정렬(Topological Sorting)

순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주는 데 사용되는 알고리즘

(일을 하는 순서를 찾는 알고리즘)

DAG( Directed Acyclic Graph ) -방향이 존재하고, 사이클이 존재하지 않는 그래프에서 사용 가능 

방향이 존재하는 그래프에서 사용하므로 

진입 차수를 사용하여 알고리즘을 구현한다.

진입 차수(indegree)

진입 차수(indegree) : 특정한 노드로 들어오는 간선의 개수

위의 그림에서 7 -> 5에서

5의 진입 차수는 1이다

7의 집입 차수는 0이다

위상 정렬 동작 과정

각 노드의 진입 차수를 구한다. 

진입 차수가 0 인 노드를 큐에 넣는다.

큐에 있는 노드의 간선을 제거 

 - ( 해당 간선을 진입 차수로 둔 노드의 진입 차수도 제거 )

 - 제거 과정에 진입 차수가 0이 된 노드는 큐에 추가 

    public boolean topologicalSorting(int numCourses, int[][] prerequisites) {

        List<Integer>[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) { // 노드별 진입차수 계산
            inDegree[pre[0]]++;
            graph[pre[1]].add(pre[0]);
        }
        for (int i = 0; i < inDegree.length; i++) { // 진입차수가 0인 노드 선별
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) { // 큐의 노드 간선 제거 및 진입차수 제거 
            int idx = queue.poll();

            for (int tmp : graph[idx]) {
                inDegree[tmp]--;
                if (inDegree[tmp] == 0) {
                    queue.offer(tmp);
                }
            }
        }

        return Arrays.stream(inDegree).sum() == 0;
    }

관련 문제

https://leetcode.com/problems/course-schedule/

문자열 탐색 알고리즘

Rabin-Karp는 Hashing을 이용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다.

문자열에서 찾고자 하는 패턴의 길이만큼 hash값으로 변환하여, 패턴과 hash값이 같은지 확인을 하며

일치하지 않는 다면 한 칸씩 뒤로 이동하며 비교를 반복한다.

다만, hash값이 같다고 무조건 같은 패턴일 수는 없다.

그렇기 때문에 hash값이 같은 경우에는 문자열에 값과 패턴의 값을 일대일 매칭 하며 비교하는 과정도 필요하다.

기본적인 아이디어는 간단하다. 다만, 문자열을 이동하며 hash값을 계산해야 하는데 이 또한 효율적으로 찾을 수 있다. 

Rolling Hash

sliding window와 같이 문자열을 훑으면서 hash 값을 구하는데 유용하다.

주어진 문자열을 처음부터 끝까지 패턴과 비교하면서 해시값을 구하는데, 중복되는 부분의 해시값은 그대로 두고 업데이트되는 부분만 해시값을 계산해주어서 중복되는 연산을 줄일 수 있다.

위의 그림같은 경우에는 abec의 hash값 dece의 hash값을 구한다고 해보자

두 문자의 공통 부분인 dec는 그대로 두고 변경된 부분만 적용하면 된다.

우선 adec의 hash값은 

97*2^3 + 100*2^2 + 101*2^1 + 99*2^0 = 1477

다음으로 dece의 hash값은 아래와 같이 계산할 수 있다.

(1477 - 97*2^3) * 2 + 101*2^0 = 1503

adec문자에서 a는 제외되었기 때문에 a에 해당하는 값을 빼고 

한 자리씩 앞으로 이동했기 때문에 곱하기 2를 해주고 

마지막에 추가된 문자를 더해주면 된다.

    public List<Integer> find(String parent, String pattern) {

        int parentHash = 0, patternHash = 0, power = 1;

        int parentLen = parent.length();
        int patternLen = pattern.length();

        List<Integer> idxList = new ArrayList<>();

        for (int i = 0; i < parentLen - patternLen; i++) {

            if (i == 0) {
                for (int j = 0; j < patternLen; j++) {
                    parentHash = parentHash + parent.charAt(patternLen - 1 - j) * power;
                    patternHash = patternHash + pattern.charAt(patternLen - 1 - j) * power;

                    if (j < patternLen - 1) {
                        power *= 2;
                    }
                }
            } else {
                parentHash = (parentHash - parent.charAt(i - 1) * power) * 2 
                    + parent.charAt(i + patternLen - 1);
            }

            if (parentHash == patternHash) {
                boolean found = true;

                for (int j = 0; j < patternLen; j++) {
                    if (parent.charAt(i + j) != pattern.charAt(j)) {
                        found = false;
                        break;
                    }
                }

                if (found) {
                    idxList.add(i + 1);
                }
            }
        }

        return idxList;
    }

Tree의 종류 

Tree의 탐색 방법

Tree는 노드와 엣지의 연결관계를 나타낸다.

Root는 가장 상위의 노드를 나타내고, Leaf는 가장 하위의 노드를 나타낸다.

대부분의 알고리즘 문제에서 나오는 Tree는 Binary Tree로 자식이 2개 이하만 존재하는 Tree를 칭한다. 

Binary Tree의 종류

Full Binary Tree

각각의 노드가 Child가 없거나 2개의 Child를 가지는 경우

Complete Binary Tree

왼쪽(Left)에서 부터 가득 차있는 경우

Perfect Binary Tree

모든 노드들이 2개의 Child를 가지고 있고 Leaf의 Level이 모두 같은 경우

Tree의 탐색 종류

PreOrder : N->L->R 

( 가운데 노드가 가장 먼저 나온다 ) 

InOrder : L->N->R

( 가운데 노드가 중간에 나온다 )

PostOrder : L->R->N

( 가운데 노드가 가장 마지막에 나온다 )

Recursive를 이용해 Tree 탐색 구현해보기 ( PreOrder )

	public static void main(String[] args) {
		
		TreeNode n1 = new TreeNode(1);
        
        // ... TreeNode 구성 
        
		System.out.println("PreOrder");
		recursivePreOrder(n1);
	}

	private static void recursivePreOrder(TreeNode n) {
		
		if (Objects.isNull(n)) {
			return;
		}
		
		System.out.print(n.val + " - ");
		
		recursivePreOrder(n.left);
		recursivePreOrder(n.right);
		
	}

Iterative를 이용해 Tree 탐색 구현해보기 ( PreOrder )

	private static void iterativePreOrder(TreeNode n) {
		
		if (Objects.isNull(n)) {
			return;
		}
		
		Stack<TreeNode> stack = new Stack<>();
		stack.push(n);
		
		while (stack.size() > 0) {
			TreeNode tmp = stack.pop();
			System.out.print(tmp.val + " - ");
			
			if(Objects.nonNull(tmp.right)) {
				stack.push(tmp.right);
			}
			
			if(Objects.nonNull(tmp.left)) {
				stack.push(tmp.left);
			}
		}
	}