Ch 09 Recursion and Dynamic Programming


재귀적 방법

  • 상향식과 하향식으로 나눠 진다.

동적 프로그래밍의 예: 피보나치 수
중간과정을 저장하면 그게 동적 프로그래밍이다.

$n^2$ 복잡도의 일반 코드

int fibonacci(int i){
	if(i==0) return 0;
	if(i==1) return 1;
	return fibonacci(i-1) + fibonacci(i-2);
}

Time complexity를 $O(n)$으로 줄이는 코드

int[] fib = new int[max];
int fibonacci(int i){
	if (i==0) return 0;
	if (i==1) return 1;
	if (fib[i] != 0) return fib[i]; // 캐시된 결과 반환
	fib[i] = fibonacci(i-1) + fibonacci(i-2); // 계산 결과 캐시
	return fib[i];
}

동적 프로그래밍을 구현 할 때의 전략은 다음과 같다.

  • 재귀함수를 먼저 구현
  • 캐쉬 부분을 구현


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch02 LinkedList  (0) 2017.08.11
Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Ch02 LinkedList


2.1 정렬되지 않은 linkedList에서 중복된 값을 삭제하는 코드를 작성 한다.

해법1
set자료 구조에 하나씩 저장하면서 순회하는 방식을 사용한다.
단 한번의 순회로 모두 처리 할 수 있다.
복잡도는 O(n)이다.

def remove_dups(ll):
    if ll.head is None:
        return

    current = ll.head
    seen = set([current.value])
    while current.next:
        if current.next.value in seen:
            current.next = current.next.next
        else:
            seen.add(current.next.value)
            current = current.next

    return ll

실행결과

# 제거 전
1 -> 6 -> 1 -> 4 -> 3 -> 2 -> 4 -> 2 -> 2 -> 5 -> 5 -> 4 -> 2 -> 3 -> 8 -> 6 -> 2 -> 0 -> 1 -> 6 -> 3 -> 6 -> 2 -> 2 -> 6 -> 2 -> 1 -> 6 -> 2 -> 4 -> 2 -> 4 -> 7 -> 8 -> 4 -> 4 -> 3 -> 8 -> 5 -> 5 -> 0 -> 7 -> 7 -> 4 -> 1 -> 1 -> 1 -> 8 -> 5 -> 0 -> 7 -> 5 -> 9 -> 3 -> 0 -> 9 -> 2 -> 0 -> 4 -> 0 -> 0 -> 3 -> 1 -> 3 -> 5 -> 1 -> 0 -> 0 -> 5 -> 9 -> 7 -> 7 -> 0 -> 3 -> 3 -> 1 -> 7 -> 5 -> 5 -> 9 -> 7 -> 4 -> 2 -> 4 -> 6 -> 5 -> 3 -> 2 -> 9 -> 9 -> 8 -> 5 -> 1 -> 7 -> 4 -> 1 -> 8 -> 4 -> 3 -> 9

# 제거 후
1 -> 6 -> 4 -> 3 -> 2 -> 5 -> 8 -> 0 -> 7 -> 9

제약사항

  • temporary buffer를 허용하지 않는다.

해법
버퍼를 사용할 수 없다면 두 개의 포인터를 사용해 순회하여 문제를 해결할 수 있다. current라는 포인터로는 연결 리스트를 순회하고, runner로는 그 뒤에 중복이 있는지 확인 하는 것이다.

하지만 하나의 current node에 대해서 반복을 수행을 계속 해야 하므로 공간 복잡도는 O(1)이 되지만, 시간 복잡도는 O(N^2)이 된다.

def remove_dups_followup(ll):
    if ll.head is None:
        return

    current = ll.head
    while current:
        runner = current
        while runner.next:
            if runner.next.value == current.value:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next

    return ll.head

실행결과

# 제거 전
1 -> 7 -> 8 -> 1 -> 5 -> 7 -> 8 -> 4 -> 9 -> 6 -> 5 -> 9 -> 0 -> 3 -> 8 -> 8 -> 9 -> 3 -> 2 -> 8 -> 7 -> 6 -> 7 -> 9 -> 9 -> 8 -> 5 -> 8 -> 9 -> 5 -> 1 -> 2 -> 6 -> 5 -> 6 -> 9 -> 2 -> 9 -> 2 -> 4 -> 4 -> 0 -> 8 -> 1 -> 5 -> 9 -> 9 -> 5 -> 0 -> 2 -> 9 -> 8 -> 0 -> 6 -> 1 -> 2 -> 1 -> 3 -> 0 -> 7 -> 6 -> 8 -> 1 -> 4 -> 5 -> 0 -> 2 -> 4 -> 9 -> 9 -> 9 -> 5 -> 3 -> 8 -> 0 -> 5 -> 7 -> 2 -> 8 -> 0 -> 3 -> 2 -> 8 -> 0 -> 0 -> 8 -> 2 -> 9 -> 0 -> 5 -> 3 -> 6 -> 8 -> 2 -> 1 -> 7 -> 8 -> 3 -> 7 -> 6

# 제거 후
1 -> 7 -> 8 -> 5 -> 4 -> 9 -> 6 -> 0 -> 3 -> 2

2.2 단방향 Linked List에서 k번째 요소를 찾는 코드를 구현 해야 한다.

해법1
재귀함수를 이용하는 방법

순회하고 매번 index를 저장하기 때문에 O(n)의 복잡도를 가지게 된다. 해당 위치에서 값을 출력하고 index는 return하는 방법으로 구현 했다.

def recursive_kth_to_last(ll, k):
    if ll is None:
        return 0
    i = recursive_kth_to_last(ll.next, k) + 1

    if i is k:
        print(ll.value)
    return i

실행결과

# 생성된 linked list
71 -> 83 -> 3 -> 2 -> 59 -> 25 -> 33 -> 40 -> 21 -> 93

# 뒤에서 3번 째 index라고 하면
40 #

해법2
순환적(iterarive) 방법으로 해결할 수 있다.
직관적이지는 않지만 좀 더 최적인 방법은, 순환적으로 푸는 것이다. 두 개의 포인터 p1과 p2를 사용한다. p1이 리스트 시작 노드를 가리키게 한 다음, p2를 k 노드만큼 움직여서 p1과 p2가 k 노드만큼 떨어져 있도록 만든다. 그런 다음, p1과 p2를 보조를 맞춰 같이 이동시킨다. p2는 LENGTH-k번 후에 연결 리스트의 맨 마지막 노드에 도달할 것이다. 바로 그 시점에, p1은 LENGTH-k번 노드, 그러니까 뒤에서부터 k번째 노드를 가리키게 된다.

코드

def kth_to_last(ll, k):
    runner = current = ll.head
    for i in range(k):
        if runner is None:
            return None
        runner = runner.next

    while runner:
        current = current.next
        runner = runner.next

    return current

실행결과

11 -> 11 -> 83 -> 92 -> 74 -> 2 -> 80 -> 97 -> 76 -> 88
97

2.3 Delete Middle Node

중간 노드를 삭제하는 알고리즘을 구현 한다. 즉 head나 tail을 제외한 아무 노드나 삭제 할 수 있어야 한다.

그렇다고 정확히 middle일 필요도 없다.

example
input: the node c from the linked list a->b->c->d->e->f
result: nothing is returned, but the new linked list looks like a->b->d->e->f

python에서는 쉽게 구현이 가능하다.

def delete_middle_node(node):
    node.value = node.next.value
    node.next = node.next.next

ll = LinkedList()
ll.add_multiple([1, 2, 3, 4])
middle_node = ll.add(5)
ll.add_multiple([7, 8, 9])

print(ll)
delete_middle_node(middle_node)
print(ll)

실행결과

1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9

2.4 x값을 갖는 노드를 기준으로 연결 리스트를 나누는 코드를 작성하라. x 보다 작은 값을 갖는 노드가 x와 같거나 더 큰 값을 갖는 노드들보다 앞쪽에 오도록 하면 된다.

연결리스트를 사용하면 쉽게 해결 된다.
x를 기준으로 작은 값을 저장하는 것과 그렇지 않은것을 저장 하는 것으로 나누면 된다.

index를 1개만 이용해서 앞에서 부터 채우게 하면 좀 더 메모리를 절약할 수 있다.

def partition(ll, x):
    current = ll.tail = ll.head

    while current:
        nextNode = current.next
        current.next = None
        if current.value < x:
            current.next = ll.head
            ll.head = current
        else:
            ll.tail.next = current
            ll.tail = current
        current = nextNode
        
    # Error check in case all nodes are less than x
    if ll.tail.next is not None:
        ll.tail.next = None


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
partition(ll, ll.head.value)
print(ll)

실행결과
partition 46으로 선택했을 때의 결과이다.

46 -> 53 -> 52 -> 69 -> 48 -> 3 -> 23 -> 59 -> 2 -> 91
2 -> 23 -> 3 -> 46 -> 53 -> 52 -> 69 -> 48 -> 59 -> 91

