본문 바로가기

분류 전체보기

 (689)
접미사 배열 - 예제1 [1. 코드]
문자열 - 접미사 배열 [1. 개요] 접미사 배열은 굉장히 다양한 문자열 문제를 푸는 데 사용 할 수 있으며, 이 자료구조는 아래와 같은 데이터를 표현한다. 어떤 문자열 S 의 모든 접미사를 사전순으로 정렬 이때, 배열에 실제로 저장하는 것은 각 접미사의 시작 위치이다. 예를들어, A[i] = 7 일 때, S[7...] 을 표현하는 것이다. 그래서 이 자료구조를 이용하여 아래와 같은 문제를 해결 할 수 있다. 문자열 검색 찾고자 하는 "문자열 N" 이 "문자열 H" 의 어떤 접미사의 접두사라는 점을 이용한다. H 의 접미사 배열을 이진 탐색하여, 문자열 N 이 출현하는 위치를 찾을 수 있다. [2. 접미사 배열 생성] 접미사 배열을 생성하는 가장 단순한 방법의 시간복잡도는 O(n^2logn) 으로, 일반적인 경우에서는 이 보다..
우선순위 큐. [7662] [1. 문제 설명] https://www.acmicpc.net/problem/7662 [2. 풀이 접근] map 을 이용한 풀이와 우선순위 큐를 이용한 풀이가 있다. map 을 이용한 풀이 STL map 은 begin(): 최소, rbegin(): 최대가 됨을 이용한다. 우선순위 큐를 이용한 풀이 주의 점, min_int 에 - 부호 사용 시 overflow 발생으로 인한 오답 발생 -std::numeric_limits::min() max() 는 오버플로우 발생 안함... [3. 코드 - map] [3. 코드 - 우선순위 큐]
문자열 - kmp 알고리즘 [1. 개요] 문자열 검색 문제 문자열 H 가 문자열 N 을 부분 문자열로 포함하는지 확인 포함한다면, N 과 일치하는 부분 문자열의 시작 위치를 찾는 문제 N 이 H 에서 여러 번 출현한다면, N 이 출현하는 모든 위치를 반환해야 한다. 단순한 탐색 알고리즘의 경우 시간 복잡도는 O(|N| x |H|) 로, 입력되는 문자열의 길이가 매우 긴 경우(그리고 특정 형태의 입력에 대해서), 꽤나 비효율적인 알고리즘 이지만, 현실적인 경우에서 그런 경우는 흔하지 않다. KMP 알고리즘은 검색 과정에서 얻는 정보를 버리지 않고 활용하여, 동일한 문제에 대한 시간복잡도를 O(|N| + |H|) 로 상당히 개선할 수 있다. [2. 알고리즘 원리] KMP 알고리즘의 아래와 같은 특성을 이용한다. H[i...] 에서 N..
window app 작성 시 유의 할 점 [1. 개요] Winsock 프로그래밍에서 32bit 로 빌드하다가 64bit 로 빌드 시 유의할점을 정리한다. window thread 관련 주의 사항 [2. SOCKET type] SOCKET 자료형 32bit 에서는 4byte unsigned 정수형 64ibt 에서는 8byte unsigned 정수형 단순히 SOCKET 을 사용한 입출력은 크게 문제가 되지 않지만, 내부 구현등으로 인해 bit mask 를 통해 다른 데이터와 bit 연산을 통해 값을 전달 하는 경우 문제가 될 수 있다. [3. Thread] __beginthreadex() 등으로 thread를 생성하고 반환되는 핸들은 반드시 닫아주어야 하는데, 생성한 thread 종료 후 닫아줄 필요는 없다. 스레드가 정상적으로 생성되었음을 알았다..
우선순위 큐. [1202] [1. 문제 설명] https://www.acmicpc.net/problem/1202 [2. 풀이 접근] 카테고리는 우선순위 큐를 이용해서 푸는 방법이지만, map 을 이용해서 풀 수 도 있다. map 을 이용한 풀이 기본적인 전략은 아래와 같다. 훔친 보석의 가격을 최대로 해야 하므로, 보석 가격 순을 내림차순 정렬 후, 하나 씩 가져가는 방식이다. 이 때, 보석 무게가 도둑이 갖고 있는 가방 들 중 어느 하나에 포함될 수 있어야 한다. 이 때 이분 탐색을 위해, 가방 무게 역시 오름차순으로 미리 정렬 되어 있어야 한다. 그래서 보석을 기준으로 iterate 하면서 보석을 선택적으로 취해 나가는 것이다. 단) 여기서 아래와 같은 문제가 있다. 이번 보석을 어느 가방에 넣었으면, 이 가방은 다음 탐색에서..
트리-DP. [1949] [1. 문제 설명] https://www.acmicpc.net/problem/1949 [2. 풀이 접근] 처음에는 완전 탐색 형식으로 풀어보고, 메모이제이션 해서 최적화 하는 방법으로 접근해보려 했는데, 이 때, 문제에서 조건 중 3번 조건을 다루기가 많이 까다로웠다. root 가 선택되지 않았을 때, 적어도 하나의 자식은 우수 마을로 선정되어야 한다. 자식 노드의 개수가 4 개일 때, 전체 경우의 수는 (2^4-1) 개 이다. # 전체 경우의 수에서, 모두 우수 마을이 아닌 경우를 뺀 개수 자식 노드의 개수가 늘어나면 지수 형태로 경우의 수가 늘어나므로, 적절한 풀이가 아니다. 찾아보니 일반적인 풀이는 아래와 같다. 부분 문제를 다음과 같이 정의 # 어떤 노드를 root 로 하는 서브 트리에서 최대 주..
pod stuck [1. 개요] pod 생성 시, status 가 계속 ContainerCreating 인 경우 describe 로 pod 상태 확인 시, cni.0 ~~ ip 문제 인 경우 이런 상황에서 해결 방법? [2. 원인] CNI 플러그인으로 flannel 설치 시에도 문제가 되었던 부분이 있었는데, host 상에 ifconfig 로 네트워크 인터페이스에 할당 된 ip 주소 범위가 겹치는 경우 주로 발생했음 kubectl get services 에서 service/kubernetes 의 Cluster-ip : 10.96.0.1 일 때, --pod-network-cidr 및 kube-flannel.yml 에서 ip 주소 대역을 10.96.0.0/16 으로 명시한 경우 [3. 해결책] Docker 및 쿠버네티스 설치..
트리. [2533] [1. 문제 설명] https://www.acmicpc.net/problem/2533 [2. 풀이 접근] 문제 조건에서 주어지는 그래프는 트리 형태이다. 어떤 노드에서 인접한 모든 노드가 얼리 어답터일 때만, 이 노드 역시 얼리어답터가 될 수 있다. leaf 노드인 경우, 이 노드가 얼리어답터가 될 수 없다. 트리에서 노드는 최소 2개 이상이다. Left - Root - Right 인 구조에서, Left 를 얼리어답터로 선정한다면, Right 역시 얼리어답터로 해야한다. => Root 만 얼리어답터로 선정하는 것이 더 낫다. 그래서, Leaf 노드 역시 얼리어답터가 되려면, Leaf 에 유일하게 연결되는 Parent 가 얼리어답터가 되어야 한다. Leaf 및 parent 를 얻기 위한 트리 구성 임의의 ..
트리. [2250] [1. 문제 설명] https://www.acmicpc.net/problem/2250 [2. 풀이 접근] [3. 코드]

티스토리툴바