본문 바로가기

분류 전체보기

 (333)
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-omakase/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 시간 제한: 1500ms 1 ≤ name 의 길이 ≤ 30 name 은 소문자 알파벳으로만 이루어져 있습니다. 5비트 * 30 = 150비트.. 이건 아닌거 같으니까 그냥 unordered_map 써서 해싱하자. 최대 100000개의 명령이 주어진다. 3 ≤ L ≤ 1,000,000,000 배열의 길이가..
토끼와 경주 https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이동하는 도중 그 다음 칸이 격자를 벗어나게 된다면 방향을 반대로 바꿔 한 칸 이동하게 됩니다. 어떻게 처리할까? 이 문제로 정확하게 알고 넘어가자! 일단 모듈러 연산을 한다. (얼마나 가야지 같은 방향 & 제자리로 가는가?) go_down -> 아래, 위, 아래 내려가는 것의 최댓값은 (n - rabbit..
어항 정리 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 빡 구현 문제 문제를 읽으면서 쭉 따라가보자. 제한조건을 보면 숫자가 매우 작고 시간도 넉넉하다 O(N^2) 충분히 될 것 같다. (다른 쓸 알고리즘이 없기도 하다.) 다른 블로그들 코드 보면 배열 돌리기를 사용하던데 나는 그냥 직관적으로 구현을 했다. 1. 틀 짜기 우선 구조체를 만들었다. fishbowl 구조체는 cnt -> 위로 올라가는 어항 개수 arr -> 물고기 수 어항이 4개라면 5 ..
코드트리 메신저 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..
공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 도킹 set::iterator it = s.find(t); 값이 있다면 -> s.erase(it); 값이 없다면? lower_bound 불가능한 경우 2가지 1. t 보다 큰 값의 위치가 s.begin() 2. t 보다 큰 값의 위치의 앞이 t 보다 큼 *(--it) > t 1 2 3 4 5 6 7 8 9..
검색 엔진 2 보호되어 있는 글입니다.

티스토리툴바