2.5 Sum Lists

  • 2개의 연결 리스트가 있고 각각은 싱글 digit을 포함하고 있다. 그리고 이 숫자는 역순으로 정렬되어 있다. 즉 1의 자리숫자가 맨 앞에 있다는 뜻이 된다. 이 두개의 연결 리스트를 더해서 그 결과를 반환하는 코드를 작성하라.

Example
Input: (7->1->6) + (5->9->2). That is, 617 + 295
Output: 2->1->9. That is 912.

코드

def sum_lists(ll_a, ll_b):
    n1, n2 = ll_a.head, ll_b.head
    ll = LinkedList()
    carry = 0
    while n1 or n2:
        result = carry
        if n1:
            result += n1.value
            n1 = n1.next
        if n2:
            result += n2.value
            n2 = n2.next

        ll.add(result % 10)
        carry = result // 10

    if carry:
        ll.add(carry)

    return ll

실행 결과

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
3 -> 0 -> 6 -> 8

Follow up problem

  • 길이가 맞지 않는 경우
  • 계산결과를 head에 붙여서 처리하는 방식으로 구현

코드

def sum_lists_followup(ll_a, ll_b):
    # Pad the shorter list with zeros
    if len(ll_a) < len(ll_b):
        for i in range(len(ll_b) - len(ll_a)):
            ll_a.add_to_beginning(0)
    else:
        for i in range(len(ll_a) - len(ll_b)):
            ll_b.add_to_beginning(0)

    # Find sum
    n1, n2 = ll_a.head, ll_b.head
    result = 0
    while n1 and n2:
        result = (result * 10) + n1.value + n2.value
        n1 = n1.next
        n2 = n2.next

    # Create new linked list
    ll = LinkedList()
    ll.add_multiple([int(i) for i in str(result)])

    return ll

실행결과

뒤에서 부터 1의 자리로 생각 하기 때문에 결과가 다르다.

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
6 -> 2 -> 4 -> 5

2.6 주어진 연결 리스트가 회문(palindrome)인지 검사하는 함수를 작성하라

palindrome이라 함은 앞에서 보다 뒤에서 보다 같은 구조를 뜻한다.

0->1->2->1->0

해법1: 뒤집어 비교한다.

  • 포인트는 절반만 비교한다는 것이다.

해법2: 순환적(iterative) 접근법

  • 리스트 앞 절반을 뒤집는 것을 스택을 사용해서 구현 한다.
  • 연결리스트의 길이를 알 경우 절반만 push 하면 된다 (홀수인 경우에도 올바르게 처리 해줘야 한다).
  • 길이를 모를 경우 fast runner slow runner를 적절히 조합해서 사용 한다.

해법3: 재귀적 접근법

코드

def is_palindrome(ll):
    fast = slow = ll.head
    stack = []

    while fast and fast.next:
        stack.append(slow.value)
        slow = slow.next
        fast = fast.next.next

    if fast:
        slow = slow.next

    while slow:
        top = stack.pop()

        if top != slow.value:
            return False

        slow = slow.next

    return True


ll_true = LinkedList([1, 2, 3, 4, 5, 4, 3, 2, 1])
print(is_palindrome(ll_true))
ll_false = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(is_palindrome(ll_false))

실행 결과

True
False


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch 09 Recursion and Dynamic Programming  (0) 2017.08.23
Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Ch01 Array and Strings


1.1 문자열에 포함된 다른 문자들이 전부 유일한지를 검사하는 알고리즘 구현. 다른 자료구조를 사용할 수 없는 상황에서의

문자가 a~z로 총 26개라면 int 변수 1개로 count해서 이를 판별할 수 있다.

Code

public class QuestionB {

	/* Assumes only letters a through z. */
	public static boolean isUniqueChars(String str) {
		if (str.length() > 26) { // Only 26 characters
			return false;
		}
		int checker = 0;
		for (int i = 0; i < str.length(); i++) {
			int val = str.charAt(i) - 'a';
			if ((checker & (1 << val)) > 0) return false;
			checker |= (1 << val);
		}
		return true;
	}
	
	public static void main(String[] args) {
		String[] words = {"abcde", "hello", "apple", "kite", "padle"};
		for (String word : words) {
			System.out.println(word + ": " + isUniqueChars(word));
		}
		String a = "abcde";
	}
}

1.2 Permuation을 확인 하는 방법, Anagram 이랑 동일

정렬된 Algorihtm을 가지고 비교 한다.

Sroting을 해서 비교하는 방법이다.

