Next Permutation Algorithm은 순열 알고리즘 중에 하나로 무작위 순열의 다음 순열을 구하는 알고리즘입니다. 시간 복잡도는 O(N)이고 Greedy 알고리즘을 기반으로 합니다. 아래의 수열을 예로 다음에 올 순열을 구해보겠습니다. 5가지의 무작위 숫자가 주어지고 이를 N 배열에 저장합니다. Greedy를 이용하여 N[i] N[i]를 만족하는 j값을 구합니다. 바로 직전 반복문에서 N[i] < N[i + 1]을 만족했기 때문에 j는 최소한 하나는 무조건 존재합니다. j를 찾았으면 N[i]와 N..

문제 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 풀이 단순히 \( _{n}\mathrm{C}_{m} \) 으로 답을 구하기엔 n과 m이 20억일 때 제한시간을 초과할 수 있습니다.(1000만 ~ 10억 개의 연산이 약 1초 소요) 따라서 수학적으로 접근해서 풉니다. 조건(1): \( _{n}\mathrm{C}_{m} = {_{n}\mathrm{P}_{m} \over m!} = { n! \over m! \times (n - m)!} \) 조건(2): 어떠한 수x가 있을 때, x를 인수분해했을 때 인수..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 DP를 이용하여 풉니다. 문제에 주어진 예제를 2차원 DP 테이블에 나타내면 다음과 같습니다. - C A P C A K - 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 2 3 4 P 0 1 2 3 3 3 4 입력받은 두 문자열을 순..

가상화란?(virtualization) 가상화는 하나의 컴퓨터에서 여러 개의 운영체제를 동시에 실행하는 것을 말합니다. 가상화를 사용하는 이유? 일반적으로 OS를 실행하려면 OS 하나당 물리적 서버 1대가 필요합니다. 여러대의 서버를 운영하는 것은 비용이 많이 들기 때문에 가상화를 이용해서 Linux나 Windows 같은 여러 운영체제를 하나의 물리적 머신에서 동시에 실행하여 시간과 비용을 절약할 수 있습니다. 또한 기술적으로 자세한 내용을 격리하여 외부로부터 숨기기 위한 목적으로 사용합니다. 가상화의 장점 대부분의 서버는 용량의 단 10~15%만 사용하는데 가상화로 서버의 효용률을 70%이상으로 올리 수 있습니다. 한 물리적 서버에서 다른 물리적 서버로 파일이나 사진을 옮기는 것처럼 운영체제도 이동이 ..

문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 간선의 비용이 전부 1로 같기 때문에 BFS를 사용했습니다. 딕셔너리 타입의 edges 변수에 (현재 노드: 연결된 다음 노드)의 형태로 값을 push합니다. BFS로 사이클의 갯수를 셉니다. 사이클을 찾으면 사이클 안에 포함된 노드들을 cycle_components 리스트에 넣어서 다음 사이클 탐색시 이미 사이클..

도커란 애플리케이션을 개발, 실행, 관리하기 위한 컨테이너 기반의 오픈 소스 플랫폼입니다. 도커는 컴퓨터의 실행환경에 구애 받지 않고 컨테이너안에 프로그램 실행에 필요한 모든 실행 환경들을 패키징하여 프로그램의 배포 및 관리를 단순하게 해줍니다. 도커는 go 언어로 작성되었습니다. 도커 컨테이너는 일종의 소프트웨어를 소프트웨어의 실행에 필요한 모든 것을 포함하는 완전한 파일 시스템 안에 감싼다. 여기에는 코드, 런타임, 시스템 도구, 시스템 라이브러리 등 서버에 설치되는 무엇이든 아우른다. 이는 실행 중인 환경에 관계 없이 언제나 동일하게 실행될 것을 보증한다. - 위키백과 컨테이너란? 컨테이너는 도커가 등장하기 전에도 있던 기술로, 격리된 공간에서 프로세스가 동작하는 기술입니다. 기존의 VMware나 ..