개인사

리뷰 구간의 합이 특정 값이 되는 구간의 개수를 구하는 문제https://www.acmicpc.net/problem/2015 전역 변수dic : 특정 구간의 누적합을 key로 갖고, 그러한 누적합의 개수를 value로 받는 해시맵 long long, int 타입total, ans : 누적합 정보를 저장할 변수total, 인접한 수열의 합이 k인 수열의 개수 ans, long long타입으로 초기화 한다.n, k, : 수열의 길이 n, 찾을 값 k,  함수없음  문제풀이n, k를 입력 받고, sum배열의 1 ~ n번째 인덱스에 누적합 정보를 저장해 준다.다시 1 ~ n번의 정보를 탐색하며 ans에 현재 누적합 인덱스에서 k를 뺀 값의 개수를 더해준다.이후 현재 누적합 정보를 키로 갖는 dic의 개수를 증가..

리뷰 XOR연산에 대해 재정립 하는 시간이 되었다.https://www.acmicpc.net/problem/12844 전역 변수MAX_N : 노드의 최대 개수를 저장할 인트형 상수 정수, 50만으로 초기화 해준다.nodes : 노드의 정보를 저장할 정수형 배열, MAX_N크기로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.lazy : 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.n, m : 노드의 개수를 저장할 정수 변수 n, 쿼리의 개수를 저장할 정수 변수 m 함수1. buildvoid build(int node, int start, int end) 세그먼트 트리를 초기화 해주는 함수 2. propagatevoid ..

리뷰 2048(Easy)의 어려운 버전, 재귀의 깊이가 기존 5에서 10으로 늘어났다. [G1] 백준 12100번 2048 (Easy) C++ 백트래킹, 구현, 시뮬레이션, 브루트포스 알고리즘리뷰 2048게임을 구현하는 문제, 시뮬레이션만 잘 작성하면 쉽게 풀 수 있으나 문제를 잘 읽어보아야 할듯 하다.https://www.acmicpc.net/problem/12100 문제 풀이전역 변수n : 맵의 행, 열을 저장할 변수anszzzz955.tistory.com 가지치기를 최소 두개를 추가해 줘야 시간 초과를 막을 수 있는 문제인 듯https://www.acmicpc.net/problem/12094 전역 변수n, ans : 맵의 행과 열의 길이를 저장할 정수형 변수 n, 최대값을 저장할 변수 ansmap ..

리뷰 느리게 갱신되는 세그먼트 트리 문제 치고 굉장히 짧고 쉬운 문제!https://www.acmicpc.net/problem/1395 전역 변수MAX_N : 스위치의 최대 개수를 정의할 정수형 상수 변수tree : 세그먼트 트리 정보를 저장할 배열 MAX_N * 4 크기로 초기값은 0이다.lazy : 업데이트 갱신을 적용하기 위한 트리 배열 MAX_N * 4 크기로 초기값은 0이다.n, m : 스위치의 개수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 m 함수1. propagatevoid propagate(int node, int start, int end) 현재 노드에 갱신이 필요하다면 갱신을 진행하고 자식 노드에 지연 업데이트를 기록하는 함수이다.현재 노드에 갱신이 필요하다면 구간의 길이 - 자신..

리뷰 간만에 풀어본 해시맵 문제, 파이썬으로 숙달한 사람은 map에 익숙해 지는 것 같다.https://www.acmicpc.net/problem/21944 전역 변수n, m : 초기에 입력되는 문제의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 mProb : 문제의 난이도와 알고리즘 분류 정보를 저장할 구조체probs : 문제 정보를 저장할 Prob 타입 배열, 문제 번호를 index로 사용하여 관리, 크기는 최대문제 번호 10만 + 1rec1 : recommed입력 시 문제 정보를 출력할 맵, 알고리즘 분류를 키로 가지며 int와 set 쌍으로 관리해 준다.rec2 : 알고리즘 분류 상관 없이 문제의 난이도로만 출력을 관리할 set, pair을 통해 난이도와 문제 번호를 관리한다..

