개인사

리뷰 https://www.acmicpc.net/problem/9344MST가 보장될 때 특정 간선이 MST에 포함되는지 여부를 체크하는 문제  전역 변수t : 테스트 케이스의 개수를 저장할 정수형 변수n : 각 테스트 케이스 마다 도시의 개수를 저장할 정수형 변수m : 각 테스트 케이스 마다 도로의 개수를 저장할 정수형 변수p, q : 각 테스트 케이스 마다 도로가 MST에 포함되는지 여부를 결정할 두 도시의 번호를 저장할 정수형 변수nodes : 각 도시의 그룹화를 진행하기 위한 정수형 배열Edge : 간선 정보를 정의하기 위한 구조체 두 노드 정보 cn, nn와 가중치 w를 갖고, w기준으로 오름차순으로 정렬하는 operator 함수를 정의해 준다. 함수1. Findint Find(int a) 현재..

리뷰 세그먼트 트리에 수열의 값 중 가장 작은 값의 인덱스를 저장하고, 이를 활용하여 재귀를 통해 구간의 최대 값을 구하는 문제, 유사한 문제가 상당히 많아 하나만 풀어도 딸려오는 문제가 많다. [P5] 백준 1725번 히스토그램 C++ 세그먼트 트리 [P5] 백준 1725번 히스토그램 C++ 세그먼트 트리리뷰 https://www.acmicpc.net/problem/1725주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 문제세그먼트 트리를 활용해 히스토그램의 각 높이를 비교하고 구간에서 가장 작은 높이의 인덱zzzz955.tistory.com  [P5] 백준 6549번 히스토그램에서 가장 큰 직사각형 C++ 세그먼트 트리, 분할 정복 [P5] 백준 6549번 히스토그램에서 가장 큰 직사각형..

리뷰 https://www.acmicpc.net/problem/14727히스토그램에서 가장 큰 직사각형의 면적을 찾는 문제와 동일한 풀이 방식을 가진 문제 [P5] 백준 6549번 히스토그램에서 가장 큰 직사각형 C++ 세그먼트 트리, 분할 정복 [P5] 백준 6549번 히스토그램에서 가장 큰 직사각형 C++ 세그먼트 트리, 분할 정복리뷰 세그먼트 트리를 응용하여 히스토그램 상에서 가장 큰 면적을 구하는 문제https://www.acmicpc.net/problem/6549 전역 변수lst : 히스토그램의 높이 정보를 저장할 정수형 배열, 최대 히스토그램 크zzzz955.tistory.com  전역 변수N : n의 최대값을 명시하기 위한 정수형 상수 변수n : 퍼즐 조각의 개수를 저장하기 위한 정수형 변수..

리뷰 https://www.acmicpc.net/problem/1572https://www.acmicpc.net/problem/9426처음엔 머지 소트 트리를 통해 접근하였으나 바로 시간 초과를 맞게 되었다.이후 도는 0보다 크거나 같고, 65535보다 작거나 같은 정수라는 조건에 영감을 얻어 구간합 세그트리로 AC를 받았다.1572번과 9426번 둘 다 같은 문제로 9426번은 레이팅 점수를 주지 않는다.  전역 변수N : n의 최대값을 저장할 정수형 상수 변수P : 온도의 최대값을 저장할 정수형 상수 변수n : 수열의 길이를 저장할 정수형 변수k : 부분 수열의 길이를 저장할 정수형 변수lst : 수열의 값을 저장할 정수형 배열tree : 세그먼트 트리 정보를 저장할 정수형 배열 함수1. update..

리뷰 https://www.acmicpc.net/problem/1517누적합 세그먼트 트리를 통해 버블 소트 시 swap의 횟수를 구하는 문제  전역 변수N : n의 최대값을 저장하기 위한 정수형 상수 변수n : 수열의 길이를 저장하기 위한 정수형 변수lst : 원소의 값과 인덱스를 저장하기 위한 pair타입의 벡터tree : 세그먼트 트리 정보를 저장하기 위한 정수형 배열ans : 정답을 저장하고 출력하기 위한 정수형 변수 함수1. updatevoid update(int node, int s, int e, int idx) 세그먼트 트리 정보를 업데이트 하기 위한 함수매개 변수로 현재 노드 정보 node, 탐색 범위 s, e, 업데이트할 인덱스 idx를 전달받는다.리프 노드에 도달했을 경우 현재 노드의 ..

리뷰 https://www.acmicpc.net/problem/1168배열을 순회하며 k번째 사람을 제거하고 출력하는 문제이전에 풀었던 데이터 구조 문제와 유사하나 살짝 더 응용한 문제였다.[P4] 백준 12899번 데이터 구조 C++ 세그먼트 트리 [P4] 백준 12899번 데이터 구조 C++ 세그먼트 트리리뷰 https://www.acmicpc.net/problem/12899세그먼트 트리를 활용한 배열에 값을 삽입/삭제하고, k번째 작은 수를 구하는 문제  전역 변수N : 배열의 최대 크기를 저장할 정수형 상수 변수n : 쿼리의 개수zzzz955.tistory.com  전역 변수N : 배열의 최대값을 저장하기 위한 정수형 상수 변수n : 사람의 수를 저장하기 위한 변수k : 사람을 순회할 때 건너 뛰..

리뷰 https://www.acmicpc.net/problem/12899세그먼트 트리를 활용한 배열에 값을 삽입/삭제하고, k번째 작은 수를 구하는 문제  전역 변수N : 배열의 최대 크기를 저장할 정수형 상수 변수n : 쿼리의 개수를 저장할 정수형 변수t : 쿼리의 종류를 입력 받기 위한 변수x : 쿼리의 값을 입력 받기 위한 변수tree : 세그먼트 트리 정보를 저장할 정수형 배열 함수1. updatevoid update(int node, int s, int e, int idx, int val) 세그먼트 트리 정보를 업데이트 하기 위한 함수매개변수로 현재 세그먼트 트리의 노드 node, 탐색 범위 s, e, 변경할 값의 인덱스 idx, 삽입/제거 여부 val을 전달받는다.리프 노드에 도달했을 경우 현..

리뷰 https://www.acmicpc.net/problem/14567까먹을까봐 간만에 풀어본 위상정렬 문제  전역 변수N : 배열의 최대값을 저장할 정수형 상수 변수n : 과목의 개수를 저장할 변수m : 선수 조건의 개수를 저장할 변수result : 각 과목이 최소 몇학기에 이수할 수 있는지 저장할 정수형 배열lst : 간선을 저장하기 위한 정수형 벡터 배열 함수없음  문제풀이n, m값을 입력 받고, m개의 간선 정보를 입력받아 lst배열에 저장한다.정수형 벡터 cnt를 n + 1크기로, 기본값은 0인 상태로 초기화 한다.1번 과목부터 순서대로 연결된 간선을 순회하며 다음 과목의 cnt를 증가시켜 준다.정수형 타입의 큐 q를 초기화 하고, 1번 과목부터 순회하며 cnt가 0인경우 q에 push해준다...

리뷰 https://www.acmicpc.net/problem/15840, 0에서 500, 500까지 생명이 최소로 깎인 상태로 이동하는 문제다익스트라로 구현할까 했지만 그냥 기저 조건에 도달하면 바로 리턴하는게 좋을 것 같아 bfs를 돌렸다.  전역 변수n : 위험 구역의 개수를 저장할 변수m : 죽음 구역의 개수를 저장할 변수lst : 맵 정보를 저장할 정수형 2차 배열v : 방문 정보를 저장할 논리형 2차 배열dx, dy : 4방향 탐색을 하기 위한 방향 배열 함수1. bfsint bfs() 너비 우선 탐색을 사용해 시작 위치부터 목표 위치까지 생명을 가장 조금 사용하여 도착하는 경우를 구하는 함수Pos타입의 우선순위 큐 q를 초기화 해주고, 초기값 0, 0, 0을 넣어준다.v배열에 시작 좌표인 0..

리뷰 https://www.acmicpc.net/problem/1365lower_bound를 사용하여 가장 긴 증가하는 부분 수열을 구하는 문제  전역 변수n : 전봇대의 개수를 저장할 변수ans : 정답을 저장할 변수 함수없음  문제풀이정수형 벡터 lis를 초기화 해준다.n값을 받아 주고, n번의 while루프를 수행해 준다.매 루프마다 정수형 변수 num에 오른편 전봇대의 위치를 받아준다.lower_bound 함수를 통해 lis에서 num이상인 값의 이터레이터를 it에 저장해 준다.it이 lis의 end라면 lis에 num을 push해준다.아니라면 ans를 증가시키고, it의 위치의 값을 num값으로 변경해 준다. 트러블 슈팅없음  참고 사항없음  정답 코드#include#include#include..