개인사

리뷰누적곱을 활용한 응용문제 문제 풀이n개의 수를 입력받아 트리형태로 build 해주고, k에 줄로 입력되는 쿼리를 처리해 주어야 한다.n은 최대 10만, 입력되는 숫자의 범위는 -100 ~ 100 이므로 누적곱을 해버리면 long long 타입으로 감당되지 않는다.따라서 입력을 받을 때 0이라면 0으로, 양수면 1, 음수면 -1로 변환 후 저장해 주어야 한다.이후 업데이트 시에도 value 값에 동일한 조건을 추가해 준다.마찬가지로 쿼리를 통해 반환받은 값을 0과 음수, 양수로 나누어 출력을 해준다. 참고 사항누적곱 세그먼트 트리 로직은 같다, 입력과 출력에 신경을 써주면 되는 문제  정답 코드#include #include using namespace std;int n, k;vector tree;vo..

리뷰세그먼트 트리를 활용하여 최소값을 구하는 문제 문제 풀이상세 내용은 https://zzzz955.tistory.com/180를 참고 바란다.위 링크 문제에서 index가 아닌 최소 값을 구하는 문제, 폼은 거의 일치하며 오히려 더 쉬운 문제다.  참고 사항없음  정답 코드#include #include using namespace std;int n, m;vector tree;void build(vector& lst, int node, int start, int end) { if (start == end) { tree[node] = lst[start]; } else { int mid = (start + end) / 2; build(lst, node * 2, start, mid); build(ls..

리뷰세그먼트 트리를 통한 최소값을 찾고, 해당 값의 index를 찾는 문제 문제 풀이n값을 입력받고 n개의 수를 1차 벡터에  입력 받는다, tree는 4 * n 사이즈로 초기화 해준 뒤 build를 진행한다.이때 tree는 vector> 타입으로 최솟값과 해당 index를 모두 저장할 수 있게 해준다.m개의 줄에 걸쳐 쿼리를 받아주고 각 첫번째 숫자에 따라 업데이트 및 출력을 해주면 된다.쿼리 함수를 실행할때도 리턴 형식을 pair로 해주고 출력 시엔 second + 1을 해주면 된다. 참고 사항 ios::sync_with_stdio(false); cin.tie(NULL); 이건 꼭 해주기 정답 코드#include #include using namespace std;int n, m;vector> tre..

리뷰일반적인 세그먼트 트리를 활용한 구간합 문제인 줄 알았으나 함정이 있었다. 문제 풀이n, q값을 받아오고 벡터에 n개의 수를 받아온 뒤 n * 4 크기의 트리로 build해 준다.q개의 질문을 받고 첫 두개의 수 a, b에 해당하는 구간합을 출력해 준다.이후 두번째 두개의 수 c - 1번째 노드의 수를 d로 업데이트 해준다.q가 종료될 때까지 해당 작업을 반복해 주면 된다. 참고 사항노트에 힌트가 나와있다."x~y는 당연히 x번째 부터 y번째가 맞다. 하지만, 이 문제에서는 x > y인 경우 y번째 부터 x번째이다."이 말은 a, b가 입력될때 b보다 a가 큰 경우가 있다는 말이다. 정답 코드#include #include #include using namespace std;int n, q;vecto..

리뷰세그멘트 트리를 사용하여 최솟값과 최댓값을 찾는 문제 문제 풀이n, m값을 받고 tree_min과 tree_max를 각각 4 * n 크기르 초기화를 해준다.정수형 벡터 nodes를 초기화 하고 n개의 수를 해당 벡터에 push 해준다.build_min, build_max 함수를 통해 nodes 벡터를 각각 tree_min, tree_max에 build 해준다.update 해주는 경우는 없기 때문에 입력 받은 index에 맞게 query_min, query_max 함수를 실행해 주면 된다. 참고 사항각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다 라는 조건이 있기 때문에 최소값 쿼리 함수의 범위가 벗어난 케이스는 1000000001을 리턴해 주고, 최대값 쿼리 함수의 범위가 벗어난 케..