리뷰 쿼리로 부분 수열에 특정 수를 더하기, 곱하기, 대체하기가 나오는 구간합 문제느리게 갱신되는 세그먼트 트리의 개념을 익혔다고 섣불리 덤볐다가 혼쭐났다.https://www.acmicpc.net/problem/13925 문제 풀이전역 변수MAX_N : 노드의 최대 개수를 지정할 정수형 상수 변수MOD : MOD 연산을 해줄 정수형 상수 변수, 10억 + 7로 고정이다.nodes : 수열의 정보가 저장될 정수형 배열, MAX_N 크기로 초기화 해준다.tree : 세그먼트 트리 정보가 저장될 정수형 배열, MAX_N * 4 크기로 초기화 해준다.n, m : 수열의 길이를 저장할 변수 n, 쿼리의 개수를 저장할 변수 mLazy : 세그먼트 트리의 구간 더하기(add), 곱하기(mul), 대체하기(set)를..

리뷰 처음엔 정수를 활용하여 풀려고 했으나 로직짜는게 너무 더러워 질 것 같아서 문자열을 택했다.https://www.acmicpc.net/problem/1327 문제 풀이전역 변수n, k : 정수형 변수이다. 수열의 길이 n, 뒤집는 개수 kinput, s, e : 문자열 변수이다. 수열을 입력 받을 input, 최초 수열의 상태 s, 목표 수열의 상태 ev : 해시를 통한 방문처리를 진행할 unordered_map, 타입으로 초기화 해주었다.Now : BFS를 돌릴때 사용할 구조체, 현재 수열을 나타낼 문자열 cur과 뒤집은 횟수 정수t로 이루어져 있다. 함수1. Reversestring Reverse(string num, int index) 현재 문자열을 입력 받고, index부터 index + ..

리뷰 느리게 갱신되는 세그먼트 트리의 기초 문제, 쿼리가 구간합이 아닌 특정 인덱스를 출력하는 문제이다.https://www.acmicpc.net/problem/16975 문제 풀이전역 변수MAX_N : 노드의 최대 개수를 지정할 상수 변수, 10만으로 초기화 한다.nodes : 수열의 정보를 저장할 배열, 크기는 MAX_N으로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.lazy : 느린 업데이트 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.n, m : 수열의 크기 n, 쿼리의 개수 m을 저장할 변수 함수1. buildvoid build(ll node, ll start, ll end) nodes 수열을 갖고 tree배열에 세그먼트 ..

리뷰 lazy propagate를 배우고 처음으로 문제에 접목해 봤다, 함수 구현보단 정수형 타입때문에 애를 좀 먹었다.https://www.acmicpc.net/problem/10999 문제 풀이전역변수MAX_N : 배열의 크기를 초기화 할 상수형 long long타입 변수nodes : 수열의 정보를 받아 저장할 배열 크기는 MAX_N으로 초기화tree : 세그먼트 트리 정보를 저장할 배열 크기는 MAX_N * 4로 초기화lazy : 업데이트 갱신용 트리 정보, tree와 같은 구조를 가진다.n, m, k : 수열의 길이를 나타낼 n, 업데이트 쿼리의 개수 m, 구간합 출력 쿼리의 개수 k함수1. buildvoid build(ll node, ll start, ll end) 세그먼트 트리를 빌드해 준다...

리뷰 세그먼트 트리를 통해 수열의 특정 구간의 첫번째 최대값과 두번째 최대값을 구하고 그 합을 구해 출력하는 문제https://www.acmicpc.net/problem/17408 문제 풀이전역 변수MAX_N : 노드의 최대 개수 10만을 상수형 정수타입으로 설정해 준다.nodes : 수열의 정보를 담을 배열, 크기는 MAX_N으로 설정한다.tree : 최대값과 인덱스를 담을 정수형 pair 배열, 크기는 MAX_N * 4로 설정한다.n, m : 노드의 개수 및 쿼리의 개수 정보를 담을 변수 함수1. 최대값을 갖는 세그먼트 트리를 만드는 함수 void build(int node, int start, int end) 리프 노드 도달 시 배열의 값과 인덱스를 저장해 준다.이후 탐색을 통해 위로 올려주며 각 ..