본문 바로가기

분류 전체보기

 (700)
sha256sum [1. 개요] 파일의 sha256 해시코드를 계산하는 명령어로 계산한 해시코드를 이용해 파일의 무결성을 체크 할 수 있다. [2. 예제] 해시코드 계산 => /root/abc.txt 라는 파일이 있다고 가정 $ sha256sum /root/abc.txt => 결과 edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb /root/abc.txt $ sha256sum abc.txt => 결과 edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb abc.txt 무결성 체크 $ sha256sum abc.txt > my.sha256 $ sha256sum --check my.sha256 => ..
최소신장트리. [1197] [1. 문제 설명] 그래프가 주어졌을 때, 최소 신장 트리의 가중치를 출력한다. [2. 풀이 접근] A. 크루스칼 알고리즘 edge 를 가중치를 기준으로 하여 오름차순 정렬한다. 가중치가 낮은 edge 부터 tree 에 추가하도록 한다. => edge 추가로 인해 cycle 이 발생하는 경우, 이번 edge 는 버리도록 한다. tree 에 추가된 edge 개수가 정점의 개수 - 1 일 때 까진 반복한다.\ => cycle 여부 판별을 union-find 를 이용하면 전체 알고리즘은 정렬 시간에 가장 큰 영향을 받는다. (최적의 union-find 는 거의 상수 시간으로 동작 하기 때문이다.) => 시간복잡도: O(ElogE) B. 프림 알고리즘 임의의 정점에서 시작한다. (보통 번호가 가장 빠른 노드) ..
docker compose 설치 [1. 개요] docker compose 란? 여러 개의 docker container 를 간단하게 실행하기 위한 하나의 툴이다. 어떤 서비스가, mysql container 와 이를 사용하는 어떤 application 을 실행하는 컨테이너로 구성되어 있을 때, 두 컨테이너를 설정파일에 맞게 알아서 실행시켜 준다. (작업자가 mysql container 를 실행하고, application container 를 실행 할 필요가 없다.) 설정파일은 yml 파일 형식으로 작성한다. [2. 설치] windows docker 는 보통 docker compose 를 따로 설치 할 필요가 없다. 설치가 필요한 경우 linux 와 비슷한 방식으로 설치하면 된다. linux 에서는 아래와 같은 방식으로 docker co..
소수 판정 [1. 개요] 어떠한 자연수가 소수인지 판별 할 수 있는 방법에 대해 정리한다. [2. 알고리즘] 단순한 방법 => 소수는 1과 자기자신으로만 나누어 떨어지므로, => 2 부터 N-1 까지의 자연수 중 나누어 떨어지는 것이 있는지 확인 한다. => 단일 자연수 N에 대해서 시간 복잡도는 O(N) 이 된다. N 의 절반까지만 확인 => N 의 제곱근 까지만 확인 => [3. 에라토스테네스의 체] 특정 범위 내 모든 소수를 찾을 때 매우 유용하다. 시간 복잡도가 O(nlog(logn)) 이다. 원리 최초 모든 수를 소수라 가정 '1'은 소수가 아니라고 망킹 '2' 는 소수이므로, 2의 배수를 모두 소수가 아니라고 마킹 '3' 은 소수이므로, 3의 배수를 모두 소수가 아니라고 마킹 다음 수 에 대해서 반복, ..
Meet in the middle. [1450] [1. 문제 설명] N 개의 물건을 최대 C 만큼의 무게를 넣을 수 있는 가방에 넣을 수 있는 경우의 수를 구한다. N 은 30 이하의 자연수 C 는 10억 이하의 자연수 [2. 풀이 접근] 이 문제는 동적 계획법으로 풀이가 가능하다. 단, 완전 탐색 중 i 번째 물건을 포함할지 말지를 결정할 때, 아래에 대해서 메모이제이션 할 수 있어야 한다. i번째 물건의 index 현재까지 누적된 무게 그러나 문제에서 C 는 최대 10억이 될 수 있으므로, 메모리가 부족하여, 다른 접근법이 필요하다. 다시 완전 탐색으로 돌아와서 생각해보면, 문제는 탐색의 개수가 너무 많다는 것이다. 재귀의 각 단계에서 i번째 물건 선택여부가 존재하니, 총 탐색 개수는 2N 이다. N 이 최대 30이니, 대략 10억 정도 된다. 여..
투 포인터 .[1644] [1. 문제 설명] 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구한다. (N https://testkernelv2.tistory.com/378 소수 리스트를 구할 수 있으므로, 부분 합을 구하면 나머지는 여타 다른 문제들과 비슷하다. head 와 tail 을 옮겨가면서 주어진 자연수가 되는지 확인하는 것이다. [3. 코드]
투 포인터. [1806] [1. 문제 설명] 10,000 이하의 자연수로 이루어진 길이 N 인 수열에서 연속된 부분 합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구한다. [2. 풀이 접근] 먼저 부분 합을 구한다. 연속된 부분 합을 찾기 위한 탐색을 해야 하는데, 자연수로 이루어진 수열의 부분 합은 값이 증가할 수 밖에 없으므로, 여기서는 head 와 tail 을 맨 앞에서 부터 움직이도록 한다. 최초 head 를 고정 시킨 상태에서 tail 을 움직이면서 부분 합이 S 이상이 되는지 확인하도록 한다. S 이상이 된 경우 head 를 움직이도록 한다. head 를 움직인 경우 S 미만이 되면, tail 을 움직이도록 한다. 부분 합은 오름차순으로 되어있기 때문이다. === 실수했던 사항 === 불가능 한 경우 ..
05. 조합 탐색 - 예제2 [1. 문제 설명] m가지의 음식을 준비할 수 있고, n명의 친구를 초대하려고 한다. 각 친구가 먹을 수 있는 음식, 먹을 수 없는 음식이 주어질 때, 각 친구가 먹을 수 있는 음식이 최소한 하나씩 있게 하려면 최소 몇가지의 음식을 해야하는가? [2. 풀이 접근] NP 완비 문제 중 하나로, 다항 시간에 푸는 방법은 아직 없다. 탐욕적 접근 방법으로 가장 많은 사람들이 먹을 수 있는 음식을 만들어 보는 방식으로 접근 할 수 있지만, 모든 입력에 대해 최적해를 찾아낼 수는 없다. 예제) ??? 완전 탐색으로 접근 해서, 간단한 가지치기를 하면 답을 구할 수 는 있지만, 시간 내에 동작하지 않는다. 이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것 이다. 매 재귀 호출마다 아직 먹을 음식이 없는 친구를..
05. 조합 탐색 [1. 개요] 동적 계획법이나 분할 정복 등의 문제 해결 방법을 모든 문제에 적용 할 수 없다. 캐시를 위한 메모리를 너무 많이 사용하거나 적절한 분할 방법이 없는 경우가 존재하기 때문이다. 이 경우 완전 탐색에서 다시 돌아와 생각 해야 한다. 부분 답과 완성된 답의 집합을 탐색공간이라 부른다. 완전 탐새의 수행 시간은 탐색 공간의 크기에 비례한다. 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 조합 탐색이라 부르기로 한다. 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하지 않는다. [2. 가지치기 기법] pruning 기법은 현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 구한 최적해보다 나쁘면 탐색을 더 하지 않는다. 똑똑한 가지치기 기법들은 ..
투 포인터. [2470] [1. 문제 설명] N 개의 정수로 이루어진 수열에서 두 원소의 합이 0에 가장 가까운 원소 한쌍을 오름 차순으로 출력 각 원소의 값은 모두 다르다. [2. 풀이 접근] 수열이 모두 음수로 구성 된 경우, 가장 큰 값 두개를 더하면 되고, 수열이 모두 양수로 구성 된 경우, 가장 작은 값 두개를 더하면 된다. 수열이 양수와 음수로 구성 된 경우는 아래와 같이 접근할 수 있다. 먼저 전체 수열을 오름차순으로 정렬한다. head 와 tail 을 각각 0 과 N-1 로 설정한다. head 와 tail 을 적절히 움직이면서 탐색하는 것이다. 배열에 양 끝쪽에는 절대값이 가장 큰 값들이 온다. head tail 탐색 과정은 아래와 같다. 두 원소의 합이 0이 된 경우는 더 이상 탐색 할 필요가 없다. 그러나, 두..

티스토리툴바