public class QuestionA {	
	public static String sort(String s) {
		char[] content = s.toCharArray();
		java.util.Arrays.sort(content);
		return new String(content);
	}
	
	public static boolean permutation(String s, String t) {
		return sort(s).equals(sort(t));
	}	
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

Ascii 코드를 이용한 방법이다.

public class QuestionB {	
	public static boolean permutation(String s, String t) {
		if (s.length() != t.length()) return false; // Permutations must be same length
		
		int[] letters = new int[128]; // Assumption: ASCII
		for (int i = 0; i < s.length(); i++) {
			letters[s.charAt(i)]++;
		}
		  
		for (int i = 0; i < t.length(); i++) {
			letters[t.charAt(i)]--;
		    if (letters[t.charAt(i)] < 0) {
		    	return false;
		    }
		}
		  
		return true; // letters array has no negative values, and therefore no positive values either
	}
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

1.3 URLify 모든 빈 공간을 %20으로 채워라

예제
input: "Mr John Smith "
Output: "Mr%20John%20Smith"

뒷 쪽에 충분한 Margin이 있으므로 뒤에서 부터 앞으로 작업하는 것이 일반적인 방법이다.

two scan approach를 채택 한다.

  • 첫 번째에서는 number of spaces를 카운트 한다. 그 다음 3배를 해서 최종적으로 얼마나 많은 추가 character가 필요한지 알 수 있다.
  • 두 번째에서는 실제 string의 순서를 조절하게 된다. 즉 space가 있으면 %20을 채우고 no space면 orignal character를 채운다.
# O(N)
import unittest

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    new_index = len(string)

    for i in reversed(range(length)):
        if string[i] == ' ':
            # Replace spaces
            string[new_index - 3:new_index] = '%20'
            new_index -= 3
        else:
            # Move characters
            string[new_index - 1] = string[i]
            new_index -= 1

    return string

class Test(unittest.TestCase):
    '''Test Cases'''
    # Using lists because Python strings are immutable
    data = [
        (list('much ado about nothing      '), 22,
         list('much%20ado%20about%20nothing')),
        (list('Mr John Smith    '), 13, list('Mr%20John%20Smith'))]

    def test_urlify(self):
        for [test_string, length, expected] in self.data:
            actual = urlify(test_string, length)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

문자열 압축 (String Compression)

# O(N)
import unittest

def string_compression(string):
    compressed = []
    counter = 0

    for i in range(len(string)):
        if i != 0 and string[i] != string[i - 1]:
            compressed.append(string[i - 1] + str(counter))
            counter = 0
        counter += 1

    # add last repeated character
    compressed.append(string[-1] + str(counter))

    # returns original string if compressed string isn't smaller
    return min(string, ''.join(compressed), key=len)


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ('aabcccccaaa', 'a2b1c5a3'),
        ('abcdef', 'abcdef')
    ]

    def test_string_compression(self):
        for [test_string, expected] in self.data:
            actual = string_compression(test_string)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

Rotate Matrix

Matrix를 Rotation 하게 된다. 외부에서 안으로 진행하는 방식으로 처리 한다.

# O(NxN)
import unittest


def rotate_matrix(matrix):
    '''rotates a matrix 90 degrees clockwise'''
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - layer - 1
        for i in range(first, last):
            # save top
            top = matrix[layer][i]

            # left -> top
            matrix[layer][i] = matrix[-i - 1][layer]

            # bottom -> left
            matrix[-i - 1][layer] = matrix[-layer - 1][-i - 1]

            # right -> bottom
            matrix[-layer - 1][-i - 1] = matrix[i][- layer - 1]

            # top -> right
            matrix[i][- layer - 1] = top
    return matrix


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [1, 2, 3, 4, 5],
            [6, 7, 8, 9, 10],
            [11, 12, 13, 14, 15],
            [16, 17, 18, 19, 20],
            [21, 22, 23, 24, 25]
        ], [
            [21, 16, 11, 6, 1],
            [22, 17, 12, 7, 2],
            [23, 18, 13, 8, 3],
            [24, 19, 14, 9, 4],
            [25, 20, 15, 10, 5]
        ])
    ]

    def test_rotate_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = rotate_matrix(test_matrix)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

1.7 M x N 행렬의 한 원소가 0일 경우 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성

생각1
단순히 발견하는 0의 행과 열을 0으로 변경하면서 진행하면 금방 전부다 0이 되어 버린다.

생각2
추가적인 공간 O(MN)에 0의 위치를 기록하고 그 다음 해당 열과 행을 0으로 초기화 하는 방법이 있다.

