개인사

리뷰 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/17435문제 분류만 보았을 땐 이게 왜 LCA지? 라는 느낌이 들었지만, 친구에게 설명을 듣고 나서 이해가 되었다. 전역 변수MAX_N : 주어지는 함수 내 원소의 최대 개수를 저장할 정수형 상수 변수LOG : 비트단위로 부모를 탐색할때 사용할 정수형 상수 변수m, q : 주어진 원소의 개수를 저장할 변수 m, 쿼리의 개수를 저장할 변수 qn, x : 함수를 반복할 회수를 저장할 변수 n, 함수의 초깃값에 넣을 원소의 번호 xpar : 각 원소의 2^n번째 부모 원소를 저장할 2차원 배열, MAX_N * LOG 크기로 저장한다. 함수1. preprocessvoid preprocess() par배열을 초기화 하기 위한 함수각 원소의 par배열..

리뷰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/2871 전역 변수n : 주어진 문자열의 길이v : 현재 상황에서 문자열이 존재하는지 체크하기 위한 배열 크기는 최대 문자열 크기인 10만으로 초기화 한다.s, t1, t2 : 입력되는 초기 문자열 s, 상근이의 문자열 t1, 희원이의 문자열 t2Prio : 원하는 단어를 얻기 위한 우선순위 큐용 구조체pq : 희열이가 사용할 우선순위 큐, 문자 기준 오름차순, 같다면 인덱스 기준 내림차순 정렬을 하였다. 함수없음  문제풀이n과 s값을 입력받은 뒤 0부터 n - 1까지 순회해준다.v배열을 모두 1로 변경해 주고 pq에는 문자와 해당 문자의 인덱스를 추가해 준다.상근이가 문자열을 가..

리뷰 트라이를 사용해 유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구하는 문제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..

리뷰 업데이트를 통해 세그먼트 트리를 확장하고 구간합을 구하는 문제https://www.acmicpc.net/problem/3653 전역 변수tc, n, m : 테스트 케이스의 개수 tc, 각 테케의 DVD의 수 n, 각 테케의 쿼리의 수 mlst : DVD의 초기정보와 인덱스 정부를 담은 정수형 벡터tree : 세그먼트 트리의 구간합 정보를 담은 정수형 벡터 함수1. updatevoid update(int node, int s, int e, int idx, int val) 세그먼트 트리의 특정 인덱스의 값을 교체하고 구간합을 업데이트 하는 함수val은 1과 -1이 올 것이며 음수가 올 경우는 주어지지 않는다. 2. queryint query(int node, int s, int e, int L, int..