개인사

리뷰 https://www.acmicpc.net/problem/4803싸이클이 발생했다는 것에 대한 재정의를 하게 된 문제  전역 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수ans : 트리의 개수를 저장할 변수v : 각 노드의 방문 처리를 하기 위한 정수형 배열  함수1. bfsbool bfs(int sn, const vector>& lst) 너비 우선 탐색을 통해 싸이클 존재 여부를 판단하기 위한 함수매개 변수로 시작 노드와 인접 리스트를 전달 받는다.정수형 타입 큐 q를 초기화 하고 시작 노드를 큐에 삽입해 준다.시작 노드를 1로 방문처리 해주고, 트리 여부를 판단할 bool 형식의 변수 isTree를 true로 초기화 한다.큐가 빌 때 까지 탐색을 진행하고 큐의 제일 앞에 ..

리뷰 https://www.acmicpc.net/problem/13505최대 10만로 주어지는 N개의 수 중 두개의 수를 XOR연산 했을때 가장 큰 값을 찾는 문제알고리즘 분류에 트라이라고 명시되어있지 않았다면 절대 트라이로 접근 못했을 것 같다. 전역 변수LOG : 입력으로 주어지는 수 최대 10억을 비트로 자릿수를 계산하기 위한 정수형 상수 변수n : 입력으로 주어지는 숫자의 개수를 저장할 변수ans : 두 수의 XOR한 결과 중 가장 큰 값을 저장할 변수Trie : 트라이를 통해 비트로 구성된 트리를 관리하기 위한 구조체 함수1. Insertvoid Insert(Trie* node, const string& str) 1, 0으로 이루어진 문자를 트리에 삽입하는 함수매개변수로 root의 노드 node..

리뷰 https://www.acmicpc.net/problem/1167간선의 가중치가 있는 트리에서 두 노드의 거리가 가장 큰 길이를 구하는 문제 전역 변수n : 노드의 개수를 저장할 정수형 변수far_node : 첫 번째 dfs를 수행했을 때 가장 먼 거리를 가진 노드의 번호를 저장할 정수형 변수max_dist : 각 dfs마다 가장 먼 거리를 식별하기 위한 정수형 변수v : 깊이 우선 탐색을 할때 방문 처리를 확인하기 위한 정수형 배열, 크기는 100001로 초기화 한다.Edge : 노드의 자식과 간선의 가중치를 저장하기 위한 구조체edges : 각 노드의 인접리스트를 저장하기 위한 Edge타입 벡터, 크기는 100001로 초기화 한다. 함수1. dfsvoid dfs(int node, int dist..

리뷰 https://www.acmicpc.net/problem/15480LCA의 심화 문제, 루트가 매번 바뀔때마다의 처리하는 아이디어에 배우게 된 문제였다. 전역 변수MAX_N : 정점의 최대 개수를 저장할 정수형 상수 변수LOG : DP에서 2의 N승으로 빠르게 탐색하기 위해 사용할 정수형 상수 변수n, m : 문제에서 주어진 정점의 개수 n, 쿼리의 개수 mdepth : 각 노드의 초기 깊이를 저장할 정수형 배열, 크기는 MAX_N으로 초기화parents : 각 노드의 부모 정보를 저장해 둔 정수형 배열, 크기는 MAX_N * LOG로 초기화lst : 각 정점간의 간선을 인접리스트로 저장할 정수형 벡터, 크기는 MAX_N으로 초기화 함수1. dfsvoid dfs(int node, int par, i..

리뷰https://www.acmicpc.net/problem/14288오일러 경로 테크닉을 구한 인덱스를 기준으로 세그먼트 트리를 양 방향으로 업데이트를 진행하며 구간합을 구하는 문제 전역 변수MAX_N : 직원의 최대 수를 저장할 정수형 상수 변수n, m : 직원의 수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 mup_tree : 상사 방향으로 칭찬값을 저장할 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4down_tree : 부하직원 방향으로 칭찬값을 저장할 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4lazy : 세그먼트 트리에 갱신될 업데이트 값을 저장할 배열, 크기는 MAX_N * 4lst : 각 직원간의 상하 관계를 인접리스트 형태로 저장할 정수형 벡터 배열, 크..

리뷰 오일러 경로 테크닉으로 세그먼트 트리의 노드를 재정의 하고 누적합을 구하는 문제https://www.acmicpc.net/problem/14287 전역 변수MAX_N : 직원의 최대 개수를 저장할 정수형 상수 변수n, m : 직원의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 mtree : 세그먼트 트리 정보를 담은 정수형 배열, 크기는 MAX_N * 4로 초기화lst : 오일러 경로 테크닉에 사용할 인접 리스트, 정수형 벡터 타입으로 크기는 MAX_N으로 초기화it : 오일러 경로에서 각 직원의 탐색 시작 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화ot : 오일러 경로에서 각 직원의 탐색 종료 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화timer : ..

리뷰 구간 대체 업데이트, 구간 합, 느린 갱신, 오일러 경로 테크닉을 활용해야 하는 문제https://www.acmicpc.net/problem/18437 전역 변수n, m : 직원의 수 n, 쿼리의 수 mMAX_N : 주어지는 n값의 최대치를 나타낼 정수형 상수 변수, 100001로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화lazy : 세그먼트 트리 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화path : 부하 직원을 인접리스트로 저장할 정수형 벡터, MAX_N크기로 초기화it : 서브 트리에서 해당 노드에 진입한 시간을 기록할 정수형 배열, MAX_N크기로 초기화ot : 서브 트리에서 해당 노드에서 빠져나온 시간을 기록할 ..

리뷰 트라이를 사용해 유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구하는 문제https://www.acmicpc.net/problem/16934 전역 변수Trie : 트라이를 구현할 구조체 동일한 닉네임이 들어올 수 있으므로 cnt라는 변수를 업데이트 해줘야 한다.root : 트라이의 루트를 나타낼 Trie타입 구조체n : 입력 받을 게임 닉네임의 개수 함수1. insertvoid insert(Trie* node, const string& str) 트라이에 게임 닉네임을 입력하고, 별칭을 출력해 주는 함수함수 호출 시 flag를 통해 별칭을 출력했는지 여부를 체크해 준다. 기본값은 1이다.입력 받은 문자열을 순회하며 다음 노드가 있는지 체크해 준다.만약 다음 노드가 존재하지 않을 시 ..

리뷰 개미굴과 유사한 부분이 많은 문제인듯 하다. 하지만 개미굴과 달리 공백이 아닌 역슬래시로 문자열을 구분https://www.acmicpc.net/problem/7432 전역 변수n : 디렉토리 전체 경로의 개수Trie : 맵을 사용하여 디렉토리 정보를 트라이로 사용할 구조체 함수1. insertvoid insert(Trie* node, const vector& strs) 트라이에 디렉토리 문자열을 추가할 함수입력할 디렉토리 이름을 벡터형식으로 입력 받는다.루트노드에서 부터 시작하여 각 문자열을 하위 요소에 넣어준다.만약 처음으로 정의된 디렉토리인 경우 새롭게 할당해주고 이동하는 작업을 해준다. 2. dfsvoid dfs(Trie* node, int level) 깊이 우선 탐색을 통해 디렉토리 정보를..

리뷰 접두사가 동일한 전화번호가 있는지 찾고, 있으면 YES를 없으면 NO를 출력하는 문제https://www.acmicpc.net/problem/5052 전역 변수tc, n : 테스트케이스의 개수 tc, 각 테케마다 입력되는 전화번호의 개수 nlst : 각 테케마다 입력된 문자열을 저장할 문자열 타입 배열, 최대 1만으로 크기를 설정한다.Trie : 트라이를 구현할 구조체, 숫자열 문자를 받아오므로 child의 크기는 10으로 설정한다. 함수1. insertbool insert(Trie* node, const string& str) 트라이에 새로운 전화번호를 넣는 함수전화번호를 넣는 도중 접두어가 있는지 체크까지 해주어야 한다.만약 접두어가 있다면 탐색을 그만하고 NO를 출력해 주어도 된다. 문제풀이t..