반응형

C++ 347

[G4] 백준 14500번 테트로미노 C++ 구현, 백트래킹

리뷰 https://www.acmicpc.net/problem/14500각 위치마다 일반적인 4방향 백트래킹을 돌린다. ㅗ모양은 방향배열로 알 수 없어 해당 부분만 추가로 체크해 준다.ㅓㅗㅜㅏ 네개만 체크했다가 한번 틀렸다, 체크해야할 모양은 총 8개이다.  전역 변수n, m : 맵의 세로 길이 n, 맵의 가로 길이 mans : 정답을 저장하고 출력하기 위한 변수dx, dy : 8방향 탐색을 위한 방향 배열lst : 맵 정보를 저장하기 위한 정수형 2차 배열v : 방문 표시를 해주기 위한 정수형 2차 배열h : ㅗ모양을 했을때 각 모양의 값을 저장하기 위한 정수형 배열 함수1. inputvoid input() n, m을 입력 받고 맵 정보인 lst배열을 입력받기 위한 함수 2. btvoid bt(int ..

[G3] 백준 16637번 괄호 추가하기 C++ 구현, 백트래킹

리뷰 https://www.acmicpc.net/problem/16637주어지는 연산자가 포함된 문자열로 이루어진 수열에서 괄호를 적절히 쳐서 최대값을 만드는 문제처음엔 모든 경우에 대해 괄호를 씌워주었는데, 괄호가 중첩되면 안된다는 조건이 있었다.추가로, 음수 정답이 나오는 예제가 없으니 해당 부분을 놓치기 쉬운 것 같다.  전역 변수n : 입력되는 수열 형태의 문자열의 길이max_lv : 재귀를 멈출 기저조건에 해당하는 레벨ans : 정답을 출력하기 위한 변수, 초기값은 매우 작은 음수값으로 초기화 해준다.s : 수열 형태의 문자열을 입력받을 변수nums : 수열에서 숫자만 따로 저장하기 위한 정수형 벡터ops : 수열에서 연산자만 따로 저장하기 위한 문자형 벡터 함수1. initvoid init()..

[P3] 백준 2820번 자동차 공장 C++ 세그먼트 트리, 오일러 경로 테크닉, 느리게 갱신되는 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/2820오일러 경로 테크닉을 통해 배열을 트리구조로 재정의 하고, 해당 정보를 이용해 세그먼트 트리를 만든다.세그먼트 트리 상에서 LazyPropagation을 통해 업데이트를 진행하고 각 쿼리마다 직원의 월급을 출력하는 문제  전역 변수MAX_N : n이 입력될 수 있는 최대값, 500001로 초기화 한다.n, m : 직원의 개수 n, 쿼리의 개수 mnodes : 각 직원의 초기 월급을 저장할 정수형 배열tree : 세그먼트 트리를 저장할 정수형 배열lazy : 세그먼트 트리의 업데이트 정보를 저장할 정수형 배열it : 오일러 경로 탐색을 통해 직원의 시작 인덱스를 저장하기 위한 정수형 배열sal : 오일러 경로에서 구한 인덱스를 기준으로 ..

[P5] 백준 1989번 부분배열 고르기 2 C++ 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/1989 [P5] 백준 2104번 부분배열 고르기 C++ 세그먼트 트리리뷰 https://www.acmicpc.net/problem/2104구간의 누적합과 최소값의 인덱스를 저장한 세그먼트 트리를 구현하고 구간의 누적합 * 구간의 최소값이 가장 큰 케이스를 찾아 출력하는 문제  전역 변수n :zzzz955.tistory.com위 문제와 동일하나 구간의 범위까지 출력해 주어야 하는 문제  전역 변수MAX_N : n값의 최대값을 저장할 정수형 상수 변수n : 배열의 길이를 저장할 변수nodes : 배열의 정보를 저장할 정수형 배열, 크기는 MAX_NminTree : 최소값의 인덱스를 저장할 세그먼트 트리, 크기는 MAX_N * 4Res : 구간의..

[P5] 백준 2104번 부분배열 고르기 C++ 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/2104구간의 누적합과 최소값의 인덱스를 저장한 세그먼트 트리를 구현하고 구간의 누적합 * 구간의 최소값이 가장 큰 케이스를 찾아 출력하는 문제  전역 변수n :주어지는 배열의 길이MAX_N : n의 최대값nodes : 배열 정보를 저장할 정수형 배열, 크기는 MAX_N으로 세팅한다.minTree : 최소값의 인덱스를 저장할 세그먼트 트리 크기는 MAX_N * 4sumTree : 구간의 합을 저장할 세그먼트 트리 크기는 MAX_N * 4 함수1. minBuildvoid minBuild(ll node, ll s, ll e) minTree를 초기화 하기 위한 함수리프 노드에 s혹은 e로 각 배열의 인덱스를 저장해 준다.리프 노드가 아닐 경우 s ..