생각3
그런데 정말로 O(MN) 만큼의 공간이 필요한가? 그렇지 않다. 같은 행과 열의 모든 원소의 값을 0으로 만들 것이므로, 0인 원소가 정확히 몇 번째 행에 몇 번째 열의 원소였는지 알 필요는 없다. 우리는 그저 어떤 행 안에 0 값을 갖는 원소가 있다는 사실만 기록하면 되고, 어떤 열 안에 0값을 갖는 원소가 있다는 사실만 기록하면 된다. 어차피 그 행과 열의 모든 원소를 0으로 만들 것인데, 왜 정확한 위치를 기록해야 하는가.

코드는 아래와 같다. 0이 있는 행과 열을 추적하기 위한 배열을 두 개 사용 했다. 그런 다음, 이 배열의 갑에 따라서 행과 열을 전부 0으로 만들도록 했다.

코드

# O(MxN)
import unittest


def zero_matrix(matrix):
    m = len(matrix)
    n = len(matrix[0])
    rows = []
    cols = []

    for x in range(m):
        for y in range(n):
            if matrix[x][y] == 0:
                rows.append(x)
                cols.append(y)

    for row in rows:
        nullify_row(matrix, row)

    for col in cols:
        nullify_col(matrix, col)

    return matrix


def nullify_row(matrix, row):
    for i in range(len(matrix[0])):
        matrix[row][i] = 0


def nullify_col(matrix, col):
    for i in range(len(matrix)):
        matrix[i][col] = 0


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [1, 2, 3, 4, 0],
            [6, 0, 8, 9, 10],
            [11, 12, 13, 14, 15],
            [16, 0, 18, 19, 20],
            [21, 22, 23, 24, 25]
        ], [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [11, 0, 13, 14, 0],
            [0, 0, 0, 0, 0],
            [21, 0, 23, 24, 0]
        ])
    ]

    def test_zero_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = zero_matrix(test_matrix)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

1.8 한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라.

s2가 s1을 회전시켜 얻은 문자열이라면, 회전된 지점이 어딘지를 알아봐야 한다.
가령 waterbottle을 회전시켜 erbbottlewat을 얻어다고 해보자.
회전시킬 때, s1을 x와 y의 두 부분으로 나눈 다음 다시 배열하여 s2를 얻었을 것이다.

s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat

하지만 중요한점은 x와 y를 나눈 지점이 어디인가 상관없이, yx는 언제나 xyxy의 부분 문자열이다. 다시 말해서, s2는 언제나 s1s1의 부분 문자열이란 이야기이다.

즉, isSubstring(s1s1,s2)인지 알아보면 된다는 것이다.

# O(N)
import unittest


def is_substring(string, sub):
    return string.find(sub) != -1


def string_rotation(s1, s2):
    if len(s1) == len(s2) != 0:
        return is_substring(s1 + s1, s2)
    return False


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ('waterbottle', 'erbottlewat', True),
        ('foo', 'bar', False),
        ('foo', 'foofoo', False)
    ]

    def test_string_rotation(self):
        for [s1, s2, expected] in self.data:
            actual = string_rotation(s1, s2)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch 09 Recursion and Dynamic Programming  (0) 2017.08.23
Ch02 LinkedList  (0) 2017.08.11
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Sorting


Bubble

시간복잡도는 $O(N^2)$이다.
공간복잡도는 $O(1)$

def bubbleSort(n, a):
    cumulatedNumSwap = 0
    for i in range(0, n):
        numSwap = 0
        for j in range(0, n-1):
            if a[j] > a[j+1]:
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                numSwap += 1
        cumulatedNumSwap += numSwap
        if numSwap == 0:
            break
    return cumulatedNumSwap, a

if __name__ == "__main__":
    a = [2, 1, 3, 1, 2]
    numSwap, sortedA = bubbleSort(len(a), a)

    print("Array is sorted in %d swaps."%numSwap)
    print("First Element: %d"%sortedA[0])
    print("Last Element: %d"%sortedA[-1])

Insertion

Time Complexity:

  • best: $O(n)$
  • worst: $O(n^2)$
    Space Complexity: $O(1)$

간단한 삽입정렬

def InsertionSort(input):
    for i in range(len(input)-1):
        for j in range(i+1,len(input)):
            if(input[j] < input[i]):
                input[i], input[j] = input[j], input[i]
    return input
import random