리뷰세그먼트 트리를 활용해 구간 내 최솟값을 찾는 문제 문제 풀이n, m값을 입력 받고 정수형 벡터 nodes를 초기화 하고 정수형 벡터 tree를 4 * n크기로 초기화 한다.n개의 줄로 입력되는 정수를 nodes 벡터에 푸시 해주고 nodes를 바탕으로 tree를 build 해준다.update를 해주는 경우는 없으므로 query를 통해 b - 1 ~ c - 1범위를 탐색하여 최소값을 출력해 주면 된다. 참고 사항각각의 정수는 1,000,000,000 이하의 값을 가지므로 query 탐색 시 범위 조건에 맞지 않는 경우 1000000001를 리턴해 준다.  정답 코드#include #include #include using namespace std;int n, m;vector tree;void buil..

리뷰세그먼트 트리를 활용한 구간 곱 문제 문제 풀이세그먼트 트리 구간합 문제에서 query 실행 시 범위를 완전 벗어났을 때의 return값을 1로 바꿔준다.그리고 build, update, query 실행 시 tree[node]값이나 return값을 + 대신 *로 변경해 주면 된다.자세한 내용은 해당 링크를 참조 https://zzzz955.tistory.com/175 참고 사항곱셈의 결과를 1000000007로 나누어 줄때 내부의 값이 int 타입인 경우 오버플로우가 발생했다.(long long)을 써서 명시적으로 형변환을 시켜주거나 1LL을 곱해줘 자동 형변환이 필요하다.  정답 코드#include #include #include using namespace std;int n, m, k;vector..

리뷰세그먼트 트리로 구간 합을 구하는 문제 문제 풀이n, m, k 값을 입력 받고 n개의 줄로 입력되는 값을 nodes 배열에 받아준다.트리를 4 * n크기로 초기화 하고 nodes 배열을 세그먼트 트리로 빌드해 준다.m + k를 합친 수만큼 반복문을 실행하고 a, b, c를 입력 받는다.만약 첫번째 수가 1이라면 b - 1인덱스의 노드 트리를 v 값으로 update 해준다.첫번째 수가 2라면 query 함수를 통해 b - 1 ~ c - 1 사이의 값을 출력해 준다. 참고 사항입력 값이 -2^63 ~ 2^63-1 범위 이므로 int가 아닌 long long 타입을 사용해 준다.  정답 코드#include #include #include using namespace std;int n, m, k;vector..

리뷰세그먼트 트리를 공부하며 실습용으로 선택한 문제, 이제 슬슬 C++에서도 입출력을 신경 써줘야 할때가 온 것 같다. 문제 풀이배열의 크기와 배열을 받아와 주고 4 * n크기로 트리를 초기화 해준다. 받아온 배열로 세그먼트 트리를 최소값 형식으로 build 해준다.이후 m을 입력 받고 m크기 만큼 루프를 실행해 준다.order값이 2일 경우 최소값을 출력하는 query를 실행해 준다.order값이 1일 경우 트리의 i - 1번째 요소를 v로 바꿔준다. 참고 사항m이 최대 10만이므로 ios::sync_with_stdio(false); cin.tie(NULL);로 입력 속도를 최적화 해주니 통과하였다.인덱스도 사용해야 하니 세그먼트 트리를 pair 형식으로 초기화 하였다. 첫번째 정수는 노드 번호, 두번..

리뷰조건에 쉬워보였으나 굉장히 까다로웠던 문제, bfs함수 내에서 2중 while문과 sort를 통해 풀었다. 문제 풀이2차 배열 필드를 입력받고 만약 현재 입력값이 9라면 아기 상어 이므로 좌표를 저장해 준다.bfs를 시작하고 total_time을 0으로 초기화 한 후 while문을 항상 true인 상태로 개행해 준다.이후 일반적인 bfs와 동일하게 큐와 방문 배열(여기선 거리계산 역할까지 병행)을 초기화 하고 큐에 시작 위치를 담은 pos 구조체를 추가해 준 뒤 현재 위치의 거리를 0으로 초기화 해준다.잡아먹은 물고기 정보를 저장할 fishes 벡터를 초기화 해주고 최소 거리를 -1로 잡은 후 bfs를 실행해 준다.4방향 탐색을 하고 만약 거리가 -1(방문하지 않은)이면서 2차 배열의 값이 아기 상어..