Goyummy

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 빅오 표기법시간 복잡도입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간주요 로직의 반복 횟수에 중점을 둠보통 빅오 표기법으로 나타낸다.for (int i = 0; i => 10n^2 + n => O(n^2)가장 영향을 많이 끼치는 상수 인자를 빼고 나머지 항을 없앤 것.   시간 복잡도가 필요한 이유 효율적인 코드로 개선하는데 쓰이는 척도가 된다.  공간 복잡도프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다. int a[1004];이면 int의 크기는 4byte이므로 1004 * 4 btye만큼의 공간이 필요하다.  자료 구..

도넛과 막대 그래프문제 설명도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형..

Virtual MachineHypervisor가 각각의 App이 독립된 하드웨어에서 돌아가는 것처럼 만들어준다.물리적 하드웨어 자원을 가상화하여  여러 운영체제를 동시에 실행할 수 있도록 하는 소프트웨어이다.물리적 자원을 가상 머신에게 분배하고, 각각의 가상 머신이 독립적으로 실행되도록 한다.Guest OS를 설치하고 동작시키므로 무겁다.Hypervisor 위의 Guest OS는 Host OS와 달라도 된다. AWS에서는 VM을 Instance라고 한다. 코어를 나눠서 서비를 내준다. / 메모리를 잘라서 내준다. Infrastructure as Service => IaaSIaaS는 서버, 스토리지 및 네트워크 등과 같은 사용자가 필요한 컴퓨팅 자원을 가상화된 형태로 제공하는 서비스이다. 이 서비스 이용시..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 조인은 조인의 원리를 기반으로 조인 작업이 이루어진다.조인의 원리는 중첩 루프 조인, 정렬 병합 조인, 해시 조인이 있다. 중첩 루프 조인중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법이다.랜덤 접근에 대한 비용이 많이 증가해서 대용량의 테이블에서는 사용하지 않는다. (디스크 접근 문제)예시t1, t2 테이블을 조인한다라고 했을 대, t1 테이블에서 한번에 하나의 행을 가져와서 읽고, t2 테이블에서도 한번에 하나의 행을 가져와서 읽어서 조건에 맞는 레코드를 찾아 결과값을 반환한다.중첩 루프 조인에서 발전한 조인할 테이블을 작은 블록으로 나누어서 블록 하나씩 조인하는 블록 중첩 루프 조인도 있다.pseudo codefor eac..

전력망을 둘로 나누기문제 설명n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.제한사항n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는..

최솟값 만들기문제 설명길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = ..

숫자의 표현문제 설명Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.1 + 2 + 3 + 4 + 5 = 154 + 5 + 6 = 157 + 8 = 1515 = 15자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.제한사항n은 10,000 이하의 자연수 입니다.입출력 예nresult154입출력 예 설명입출력 예#1문제의 예시와 같습니다. 정답 풀이def solution(n): answer = 0 for i in range(1, n + 1): ..

피보나치 수문제 설명피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.예를들어F(2) = F(0) + F(1) = 0 + 1 = 1F(3) = F(1) + F(2) = 1 + 1 = 2F(4) = F(2) + F(3) = 1 + 2 = 3F(5) = F(3) + F(4) = 2 + 3 = 5와 같이 이어집니다.2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.제한 사항n은 2 이상 100,000 이하인 자연수입니다.입출력 예nreturn3255입출력 예 설명피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 조인이란 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것이다. MySQL에서는 JOIN이라는 쿼리로, MongoDB에서는 lookup이라는 쿼리로 이를 처리할 수 있다. (MongoDB를 사용할 때 lookup은 되도록 사용하지 말기. 관계형 데이터베이스에 비해 lookup의 성능이 떨어진다. -> 여러 테이블을 조인하는 작업이 많을 경우에는 MongoDB보다는 관계형 데이터베이스를 써야 한다.) 내부 조인(inner join)왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기된다.교집합SELECT * FROM TableA AINNER JOIN TableB B ONA.key = B.k..

큰 수 만들기문제 설명어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.제한 조건number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.k는 1 이상 number의 자릿수 미만인 자연수입니다.입출력 예numberkreturn"1924"2"94""123123..