def InsertionSort(input):

    for idx, valueToInsert in enumerate(input):
        # select the hole position where number is to be inserted
        holePosition = idx

        # check if previous no. is larger than value to be inserted
        while holePosition > 0 and input[holePosition-1] > valueToInsert:
            input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
            holePosition = holePosition - 1

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    InsertionSort(A)
    print(A)

실행결과

[84, 59, 97, 41, 6, 93, 80, 62, 19, 37, 83, 24, 86, 95, 46]
[6, 19, 24, 37, 41, 46, 59, 62, 80, 83, 84, 86, 93, 95, 97]

Selection

Time complexity: $O(n^2)$
Space complexity: $O(1)$

import random
def selectionSort(input):
    for i in range(len(input) - 1):
        # assume the min is the first element
        idx_min = i
        j = i + 1

        # test against elements after i to find the smallest
        while j < len(input):
            if(input[j] < input[idx_min]):
                # found new minimum; remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i:
            # swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    selectionSort(A)
    print(A)

실행결과

[72, 10, 31, 7, 51, 11, 97, 9, 45, 54, 35, 26, 61, 55, 13]
[7, 9, 10, 11, 13, 26, 31, 35, 45, 51, 54, 55, 61, 72, 97]

Merge

worst와 average모두 $O(n \log n)$인 엄청나게 좋은 알고리즘이다.
하지만 공간 복잡도는 $O(n)$을 메모리는 많이 사용 합니다.
그래도 기본적인 Dvide and Conquer를 적용한 알고리즘이기에 확실히 알고 넘어가면 좋다.

위키피디아에 나온 그림으로 나타낸 동작 방법은 아래와 같다.

$T(n)=2T\left(\frac{n}{2}\right)+n$
$\begin{aligned}
T(n)&=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n \newline
&=4T\left(\frac{n}{4}\right)+n+n\newline
&=…\newline
&\approx O(\underbrace{n+n+…+n}_{\log n})\newline
&=O(n\log n)
\end{aligned}$

코드는 아래와 같다.

import random

# Time Complexity O(nLogn)
# Space Complexity O(n)

def mergeSort(A):
    ### Base case ###

    if len(A) <= 1:
        return A

    ### A를 반으로 쪼개서 recursive call을 해 주고 정렬된 반쪽짜리들을 받아옵니다.
    left = mergeSort(A[:int(len(A)/2)])
    right = mergeSort(A[int(len(A)/2):])

    ### 여기서부터 두 개의 쪼개졌던 list를 합치는 Merge 부분입니다.
    ### 여기서 포인트는 정렬된 상태로 돌아왔기 때문에 앞에서부터 순차적으로 한번만 돌면 정렬시킬 수 있다는 것입니다.
    i, j, k = 0, 0, 0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            A[k] = left[i]
            i += 1
        else:
            A[k] = right[j]
            j += 1
        k += 1
    if i == len(left): #만약 left의 원소를 모두 채웠고, right가 남아있을 때.
        while j<len(right):
            A[k] = right[j]
            j += 1
            k += 1
    elif j == len(right): #만약 right의 원소를 모두 채웠고, left가 남아있을 때.
        while i<len(left):
            A[k] = left[i]
            i += 1
            k += 1
    return A #마지막으로 정렬된 list를 리턴합니다.

if __name__ == "__main__":

    A=[random.randint(1,100) for _ in range(10)]
    print("unsorted List:")
    print(A)
    print("Sorted List:")
    print(mergeSort(A))

실행결과

unsorted List:
[94, 22, 47, 26, 28, 29, 33, 53, 5, 54]
Sorted List:
[5, 22, 26, 28, 29, 33, 47, 53, 54, 94]

참고자료
https://smlee729.github.io/python/algorithm/2015/03/03/1-merge-sort.html

Quick

분할 정복 알고리즘으로 Sorting한다.
Merge Sort와 다르게 분할 할 때 복잡하고 병합할 때는 복잡하지 않다.

평균 시간 복잡도는 $O(nlogn)$이다. 메모리 측면에서 좀 더 효율 적이다. 따라서 실제로 동작하는 속도가 좀 더 빠르다.
$$T(n)\approx n+2T(\frac{n}{2})$$

하지만, 최악의 상황인 이미 정렬이 완료된 List를 정렬할 경우 $T(n)=n+T(n-1)$으로 분할 된다.
왜냐하면 pivot이 가장 큰 값이라면 left side n-1개가 존재하고 이 부분을 계속 quick sort로 recursive하게 호출이 발생하기 때문이다. 결국 $O(n^2)$의 복잡도를 가진다.

Pivot이 Median값이라면 merge sort와 같은 복잡도를 가진다. 최악의 경우를 피하는 방법은 통상 random choice를 이용한다.

