본문 바로가기

분류 전체보기

 (689)
리눅스 CMake 설치 [1. 개요] centos:7 기준으로 cmake 설치 혹은 업데이트 방법 정리 [2. yum 을 이용한 설치] yum search cmake yum install -y cmake cmake --version yum 이용한 설치 시 cmake version 은 2.8.12.2 최신 버전의 cmake를 설치하려면 아래와 같은 단계를 수행] [3. cmake 최신 버전 설치] github cmake repository 에서 바이너리를 가져와 설치 wget https://github.com/Kitware/CMake/releases/download/v3.25.1/cmake-3.25.1-linux-x86_64.tar.gz tar -zxf cmake-3.25.1-linux-x86_64.tar.gz cd cmake-..
분할 정복. [1725] [1. 문제 설명] https://www.acmicpc.net/problem/1725 [2. 풀이 접근] 기타 참고 자료 https://testkernelv2.tistory.com/248 [3. 코드]
분할정복. [2261] [1. 문제 설명] https://www.acmicpc.net/problem/2261 [2. 풀이 접근] 주의 사항 중복되는 점을 제거해서는 안된다. => 같은 점이 있다고 했을 때, 모든 점들 간 최소 거리는 0 이 되는 것이 맞기 때문이다. => 중복되는 점을 제거하면 이러한 경우는 찾을 수 없다. 분할 정복 및 스위핑으로 접근해야 한다. 먼저 분할 정복을 사용하는 이유이다. x 를 기준으로 정렬 후, 모든 경우의 수를 찾는 다면, 그 시간 복잡도는 O(N2) 이므로 시간 내 풀 수 없다. 분할 정복 패턴을 적용한다. => 재귀로 구현하므로 기저 사례를 먼저 작성한다. => 기저 사례는 [head, tail] 구간의 길이가 2인 경우, 즉 두 개 의 점간 거리를 반환한다. => head ~ mid 구..
Ansible 설치 및 기본 개념 [1. 개요] 모두 리눅스 서버인 환경을 가정하고, centos 에서 ansible 설치 방법을 정리한다. 전체 서버를 관리하는 서버에만 설치하며, (이하 controller) 명령을 받는 agent 역할인 서버에는 ssh-server 와 python 만 설치되어 있으면 된다. [2. 설치 과정] # yum install -y epel-release # yum repolist # yum install -y ansible $ ansible --version $ ansible-playbook --version controller 에서 각 agent 머신에 자신의 ssh-key 를 등록 할 필요가 없다. agent 접속을 위한 ssh 계정과 패스워드를 작성하기 때문이다. [3. ansible 구조] ansib..
완전 탐색. [1759] [1. 문제 설명] https://www.acmicpc.net/problem/1759 [2. 풀이 접근] 핵심 포인트 재귀 구현 패턴을 따른다. 기저 사례 처리 => 기저 사례에서, 완성된 한가지 조합이 답이 될 수 있는지 체크 => 종료 (성공 여부 리턴...) 이번 index 를 선택하지 않는 경우 이번 index 를 선택하는 경우 => 이번 선택을 vector 에 push_back() => 재귀 호출 => 재귀 호출 종료 후, vector 에서 pop_back() 입력으로 주어진 문자 배열을 먼저 정렬한다. 정렬 여부 조건을 기저사례에서 체크 할 필요가 없다. 기저 사례에서 완성 된 조합을 정렬하는 작업이 필요하다. 재귀 호출하여 완전 탐색에서 발견된 정답 데이터는 stack 에 저장하도록 한다. ..
완전 탐색. [2309, 1182] [1. 문제 설명] https://www.acmicpc.net/problem/2309 https://www.acmicpc.net/problem/1182 [2. 풀이 접근] 이번 문제는 재귀를 이용한 전형적인 완전 탐색 문제이다. 여기서는 재귀 구현 방식에 대한 내용을 정리한다. 개인적으로 재귀를 이용한 완전 탐색 구현 시 코드는 아래 두가지 패턴이 있다고 생각한다. 반복문 없이 재귀를 여러번 호출 반복문 내부에서 재귀를 호출 단, 두 패턴 사용은 상황에 맞게 적절히 사용해야 한다. 먼저은 1182 풀이이다. 여기서는 1번 패턴으로 작성한 코드만 통과한다. 2번 패턴이 틀린 이유는 코드 구조 상 마지막 원소만 선택되지 않은 경우를 체크 할 수 없기 때문이다. index == N-1 인 경우에 재귀 호출을 ..
SCC 관련 솔루션 [1. 개요] SCC 의 특성 방향 그래프에서 정의 된다. 같은 SCC 에 속한 노드들은 Cycle 을 형성한다. => 같은 SCC 에 속한 노드 간 경로는 반드시 존재한다. SCC 를 연결하는 간선들을 모으면 DAG 를 형성한다. SCC 를 응용한 문제 SAT SCC 를 찾는데 사용되는 알고리즘은 아래와 같이 크게 두가지가 있다. 타잔 알고리즘 => 시간 복잡도 O(V+E) 코사라주 알고리즘 타잔 알고리즘은 한번의 DFS 를 통해 모든 SCC 를 찾을 수 있다. 따라서 타잔 알고리즘의 구현 패턴을 익히도록 한다. dfsAll 을 수행한다. 각 dfs 는 프로토 타입은 아래와 같이 작성하며, 동작은 아래와 같다. # int dfs(u int), u 에서 dfs 수행 시 가장 먼저 방문 한 방문 순서를 반..
SCC. [2152] [1. 문제 설명] https://www.acmicpc.net/problem/2152 [2. 풀이 접근] 아래 문제와 유사하다. https://testkernelv2.tistory.com/445 이 문제에서 헷갈릴만한 부분을 몇가지 정리하면 아래와 같다. S 에서 시작해서 T 에서 끝나야 한다. => 만약, S 와 T 가 같은 SCC 에 있다고 했을 때, S ~~~> T ~~~> Z 로 갈 수 있다고 했을 때, Z 를 경유하지 않고 T 에서 끝나야 하는가? 1번 질문에 대해서 Z 경유 없이 T 에서 끝내야 한다면, 문제가 까다로워 질 수 있다. 같은 SCC 내에서 S 에서 T 까지 최대한 많은 도시를 경유해야하는 문제를 또 풀어야 하기 때문이다. 그러나 문제에서 같은 도시를 여러 번 방문 할 수 있다고 ..
최소공통조상. [1761] [1. 문제 설명] https://www.acmicpc.net/problem/1761 [2. 풀이 접근] 구해야 하는 노드 쌍의 개수가 1개라면, 단순한 접근으로 풀 수 있지만, 최대 1만개의 노드 쌍의 거리를 구해야 하므로, 단순한 접근으로는 시간 초과 발생이 매우 높다. 트리가 한쪽 방향으로 스큐되어 있다고 생각해보면, Leaf 에서 Root 까지 올라갈 때, 하나의 노드쌍에 대해서 O(H) 걸림 쿼리 개수는 총 M 개 단순한 접근 시 전체 시간복잡도는 O(HM) => H 는 최대 4만, M 은 최대 1만, 즉, LCA 를 구할 때, 좀 더 빠른 방법으로 구해야 한다. Sparse table 을 전처리 과정에서 구한 뒤, LCA 를 찾아가고, 그 과정에서 이동 거리를 구한다면, 쿼리 하나 당 거의 상..
최소 공통 조상 솔루션 [1. 개요] 최소 공통 조상 문제는 보통 트리에서 임의의 두 노드가 있을 때, 두 노드의 공통 조상을 찾는 문제이다. 트리를 대상으로 하기 때문에, 어떤 노드의 부모노드는 단 하나 만 존재하게 된다. 최소 공통 조상을 찾는 방법은 아래와 같다. 모든 노드의 Height 를 먼저 계산한다. 두 노드의 높이를 맞춘다. 두 노드가 서로 같아 질 때 까지 위로 올라 간다. => 최대 root 까지 갈 수 있다. 먼저 height 를 계산해야 한다. root 노드를 선택한다. => root 노드는 임의의 아무 노드나 선택해도 된다. => 그 이유는 아래 그림 참조 root 노드로 부터 DFS 와 같은 그래프 탐색을 이용하여, 모든 노드를 방문한다. 이 과정에서 각 노드의 height 를 계산 할 수 있다. 위 ..

티스토리툴바