solved.ac 티어 : 플래 3 www.acmicpc.net/problem/14288 14288번: 회사 문화 4 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다. BOJ 14268(회사 문화 2)풀이 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번..
solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/14287 14287번: 회사 문화 3 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 다른 회사 문화 문제와는 다르게 위에서 아래로 값을 더해주는 것이 아닌 밑에서 위로 값을 더해주는 문제이다. 이 문제의 풀이는 생각보다 간단하다. dfs으로 새로 해당 구간을 만들고 그 구간에 대한 이진트리를 그리고 x노드의 값에 w를 더한다고 해보자. 그러면 x를 가지고 있는 구간에만 변경이 생긴다. 그러므로 구간이 (x,x)인 위치에 w를 더해주면 x를 포..
solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18407 18407번: 가로 블록 쌓기 가로 블록만 등장하는 테트리스 게임을 해보려고 한다. 가로 블록은 총 N개가 등장할 예정이고, 등장하는 순서대로 1, 2, ..., N번이다. i번 블록의 높이는 1이고, 너비는 Wi이다. i번 블록은 왼쪽 벽 www.acmicpc.net 새로 떨어지는 블록은 자신의 구간에서의 최댓값+1이다. 그러므로 세그레이지로 max를 구해주고 max+1 값을 구간에 저장해준다. 그리고 max값이 최대 높이일 경우 최대 높이를 올려준다음 마지막에 나온 최대 높이를 출력해주면 된다. #include using namespace std; typedef long long ll; struct qu{ ll ..
solved.ac 티어 : 다이아 4 www.acmicpc.net/problem/16910 16910번: mex와 쿼리 mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 자연수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, mex([1,5,2,1,5,2,1,2]) = 3이다. 비어있는 배열 A와 쿼리 N개가 주어졌을 때, www.acmicpc.net 생각보다 간단한 세그레이지이다. 1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다. 2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다. 3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서,..
solved.ac 티어 : 플래 4 www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제도 보자마자 버거운 버거라 응요이라는 거를 알 수 있다 그렇기 때문에 이것도 버거운 버거를 풀면 날먹이다. 이문제는 변경이 없는 대신 올바른 괄호 문자열인지 확인하는 것이 입력으로 주어진다. 그러므로 변경 부분을 지우고 입력을 받은 값을 구간에 넣어주면 끝이다. #include #include using namespace std; typedef long lo..
solved.ac 티어 : 플래 2 www.acmicpc.net/problem/17407 17407번: 괄호 문자열과 쿼리 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제는 딱 봐도 버거운 버거랑 비슷한 문제이다. 버거운 버거를 풀고 오면 거저로 얻는 문제이다. 버거운 버거:joseph0528.tistory.com/8 BOJ 19851(버거운 버거)풀이 세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무..
solved.ac 난이도 :플래 3 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(^)로 바꿔주면 된다. 하지만 이렇게만 바꿨을 경우 틀리게 된다. tree[n]=lazytree[n]*(e-s+1); 이거를 if((e-s+1)%2!=0){ tree[n]^=lazytree[n];//*(e-s+1); } 이렇게 바꿔주면 된다. 저렇게 바꿔 주는 이유는 어떤수를 a라고..
세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무를 마친 키파는 버거운 직장에서 벗어나 새로운 직업에 도전하고자 햄버거집을 차렸다. 키파는 케이크를 여러 차례 만들면서 빵은 좀 구워 봤지만 햄버거를 만드는 것 www.acmicpc.net 이문제는 금광세그로 하는 풀이도 있지만 세그 레이지로 풀이하겠다.. 풀이는 구간에서 남는 )의 개수와 (의 개수를 구하는 방식이다. 배열에 원래 구간과 반전했을때의 구간을 저장하고 변경이 일어날 때마다 2개의 구간을 반전시키면서 바꿔준다. 처음에 트리를 만들때 struct으로 트리안에 배열을 넣어서 트리를 만든다. void seg(ll n,ll s,l..
세그먼트 트리 min,max를 이용한 풀이입니다 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 이 문제를 풀려면 구간의 최솟값과 최댓값을 구해야합니다 그 이유는 만약 A가 1부터 4까지의 구간의 책을 가지고 왔습니다. 이때 1부터 4까지의 책들이 순서는 상관없이 모두 있어야합니다. 만약 1부터 4까지의 최솟값이 1이 아니라면 1보다 작은 값이 들어있거나 1은 들어있지 않게 ..
- Total
- Today
- Yesterday
- 트리에서의 다이나믹 프로그래밍
- 자료 구조
- 깊이 우선 탐색
- 그리디 알고리즘
- 이분매칭
- 트리
- 그래프 탐색
- 완전 탐색
- 이분 탐색
- A Dance of Fire and Ice
- C++
- 잡봇
- 수학
- 구현
- 최소 스패닝 트리
- codeforces
- 느리게 갱신되는 세그먼트 트리
- 누적 합
- Python
- 선분 교차 판정
- discord bot
- 세그먼트 트리
- KOI
- 다이나믹 프로그래밍
- 정렬
- 개발
- 알고리즘
- 자료구조
- BOJ
- 그래프 이론
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |