Google DSC Sookmyung

✅ Q1. Garbage Collection이란, 동작 방식에 대해서 설명하세요. Java 이전의 C나 C++같은 언어는 개발자가 직접 메모리 할당과 해제를 컨트롤 해야했다. (ex: C의 malloc과 free) 이는 잦은 메모리 이슈로 이어졌고, 개발환경 개선을 위해서 Garbage collection이 등장했다. 개발자가 하던 메모리 할당과 해제를 대신 해주는 것이다. 이렇게 메모리는 알아서 관리하는 언어들을 Managed language라고 한다. 언어와 동작하는 환경마다 GC의 동작 방식이 조금씩 다르지만, 특정한 때에 특정한 방식으로 필요없는 정보(garbage)를 쓸어담아 버린다. 자바스크립트의 GC 자바스크립트는 객체가 생성되었을 때 자동으로 메모리를 할당하고, 쓸모 없어졌을 때 자동으로 ..

✅ Q1. P-NP 문제란? 집합 P와 NP가 서로 같은지 다른지를 증명하는 문제이다. (집합 P가 NP의 진부분집합인지 아닌지) 아직 컴퓨터과학의 미해결 문제중 하나이다. P = NP P와 NP문제는 모두 결정문제이다. (결정문제 - 답이 YES 아니면 NO로 딱 떨어지는 문제들 ex. a는 b의 배수인가?) ↔ 함수형문제: 답이 셋 이상이 있는 경우 P문제 결정문제 중, 쉽게 풀리는 문제를 모은 집합 → 어떤 결정 문제가 주어지면, 다항식 시간(==합리적인 시간) 이내에 그 문제의 답을 YES? NO? 중 하나로 계산해낼수 있는 알고리즘이 존재하면 P문제이다. NP문제 결정 문제들 중, 적어도 검산을 쉽게 할 수 있는 것을 모은 집합 → 다항식 시간 이내에 그 문제의 답을 YES? NO?로 계산해낼 ..

Q1. 동기 vs 비동기 동기와 비동기는 프로세스 수행 순서에 대한 메커니즘이다. → 가장 많이 나오는 일반적인 예시 : 은행 업무를 볼 때 한 창구에서 한 줄로 서서 보는 업무 == “동기” 여러 업무 창구에서 보는 업무 == “비동기” 동기 의미 💡 synchronous : happening, existing, or arising at precisely the same time → 같은 시간에 발생하고 존재하는 것! 즉, 동기는 “작업의 요청과 응답이 동시에 일어난다는” 의미를 가진다. → 작업 a, b가 있을 때 작업 a의 요청이 먼저 들어왔다고 하자! (작업 a를 처리하는 데 100초가 걸린다.) a의 요청을 처리하는 동안, 즉, 100초의 시간 동안 대기하다가 처리가 완료되고 작업 a에 대한 응..

Q. 배열에 빠진 수를 찾으세요. 서로 다른 [1, n]범위의 n-1개의 숫자가 들어있는 리스트가 주어집니다. 주어진 배열에 빠진 수를 찾으세요. 정렬sort 배열에 숫자가 있는지 하나씩 검사하는 방법 def sort(A): A.sort() for i in range(1, len(A) + 1): if cur not in A: print("Missing number is " + str(i)) break 시간복잡도: O(nlogn) 파이썬 내장함수 .sort 시간 복잡도가 O(nlogn) 공간복잡도: O(1) 완전탐색 범위 내의 숫자를 하나씩 존재하는지 검사 def bruteforce(): N = len(A) for i in range(1, N+1): flag = False for x in A: if i =..

CS 문제 제공 Repository : Brave Tech Interview Q1. map, hashmap, set에 대해서 설명하세요 더보기 Map 맵은 키(key)와 값(value)의 쌍으로 이루어진 자료구조이다. 키를 값에 매핑하는 객체이며, 중복 키는 있을 수 없다. 각 키는 최대 하나의 값에 매핑할 수 있으므로 이름이 된다. 이런 쌍을 map entries(맵 항목)이라고 부른다. 같은 맵에 두 개 이상의 키가 존재하면 안되는 반면, 값은 중복된 값이어도 상관이 없다. 이러한 맵의 특성 때문에 키를 활용하여 값을 검색할 수 있다. 자바 플랫폼에는 HashMap, TreeMap, LinedHashmap의 3가지 범용 맵 구현이 포함되어 있다. HashMap 말 그대로 해싱된 맵이다. 키를 해싱하여..

Q1. Dynamic Programming이란? 장점은? 메모리를 적절히 사용해서 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과는 별도의 메모리에 저장해서 다시 계산하지 않도록 함 일반적으로 2가지 방식으로 구성됨 Top Down (하향식) Memoization : 한 번 계산한 결과 메모리 공간에 메모 (== caching) Bottom Up (상향식) 특정 문제가 다음의 조건 만족할 때 사용 가능 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있음 작은 문제의 답을 모아서 큰 문제 해결할 수 있음 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 함 장점 하나의 문제를 단 한번만 풀기 때..