개인사

리뷰 서로 교차하는 케이블 쌍의 개수를 구하고 출력하는 문제https://www.acmicpc.net/problem/7578 전역 변수MAX_N : 입력 되는 노드의 최대 개수를 의미하는 정수형 상수 변수 500001로 초기화 해준다.nodes : 입력 받은 노드의 정보를 저장할 정수형 배열, MAX_N크기로 설정한다.index : 교차하기 위한 노드 정보를 저장할 정수형 배열, index를 값으로, value를 순서로 저장한다, MAX_N * 2크기tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 설정한다.n, ans : 노드의 개수를 저장할 변수 n, 정답을 저장하고 출력할 변수 ans 함수1. updatevoid update(ll node, ll s, ll e, ll i..

리뷰 문자열을 트리 형태로 관리하여 효율적으로 저장, 출력하기 위한 트라이의 기본이 되는 문제https://www.acmicpc.net/problem/14725 전역 변수Trie : 문자열을 트리 형태로 저장하는 구조체, 맵을 통해 문자열을 key로, 하위 트라이를 value로 가진다. 함수1. insertvoid insert(Trie* node, const vector& foods) 문자열 트리의 현재 노드에 하위 노드를 삽입하는 함수현재 노드 정보와 추가해야할 음식들을 문자열 타입 벡터 매개변수로 받는다.우선 루트 노드 정보를 cur이라는 변수에 포인터를 참조하여 값을 별도로 저장해 준다.추가할 음식들을 탐색하면서 현재 루트 로드에 해당 음식이 존재하지 않으면 새로운 자식을 추가해 준다.만약 루트 로..

리뷰 최대 크기는 상관없으나 원소가 100만까지 들어올 수 있으므로 배열크기를 100만 이상으로 해야한다. ㅠㅠhttps://www.acmicpc.net/problem/17299 전역 변수n : 입력되는 수열의 길이lst : 입력된 수열이 저장될 배열, 크기는 100만보다 크게 해준다.v : 입력된 수의 개수를 저장할 배열, 크기는 100만보다 크게 해주던가 해시맵을 사용해 주자ans : 정답을 저장하고 출력할 배열, 크기는 100만보다 크게 해준다. 함수없음  문제풀이n값을 입력 받고 길이 n의 수열 정보를 lst배열에 입력받아준다, 입력 받은 수의 개수를 v배열을 통해 증가시킨다.빈 정수형 벡터 s를 초기화 해준다. 해당 벡터를 스택처럼 사용할 것이다.수열의 뒤에서부터 순회를하며 스택이 비지 않았을때..

리뷰 각 단계별 맵과 현재 위치를 고려하여 목표 위치까지 이동할 수 있는지를 구하는 문제https://www.acmicpc.net/problem/16954 전역 변수lst : 초기 맵 정보를 저장할 문자열 벡터, 크기는 8로 설정한다.ans : 정답 정보를 저장할 정수형 변수v : 각 단계별 현재 위치에 대한 방문 정보를 저장할 3차원 정수형 배열, 8 * 8 * 8크기로 설정한다.dx, dy : 상하좌우, 대각선, 제자리를 고려한 방향배열Pos : 현재 위치를 나타낼 구조체 함수1. movingvoid moving(vector& map) 현재 맵에 존재하는 벽들을 모두 한칸씩 내려주는 시뮬레이션을 진행한다.맵의 아래서 부터 swap을 통해 각 행을 변경해 주고, 마지막에 0번행을 빈 칸으로 세팅해 준다..

리뷰 ans의 타입은 long long을 써야한다!!!!!!!!!!!https://www.acmicpc.net/problem/6198 전역 변수n, ans : 옥상의 개수 정보를 저장할 변수 n, 정답을 저장할 변수 ans, ans는 long long타입이어야 한다!!!!lst : 옥상 높이 정보를 저장할 정수형 배열, 8만보다 크게 설정해 주면 된다. 함수없음  문제풀이n값을 입력 받고 lst배열에 옥상의 높이 정보를 입력 받아준다.스택으로 사용할 정수형 벡터 s를 초기화 해준다, 벡터 말고 스택으로 사용해도 무방하다.현재 스택이 비지 않았고, 스택의 맨위 인자가 현재 옥상 높이보다 작으면 스택 맨위를 pop해준다.스택의 사이즈 만큼 ans에 더해주고, 스택에 현재 옥상 높이를 추가해 준다.반복문이 완..

