CEO

Recursion? 재귀는 특정 함수 내에서 함수 자신을 다시 호출하는 것을 의미한다. 재귀는 Stack의 특성을 그대로 반영하여, 가장 최근에 호출된 함수 부터 처리되는 방식으로 진행된다. 재귀를 잘 다룰 수 있다면 DFS와 백트래킹, 트리 탐색과 같은 문제를 해결 할때 효율적으로 접근할 수 있게 된다. 이진 트리 순회 그림 1과 같은 이진 트리가 있을 경우, 3가지 방식으로 트리를 순회할 수 있다. 첫 번째는 전위 순회로 1-2-4-5-3-6-7 순서로 트리를 순회한다. 두 번째는 중위 순회로 4-2-5-1-6-3-7 순서로 트리를 순회 한다. 마지막으로 후위순회는 4-5-2-6-7-3-1로 순회한다. 트리를 순회하는 것은 재귀 호출을 통해서 구현 할 수 있다. Simple Tree Travel de..

Linked List? 단순한 선형 배열(리스트)을 선언하면 메모리를 연속적으로 할당한다. 만약, 배열 내의 값 삭제가 필요하거나 추가가 필요한 경우 값들의 자리 교체가 필요하다. 이와 달리 연결 리스트는 연속적인 공간을 사용하지 않고, 각각의 노드들을 연결한 구조로 연결되어 중간의 값 삭제가 빈번하게 일어나는 자료를 관리하기에 보다 효율적이다. Single Linked List class Node: def __init__(self, data): self.data = data self.next = None class SingleLinkedList: def __init__(self, data): self.head = Node(data) def add(self, data): node = self.head w..

Queue? 가장 처음에 삽입된 데이터를 먼저 뺄 수 있는 방식(First in First Out) 형식의 자료구조 Queue의 연산 enqueue(data) : data를 Queue의 가장 마지막에 추가한다. dequeue() : Queue의 가장 최근에 추가된 data를 제거하고 반환한다. peek() : pop()과 달리 가장 최근에 추가된 data를 반환하고, 제거하진 않는다. is_empty() : pop()을 수행하기 위해서는 추가된 data가 존재하여야 하는데 이를 판별하기 위함이다. Queue를 활용하는 경우 선입선출이 필요한 경우 프로세스 관리, 우선순위 대기열, 프린터 출력 처리 등 BFS 구현 Queue의 선입선출 방식을 통해 BFS를 구현할 수 있다. DFS의 경우 Stack을 사용..

Stack? 가장 마지막에 삽입된 데이터를 먼저 뺄 수 있는 방식(Last in First Out) 형식의 자료구조 Stack의 연산 push(data) : data를 stack의 가장 마지막에 추가한다. pop() : stack의 가장 마지막에 추가된 data를 제거하고 반환한다. peek() : pop()과 달리 가장 최근에 마지막의 data를 반환하고, 제거하진 않는다. is_empty() : pop()을 수행하기 위해서는 추가된 data가 존재하여야 하는데 이를 판별하기 위함이다. Stack을 활용하는 경우 재귀 호출 재귀적으로 함수를 호출하는 경우, 가장 마지막에 호출된 함수 부터 차례로 실행결과를 반환한다. 따라서 재귀 호출의 경우 Stack을 통해 이를 가능하도록 한다. 수식의 괄호 검사 (..

문제 Peaks coding task - Learn to Code - Codility Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] A[P + 1]. app.codility.com 문제 풀이 각 구간을 나눌 때, 각 구간마다 peek를 포함하여야 한다. 문제를 해결하기 위해 peek인 구간을 찾는다. 나눌 수 있는 구간은 주어진 A 리스트의 길이의 약수를 의미하는 것이므로, 약수에 대한 구간을 확인하고 peek를 포함하는 지 확인한다. 코드 def solution(A): peeks = [] length = len(A) f..

문제 MinPerimeterRectangle coding task - Learn to Code - Codility Find the minimal perimeter of any rectangle whose area equals N. app.codility.com 문제 풀이 Count Factor의 경우 약수를 단순히 카운트 하였다면, 넓이가 주어질 때 가장 작은 둘레를 가지는 경우를 찾는 문제이다. 넓이가 주어질 때, 두 변의 길이가 되는것은 각각의 약수 이므로, 약수 중 가장 큰 약수를 통해 계산된 둘레를 반환하면 된다. 코드 import math def solution(N): for num in range(int(math.sqrt(N)), 0, -1): if N % num == 0: break retu..

문제 CountFactors coding task - Learn to Code - Codility Count factors of given number n. app.codility.com 문제 풀이 예를 들어 24라는 수가 주어지면 24의 약수의 개수를 효율적으로 구하는 문제이다. 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24로 개수는 8개 이다. 코드 def solution(N): i = 1 ret = 0 while i * i < N: if N % i == 0: ret += 2 i += 1 return ret + 1 if i * i == N else ret 브루트포스로 풀면 효율성 부분을 통과할 수 없다. 약수는 구하고자 하는 수인 N 까지 모두 탐색하지 않아도 되는 특성을 활용하면 쉽게 ..

문제 MaxSliceSum coding task - Learn to Code - Codility Find a maximum sum of a compact subsequence of array elements. app.codility.com 문제 풀이 Max Profit 문제와 동일하게 브루트 포스로 풀지 않고, 카데인 알고리즘 사용하면 쉽게 풀 수 있다. 코드 def solution(A): max_sum = sub_sum = A.pop(0) for num in A: sub_sum = max(sub_sum + num, num) max_sum = max(max_sum, sub_sum) return max_sum