[P5] 백준 1725번 히스토그램 C++ 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/1725주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 문제세그먼트 트리를 활용해 히스토그램의 각 높이를 비교하고 구간에서 가장 작은 높이의 인덱스를 관리해 준다.query를 수행하며 각 구간에서의 가장 작은 높이를 가진 막대 기준으로 만들 수 있는 사각형의 최대 넓이를 구한다.  전역 변수n : 주어지는 히스토그램의 개수MAX_N : n이 입력될 수 있는 최대의 수, 10만으로 저장했다.nodes : 히스토그램의 정보를 저장할 정수형 배열, 크기는 MAX_N으로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화 한다. 함수1. buildvoid build(int node, in..

[G4] 백준 14499번 주사위 굴리기 C++ 구현, 시뮬레이션

리뷰 https://www.acmicpc.net/problem/14499맵 상에서 주사위를 굴려 맵과 주사위의 정보를 변경하고, 유효한 굴림 마다 주사위의 위쪽에 저장된 값을 출력하는 문제처음엔 각 구른 상태를 적절히 더하거나 빼주어 모듈러 연산을 하려 했으나 값이 일치하지 않았다.결국 전개도를 펼쳐 구현하였는데 오히려 이게 더 쉽고 빨랐던 것 같다.  전역 변수dx, dy : 주사위가 맵 상에서 움직이는 것을 구현하기 위한 방향 배열lst : 맵 정보를 입력 받을 정수형 2차 배열, 20 * 20 크기로 초기화 해준다.n, m : 맵의 세로 크기n, 맵의 가로 크기 msx, sy : 주사위의 시작 지점 x, y좌표를 받기 위한 변수k : 주사위를 굴릴 쿼리의 개수dice : 주사위의 각 면의 값을 저장..

[G2] 백준 21276번 계보 복원가 호석 C++ 위상 정렬, 해시맵, set

리뷰 https://www.acmicpc.net/problem/21276이를 기반으로 몇 개의 가문이 존재했는 지, 각 가문에 대한 정보를 출력하는 문제m값을 입력 받아놓고 for문을 n번 돌려서 틀렸다 ㅠ 전역 변수n, m : 이름의 개수 n, 부모 및 조상을 나타내는 간선의 개수 msum : 시조의 개수를 저장할 변수dic : 시조간 인접 리스트를 구현하기 위한 해시맵cnt : 이름 간 선순위가 필요한 경우의 수를 저장할 해시맵result : 이름 간 직계 자손을 저장하기 위한 해시맵q : 선순위가 더 이상 없는 이름을 저장하기 위한 큐sizo : 시조의 이름을 오름차순으로 정렬하기 위한 셋 함수1. input void input() 이름을 입력 받고 해시맵, 인접 리스트를 초기화 하기 위한 함수n을..

[G3] 백준 1644번 소수의 연속합 C++ 투 포인터, 에라토스테네스의 체

리뷰 https://www.acmicpc.net/workbook/view/8709주어진 값까지의 모든 소수를 구하고, 해당 소수 배열에서의 연속합이 주어진값과 일치하는 경우의 수의 개수를 구하는 문제  전역 변수n : 일치 시켜야 하는 정수를 저장할 변수ans : 소수의 연속합이 n값과 같은 케이스의 개수를 저장할 변수sosu : 에라토스테네스의 체를 사용하여 각 정수가 소수인지 여부를 저장할 정수형 배열, 크기는 400만 초과 함수없음  문제풀이n값을 입력 받고, n까지의 수 중 소수가 아닌 경우 sosu배열에 1로 표시해 준다.정수형 타입 벡터 sosus를 초기화 하고, 2 ~ n까지의 수에서 sosu배열 상 값이 0인 경우 추가해 준다.포인터로 사용할 정수형 변수 l, r을 각각 0으로 초기화 해준..

[G5] 백준 2668번 숫자고르기 C++ DFS, 브루트포스 알고리즘

리뷰 https://www.acmicpc.net/problem/2668백트래킹을 시도 했다가, n이 최대 100만에 걸려 시간 초과가 출력되었다.문제를 보다 보니 첫째줄은 노드를, 둘째줄은 간선을 통해 다른 노드로 이동하는 것으로 보였다.모든 정점에서 DFS를 진행하여 싸이클이 발생하면 자신을 ans에 추가하는 식으로 구현하였다.  전역 변수n : 주어지는 노드의 개수lst : 주어지는 간선의 정보를 저장할 정수형 배열v : 방문 처리를 하기 위한 정수형 배열ans : 싸이클이 발생한 노드 정보를 추가할 정수형 벡터 함수1. dfsvoid dfs(int s, int e) 시작 지점으로부터 간선을 타고 노드를 순회하며 사이클 발생 여부를 체크할 함수기저 조건은 이미 방문한 노드를 재 방문한 경우이다.이때 ..

728x90
반응형