리뷰 스택을 활용하여 O(N) 시간복잡도로 푸는 문제https://www.acmicpc.net/problem/2493 전역 변수n : 탑의 개수를 저장할 정수형 변수 nlst, ans : 탑의 정보를 저장할 정수형 배열 lst, 각 탑에서 본 결과를 저장할 정수형 배열 ans 함수없음  문제풀이n을 입력 받고 lst 배열에 n개의 탑 정보를 입력 받아준다.스택을 s로 초기화 해주고 다시 n개의 for문을 개행해 준다.스택이 비지 않았고, 스택의 top에 해당하는 인덱스의 탑 높이가 현재 탑보다 낮거나 같으면 pop을 해준다.위 작업을 마친 후 스택이 비어있다면 현재 인덱스의 ans는 0으로, 아니라면 스택의 top인덱스로 저장한다.현재 인덱스를 스택에 추가해 준다. 해당 작업을 계속 반복해 준다.반복문이..

리뷰 우선순위 큐 두개를 사용해서 문제를 풀었다.https://www.acmicpc.net/problem/11000 전역 변수n, ans : 강의의 개수를 저장할 정수형 변수 n, 정답을 저장하고 출력할 정수형 변수 ansIng : 현재 진행중인 강의 정보를 저장할 구조체, 1순위로 종료시간, 2순위로 시작시간 오름차순 정렬해 준다.Stay : 아직 대기중인 강의 정보를 저장할 구조체, 1순위로 시작시간, 2순위로 종료시간 오름차순 정렬해 준다. 함수1. Ing Comparebool operator t를 기준으로 오름차순, t가 동일하다면 s를 기준으로 오름차순 정렬해 준다. 2. Stay Comparebool operator s를 기준으로 오름차순, s가 동일하다면 t를 기준으로 오름차순 정렬해 준다...

리뷰 스택을 활용하여 리스트의 뒤에서부터 순차적으로 순회하며 오큰수를 찾는 문제https://www.acmicpc.net/problem/17298 전역 변수없음  함수없음  문제풀이n을 입력 받고 수와 정답을 저장할 벡터lst, result의 크기를 n으로 초기화 해주고 n개의 수를 입력 받아 저장한다.스택을 초기화 해준 뒤에 n - 1부터 0번 인덱스 까지 lst를 반대로 순회해 줄것이다.스택이 비지 않았을 경우 스택의 제일 위 요소와 현재 값을 비교한다.스택의 제일 위 요소가 현재 값보다 작거나 같으면 스택에서 제거해 준다. 이 작업을 반복해 준다.위 작접이 완료된 후 만약 스택이 빈 상태라면 result의 현재 인덱스 값을 -1로 저장한다.만약 스택이 빈 상태가 아니라면 스택의 마지막 요소를 res..

리뷰 업데이트를 느리게 갱신하며 구간 누적합을 구하는 문제 int 범위를 초과하므로 long long타입을 사용해 줘야 한다.https://www.acmicpc.net/problem/15967 전역 변수n, q1, q2 : 노드의 개수 n, 출력 쿼리의 개수 q1, 업데이트 쿼리의 개수 q2nodes : 노드의 정보를 저장할 정수형 배열, 크기는 100만으로 세팅tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 400만으로 세팅lazy : 업데이트 정보를 저장할 정수형 배열, 크기는 400만으로 세팅 함수1. buildvoid build(ll node, ll s, ll e) nodes배열을 사용하여 구간 합을 저장할 세그먼트 트리를 만드는 함수 2. propagatevoid propagate..

리뷰 세그먼트 트리를 응용하여 히스토그램 상에서 가장 큰 면적을 구하는 문제https://www.acmicpc.net/problem/6549 전역 변수lst : 히스토그램의 높이 정보를 저장할 정수형 배열, 최대 히스토그램 크기 10만으로 초기화 해준다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, lst의 4배 40만으로 크기를 초기화 해준다.n : 히스토그램의 최대 갯수를 저장할 정수형 변수  함수1. initvoid init() 각 테스트 케이스 마다 lst와 tree를 0으로 초기화 해주는 함수 2. inputvoid input() 데이터를 입력 받고 히스토그램 높이 정보를 lst배열에 초기화 해주는 함수 3. buildvoid build(ll node, ll start, ll end) ..