import random

# 아까 말씀드렸다시피, pivot을 선택한 후에(parition 함수의 결과값으로 pivot의 최종 index가 나옵니다.) recursive call로 쪼갭니다.
def quicksort(A, start, end):
    if start < end:
        p = partition(A, start, end)
        quicksort(A, start, p - 1)
        quicksort(A, p + 1, end)


# 이제 pivot을 뽑는 과정을 알아봅시다.
def partition(A, start, end):
    pivot = end
    wall = start
    # 나머지 원소들은 A[hi]와 비교하면서 재정렬합니다.
    for i in range(start, end):
        if A[i] < A[pivot]:
            #swap
            A[i], A[wall] = A[wall], A[i]
            wall += 1
    A[pivot], A[wall] = A[wall], A[pivot] # 마지막으로 pivot을 자신보다 큰 원소들의 첫번째 원소와 바꿔줍니다. (전반부, 후반부를 나누기 위해서)
    return wall

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    quicksort(A, 0, len(A)-1)
    print(A)


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch02 LinkedList  (0) 2017.08.11
Ch01 Array and Strings  (0) 2017.08.10
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31

Graph Search


아래와 같은 Graph가 있다고 가정한다.

Depth Frist Search (DFS)

  • 임의의 노드n을 선택
  • n을 방문했다고 표시
  • n의 방문하지 않은 인접 vertex를 방문한다.

Breadth First Search (BFS)

  • 노드 n부터 시작하고, 방문했다고 표시하면서 큐에 삽입
  • 큐가 empty일때까지 계속 반복하면서,
  • 큐에서 첫번째 원소를 뽑는다. 그리고 뽑은 원소의 방문하지 않은 이웃들을 방문했다고 표시 후에 큐의 끝에 지어넣는다.
class graph:
    def __init__(self, vertexList, edgeList):
        self.vertexList = vertexList
        self.edgeList = edgeList
        self.adjacentList = [[] for id in range(len(vertexList))]
        for edge in edgeList:
            self.adjacentList[edge[0]].append(edge[1])

def recursiveDFS(graph,node, visited=[]):
    visited.append(node)
    for neighbor in graph.adjacentList[node]:
        if neighbor not in visited:
            recursiveDFS(graph, neighbor, visited)
    return visited

# queue에 insert 할 때 넣는 방법
def BFS(graph,node, visited=[]):
    queue = [node] # 맨 처음 버텍스를 삽입 한다.
    visited.append(node) # 방문한 리스트에 맨 처음 버텍스를 넣는다.
    while queue: # 큐가 비었는지 확인 한다
        current = queue.pop() # 큐에서 데이터를 꺼내온다.
        for neighbor in graph.adjacentList[current]: # 인접 vertex에서 값을 하나 가져온다.
            if not neighbor in visited: # 현재 인접 노드의 값이 방문한 것이 아닌지 확인 한다.
                queue.insert(0,neighbor)
                visited.append(neighbor)
    return visited

# queue에 pop할 때 visit 하는 방법
def BFS2(graph,node, visited=[]):
    queue = [node]
    #visited.append(node)

    while queue:
        current = queue.pop()
        for vertex in graph.adjacentList[current]:
            if vertex not in visited:
                queue.insert(0, vertex)
        visited.append(current)
    return visited



