바위타는 두루미

문제 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다. 해결법 재귀적으로 각 노드까지의 높이를 확인하며 1이상의 차이가 나는지 확인하고, 1 이상의 차이가 나지 않는다면 높이를 반환해 나가며 균형이 잡혀있는지 확인한다. def chkHeight(root): if root is None : return -1 left = chkHeight(root.left) if left == float("Inf") : return float("Inf") right = chkHeight(root.right) if right == float("Inf") : return float("..

문제 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야한다. 접근법 재귀를 이용한 전위탐색으로 해결하거나, BFS로 해결이 가능하다. 두 방법모두 비슷한 탐색법이지만, 재귀를 이용한 전위탐색은 탐색시 logN만크의 추가공간을 요구한다. 하지만 어쩌피 return할때 무조건 N만큼 공간을 차지하기 때문에 N에 비교하면 logN은 많은 공간이 아니고, 공간 효율성 측면에서는 두 방법모두 O(N)이다. 아래 코드는 BFS로 탐색하여 해결한 코드 def Solution(root): level_list = [] current = [] if root is not None: current.append(root) wh..

문제 오름차순으로 정렬된 배열이 있다. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을때 높이가 최소가 되는 이진탐색트리를 만드는 알고리즘을 작성하라. 접근법 이진탐색트리는 '모든 왼쪽 자식들

문제 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop,peek,isEmpty의 네가지 연산을 제공해야한다. 접근법 정렬을 위한 스택을 하나 더 사용한다고 했을떄, 두번째 스택에는 정렬된 형태로만 들어갈 수 있도록 하여 해당 값이 들어갈 위치를 찾아주는 방식으로 해결 할 수 있다. class SortStack : def __init__(self): stack = [] def sort(self): tmp_stack = [] while stack : cur_num = stack.pop() if not tmp_stack or tmp_stack[-1] >..

문제 스택 두개로 큐 하나를 구현한 MyQueue 클래스를 구현하라 접근법 q1, q2가 존재하고 push를 하면 q1에 넣는다. pop를 부르는 순간, p1에서 p2에 순차적으로 pop하고 push한다. 그리고 p2에서 pop하면 가장 먼저 들어간 데이터가 먼저 나올 것이다. (FIFO) class QueueByStack : def __init__(self): s1 = [] s2 = [] def push(self, num): sl.append(num) def pop(self): if not s2 : while s1 : s2.append(s1.pop()) return s2.pop()

문제 기본적인 push와 pop기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고한다. 어떻게 설계할 수 있는가? push, pop, min 연산은 모두 O(1)시간에 동작해야한다. 접근법 1. minValue 변수를 두고 minValue가 제거되면 다음 minValue를 탐색한다. -> push와 pop이 O(1)에 연산이 불가능 2. 스택에 각 상태값(minValue)를 함께 저장해두기 class MinStack : def __init__(self): stack = [] def push(self, num): if len(stack) == 0 : stack.append((num, num)) else : cur_min = min(stack[-1][1], num) stack.append((nu..

문제 SSL/TLS가 무엇인가요? 대답 SSL은 대칭키 암호화 방식과 공개키 암호화 방식을 혼합한 하이브리드 암호시스템이다. 대칭키 암호화 방식은 암호화와 복호화에 같은 암호키(대칭키)를 사용하는 암호화 알고리즘이다. 장점 : 공개키 암호화 방식에 비해 암호화 및 복호화가 빠르다. 단점 : 대칭키를 직접 전달하지 않는 한 대칭키를 전달하는 과정에서 해킹의 위험에 노출 될 수 있다. 공개키 암호화 방식은 암호화와 복호화에 사용되는 암호키를 분리한 방식이다. 자신이 가지고 있는 고유한 개인키(Private Key)로만 복호화 할 수 있는 공개키(Public Key)를 대중에 공개한다. 이 방식이 진행되는 방식을 살펴보면, A가 웹상에 공개된 'B의 공개키'를 이용하여 평문을 암호화 하여 전송한다. B는 자신..

문제 1 HTTP 와 HTTPS 의 차이는 무엇일까요? 대답 HTTPS는 HTTP의 보안적인 문제를 해결하기위해 SSL의 껍질을 덮어쓴 HTTP이다. HTTP의 문제점 1. HTTP는 평문 통신이기 때문에 도청이 가능하다. - TCP/IP 구조의 통신은 모두 통신경로상에서 엿볼 수 있는데, 평문으로 통신하기 때문에 메세지의 의미까지 모두 파악할 수 있다. 2. 통신상대를 확인하지 않기 때문에 위장이 가능하다. - HTTP의 통신에서는 상대가 누구인지 확인하는 처리가 없기 때문에 누구든지 리퀘스트를 보낼 수 있다. 이 특징이 가져오는 문제는 1. 리퀘스트를 보낸 곳의 웹 서버가 원래 의도한 리스폰스를 보내야하는 웹 서버인지 알 수 없다. 2. 리스폰스를 반환한 곳의 클라이언트가 원래 의도한 클라이언트인지 ..

문제 순환 연결리스트(Circular linked list ) 가 주어졌을때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서는 변질된 방식의 연결리스트를 의미한다. 해결법 해법에 있는 해결법은 Runner 기법을 이용해 해결하는데 독특해서 그대로 가져와봤습니다. 1. 연결리스트에 루프가 있는지 검사 FastRunner와 SlowRunner가 각각 2칸씩 1칸씩 이동한다면 루프가 있다면 언젠가 충돌한다. 2. 언제충돌하지? 루프가 아닌 부분의 크기가 K라고 했을때, SlowRunner가 루프에 진입하기 시작하는 순간은 K번 움직인 순간이고 그순간에 FastRunner는 두배를 움직..

문제 단방향 연결리스트 두개가 주어졌을때 이 두리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다. 해법 교집합의 유무를 판별하기 위해서는 우선 각 리스트의 마지막노드가 같아야하고, 같은 길이의 출발점에서부터 순차적으로 탐색을 했을때 동시에 방문하는 노드가 같은 점이 잇어야한다. 1. 각 연결리스트를 순회하면서 길이와 마지막 노드를 구한다. 2. 길이가 긴쪽의 리스트에서 짧은쪽과의 차이만큼 시작포인터를 옮긴다. 3. 두 포인터가 같아질때까지 두 리스트를 함께 순회한다. def lengt..