본문 바로가기

분류 전체보기

 (747)
이분탐색. [2467] [1. 문제 설명] https://www.acmicpc.net/problem/2467 [2. 풀이 접근] 용액을 하나 정한다. 전체에 대해서, 이 용액과 더해서 그 합이 0에 가장 가까워 지는 용액을 이분 탐색으로 찾는다. 용액들이 이미 정렬 된 상태이므로, 이분 탐색 시 두 용액의 합이 0보다 작다면 # 양수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 (mid ~ hi] 구간을 잡아야 한다. 0보다 크다면 # 음수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 [lo ~ mid) 구간을 잡아야 한다. [3. 코드]
이분탐색. [1253] [1. 문제 설명] https://www.acmicpc.net/problem/1253 [2. 풀이 접근] 풀이 시 주의 할점 std::lower_bound 에 대응되는 sort.Search() 는 하한 값 중 가장 먼저 오는 index 를 반환한다. 중복된 값에 대해서도 확인이 필요한 경우, upper_bound 에 해당하는 index 까지 구할 필요가 있다. 즉, [lo, hi) 까지 순차적으로 확인 해 볼 필요가 있다. 시간 복잡도는 O(N^2 logN) 인데, N 의 최대가 2,000 이므로, 현실적인 시간 내에 해결 가능하다. [3. 코드]
최장 증가 부분 수열. [12738] [1. 문제 설명] https://www.acmicpc.net/problem/12738 [2. 풀이 접근] LIS 관련 문제 접근은 보통 아래와 같은 방식으로 진행한다. 완전 탐색 동적 계획법 (완전 탐색에서 부분 문제에 대한 메모이제이션 적용) 완전 탐색 접근법은 아래와 같다. 수열 A[0] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 수열 A[1] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 수열 A[2] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 이런 방식을 수열의 끝까지 적용하면 구할 수 있으나, 시간복잡도가 O(2^N) 가 되므로, 길이가 1백만 이상인 수열에 대해서는 현실적인 시간내에 구할 수 없다. 다만 여기서 중복문제가 있다는 것을 인지하면, 메모이제이션을 적용하여 조금 더 빠..
정렬. [10825] [1. 문제 설명] https://www.acmicpc.net/problem/10825 [2. 풀이 접근] 전체 데이터를 구조체 형태고 감싸서 해당 배열을 정렬하는 방식으로 구현 할 수 있지만, 이렇게 할 경우, 불필요한 복사가 발생 하게 된다. 각 데이터를 순서대로 입력받아 각각의 배열에 저장하고, 각 배열 내 데이터를 가리키는 인덱스 배열을 생성한다. 이 인덱스 배열을 정렬하여 구현하도록 한다. [3. 코드]
비트마스킹. [1062] [1. 문제 설명] https://www.acmicpc.net/problem/1062 [2. 풀이 접근] 단어를 읽기 위해서는 적어도 a,n,t,i,c 총 5개의 문자는 가르쳐야 한다. 즉, k-5 개를 가르쳐서, 읽을 수 있는 단어 개수를 최대로 해야한다. 단어에 나오는 문자 위주로 탐색해본다. z 를 포함하는 단어가 없다면, 굳이 z 를 가르칠 필요는 없다. 또, 가장 많이 나오는 문자를 가르쳐서는 안된다. zb q zb 일 때, 한 문자만 가르칠 수 있다면, q를 선택하는게 더 낫다. 조건 중, 단어의 길이는 최대 15 이 중, 5개 문자가 필수 이므로, 최대 10 10개중 선택할 수 있는 경우의 수 중 최대는 대략 10 combination 5 현실적인 시간 내에 모든 경우를 확인 해볼 수 있다...
비트연산 [1. 개요] golang 에서 bit 연산 방식을 정리한다. [2. 문제] https://www.acmicpc.net/problem/11723 [3. 특이점] bit 를 반전 시킬 때, C++ 에서는 ~ 연산자를 사용하였는데, go 에서는 ^ 를 사용해야 한다. [4. 코드]
완전 탐색. [15686] [1. 문제 설명] https://www.acmicpc.net/problem/15686 [2. 풀이 접근] 각 치킨 집에 대해서 해당 지점을 폐업하는 경우와 폐업하지 않는 경우에 대해서 완전탐색을 수행한다. 탐색 중, 남은 치킨 집 개수가 M 개 일 때, 도시의 치킨 거리를 구하며, 남은 치킨 집 개수가 M 개가 아닌데, 더 이상 확인해 볼 치킨 집이 없다면, MAX 값을 반환하도록 한다 [3. 코드]
동적계획법. [9461] [1. 문제 설명] https://www.acmicpc.net/problem/9461 [2. 풀이 접근] 완전 탐색에서 시작한다. 중복되는 부분문제를 파악한다. 메모이제이션을 적용한다. 위 그림에서 가운데 길이가 1인 정삼각형을 P(1) 그 왼쪽 정삼각형을 P(2) P(2) 의 위쪽 정삼각형을 P(3) 로 정의하고, 나선 방향으로 식을 정리하면 아래와 같게 된다. p(1) = 1 p(2) = 1 p(3) = 1 p(4) = p(3)+p(1) = 2 p(5) = p(4) = 2 p(6) = p(5)+p(1) = 3 p(7) = p(6)+p(1) = 4 # p(1)==p(2) p(8) = p(7)+p(3) = 5 p(9) = p(8)+p(4) = 7 p(10) = p(9)+p(5) = 9 p(11) = p(..
File encoding [1. 개요] 윈도우 환경에서 파일의 인코딩을 변경하여 저장하는 명령어 사용법을 정리한다. [2. 명령어] 파워 쉘 환경에서 사용 할 수 있는 Set-Content 라는 명령어가 있다. 예제) Get-Content example.txt | Set-Content -Encoding utf-8 example2.txt # example.txt 파일에 저장 된 내용을, utf-8 로 인코딩 하여, example2.txt 에 저장한다.
볼륨, 영구 볼륨, 영구 볼륨 클레임 볼륨 emptyDir hostPath downwardAPI projected nfs iscsi cephfs emptyDir 특징 pod 용 임시 디스크 영역 pod 종료 시 삭제 된다. host 의 임의 영역을 마운트 할 수 없음. 리소스 제한이 가능하며, 초과 사용 시 pod 가 축출(Evict) 된다. # emptyDir.sizeLimit: 128Mi tmpfs 로 할당 가능하다. 역시 초과 사용 시, OOM 이 발생하여 pod 가 정지 된다. # emptyDir.medium: Memory hostPath node 의 영역을 컨테이너에 마운트 한다. host 의 어떤 영역을 사용할 지 지정해야 한다. # Directory, DirectoryOrCreate, File, Socket, BlockDevic..

티스토리툴바