본문 바로가기

트리

 (26)
색깔 트리 https://www.codetree.ai/training-field/frequent-problems/problems/color-tree/description?page=1&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai트리 문제다트리 구현은 배열로 한다. 색깔 변경특정 노드 mid​ 를 루트로 하는 서브트리의모든 노드의 색깔을 지정된 색 color 로 변경합니다.최대 50000번 주어진다..이걸 dfs로 구현하면 무조건 시간 초과나겠지. 점수 조회깊이가 최대 20000인데이걸 dfs를 다 한다는건무조건 시간 초과 날 거 같다. 색이 변..
전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이에 전화번호들을 다 넣고 find를 하는 과정중에 isEnd가 true라면 false 반환 -> "NO" 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5..
휴대폰 자판 https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 구현하고 문제 조건 따라 디버깅 해가면서 풀면 된다. 각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력한다. fixed
XOR (Top-down) https://www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net XOR이란? 1 0 0 1 만 1이고 나머지는 0 XOR은 교환 법칙이 성립한다. 스위치 문제와 유사한듯 다르다. 스위치 문제에서는 lazy 배열의 값을 확인했다. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 만약 구간 업데이트의 크기가 짝수라면 k가 짝수번 XOR 되면 0이 되어 값이 그대로 유지된다. 즉, end - s..
스위치 https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 구간합 lazy propagation에서 조건을 심화한 문제이다. 1. 하나는 A번부터 B번 사이의 스위치 상태를 반전 -> 범위를 교체 lazy propagation 스위치 n개는 처음에는 다 꺼져있으므로 세그먼트 트리를 make 할 필요 없다. tree.resize(tree_size) 하면 0으로 초기화 되니까! 세그먼트 트리에는 구간마다 켜져있는 스위치..
코드트리 메신저 https://www.codetree.ai/training-field/frequent-problems/problems/codetree-messenger/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 처음에는 가장 간단하게 DFS 구현을 해보았다.최대 깊이가 20이어서 시간 초과 났다. 그 다음에는 노드에 cnt를 주고init() 할 때 Bottom-up으로 권한에 따라서 cnt를 증가시키고 문제를풀려고 해보았다.부모 교환 -> LCA처럼 같아질 때까지 부모도 같게 만든다.권한 변환 -> 변환하고 B..
상품권 배분 보호되어 있는 글입니다.
물품보관 보호되어 있는 글입니다.

티스토리툴바