if __name__ == "__main__":

    # Depth First Search (DFS)
    vertexList = ['0', '1', '2', '3', '4', '5', '6']
    edgeList = [(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]

    graphObj = graph(vertexList, edgeList)
    print("vertex list")
    print(graphObj.vertexList)
    print("edge list")
    print(graphObj.edgeList)
    print("adjacent list")
    print(graphObj.adjacentList)

    print("DFS Traverse:")
    print(recursiveDFS(graphObj,0))
    print("BFS Traverse:")
    print(BFS(graphObj,0))

실행결과

vertex list
['0', '1', '2', '3', '4', '5', '6']
edge list
[(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]
adjacent list
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
DFS Traverse:
[0, 1, 3, 2, 4, 6, 5]
BFS Traverse:
[0, 1, 2, 3, 4, 5, 6]

참고자료
https://smlee729.github.io/python/network%20analysis/2015/04/09/1-networkx-dfs-bfs.html


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31

String


Reverse

input = list("abcdefg")

mid = int(len(input)/2)
left = 0
right = len(input)-1

while left < right:
    input[left], input[right] = input[right], input[left]
    left += 1
    right -= 1

print(input)

Super Reduced String

  • pair string을 줄이는 작업을 수행 한다.
def super_reduced_string(S):
    LS = list(S)
    i = 0
    while i < len(LS)-1:
        if LS[i]==LS[i+1]:
            del LS[i]
            del LS[i]
            i = 0
            if len(LS) == 0:
                return 'Empty String'
        else:
            i+=1
    return ''.join(LS)

CamelCase

eBay, iPhone처럼 중간에 띄어쓰기 없이 대소문자로만 단어를 구분하는 것을 말한다.

이렇게 표시된 unique한 단어가 몇개인지 찾아서 출력 해야 한다.

#!/bin/python3

import sys
import string

s = input().strip()

sl = list(s)

i = 0
count = 1
while i < len(sl):
    if sl[i].isupper():
        count += 1
    i += 1

print(count)

한줄 코드

print(sum(map(str.isupper, input())) + 1)

Sliding Window

https://scipher.wordpress.com/2010/12/02/simple-sliding-window-iterator-in-python/

Two Characters

번갈아 가면서 두개의 서로다른 character를 배열 해야 한다.

  • (o) xyxyx or yxyxy
  • (x) xxyy or xyyx

들어온 입력에 대해서 가능한한 가장 긴 두개의 charater로만 생성 가능한 그리고 번갈아 가면서(alternating)으로 만들 수 있는 string을 반환하는게 목적이다.

불가능 하다면 0을 리턴 한다.

예제

10
beabeefeab

해설

  • If we delete e and f, the resulting string is babab. This is a valid as there are only two distinct characters (a and b), and they are alternating within the string.
  • If we delete a and f, the resulting string is bebeeeb. This is not a valid string because there are three consecutive e's present.
  • If we delete only e, the resulting string is babfab. This is not a valid string because it contains three distinct characters.
  • Thus, we print the length of babab, which is , as our answer.
import sys

def validate(inp):
    for i in range(len(inp)-1):
        if inp[i+1]==inp[i]:
            return False
    return True    
    

s_len = int(input().strip())
s = input().strip()

ans = 0
chtoindex = []
for ch in set(s):
    chtoindex.append((ch, len([j for j, x in enumerate(s) if x == ch])))
    

for i, pack in enumerate(chtoindex[:-1]):
    char_i, lenchar_i = pack[0], pack[1]
    for j, otherpack in enumerate(chtoindex[i+1:]):
        char_j, lenchar_j = otherpack[0], otherpack[1]
        if abs(lenchar_i-lenchar_j)<2:
            c = [cha for cha in s if cha is char_i or cha is char_j]
            if validate(c):
                ans = max(ans, lenchar_j+lenchar_i)
print(ans)

참고자료

문자열관련 Python 유용함수 모음 블로그


'Computer Science > Coding Interview' 카테고리의 다른 글

Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30

HackerRank- Trees: Is This a Binary Search Tree


해당 트리가 이진 탐색 트리인지 확인 하는 문제이다.

단순히 특정 노드의 자식들 값이 부모보다 작은지 큰지를 가지고 판단할 경우 아래의 경우에 문제가 발생 한다.

이유는 4의 경우 root 보다 큰대도 불구하고 자식 노드의 자식으로 분류되어 있다.
즉, 더 윗 부분의 부모 노드에서 판단하는 부분이 제외 되기 때문에 문제가 발생 한다.

방법1

  • 재귀적으로 최소 최대 값을 확인하며 루프를 도는 방법
  • 일단 데이터에 음수가 없다는 가정에서 출발 한다.
def checkBST(root):
    return(check_in_order(root,[-1]))
    
def check_in_order(root,prev):
    result = True
    if root.left is not None:
        result &= check_in_order(root.left,prev)
    if prev[0] >= root.data:
        return False
    prev[0] = root.data
    if root.right is not None:
        result &= check_in_order(root.right,prev)
    return result

방법2

  • Inorder traversal을 해서 확인하는 방법.
  • 올바른 Binary Search라면 출력이 순차적이게 된다.
  • 해당 문제에서 보면 중독된 노드는 이진탐색트리로 허용하지 않으니 그 문제에 대한 해결을 필요로 한다.
""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    # traversal by inOrder 
    resList = []
    resList = inOrder(root,resList)
    sortedList = sorted(resList)
    
    if len(set(resList)) != len(resList):
        return False
    
    if len([i for i, j in zip(resList, sortedList) if i == j]) == len(resList):
        return True
    else:
        return False
    
def inOrder(node,resList):
    if node.left is not None:
        resList = inOrder(node.left, resList)
    resList.appen