반응형

C++ 354

[G3] 백준 16954번 움직이는 미로 탈출 C++ 백트래킹

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

[G3] 백준 2812번 크게 만들기 C++ 스택, 문자열, 그리디 알고리즘

리뷰 수를 문자열로 변환하여 스택을 활용한 그리디 문제이다.https://www.acmicpc.net/problem/2812 전역 변수lst : 숫자를 저장할 문자열 변수n, k, cnt : 숫자의 길이 n, 지울 숫자의 개수 k, 지운 숫자를 체크할 변수 cnt 함수없음  문제풀이n, k, lst값을 순서대로 입력 받아주고, 스택으로 사용할 문자타입 벡터 s를 초기화 해준다.n번의 반복문을 개행하고, s가 비지 않았고, s의 back이 현재 수보다 작으며, cnt가 k보다 작다면 문자열을 제거한다.문자열이 제거된 후에는 cnt를 증가시켜서 k와 비교를 해주어야 한다.위 작업이 끝난 후에는 스택에 현재 숫자(문자)를 추가해 준다.최종적으로 스택에 저장되어 있는 숫자(문자)를 한개씩 출력해 주면 된다. (..

[G5] 백준 6198번 옥상 정원 꾸미기 C++ 스택

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

[G5] 백준 2493번 탑 C++ 스택

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

[G5] 백준 11000번 강의실 배정 C++ 우선순위 큐

리뷰 우선순위 큐 두개를 사용해서 문제를 풀었다.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를 기준으로 오름차순 정렬해 준다...

[G5] 백준 3980번 선발 명단 C++ 백트래킹, 브루트포스 알고리즘

리뷰 11명의 선수가 각 포지션의 최대 기량을 가질 수 있게 완전 탐색을 하는 문제https://www.acmicpc.net/problem/3980 전역 변수lst : 각 선수의 포지션별 기량 정보를 저장할 정수형 2차원 배열v : 방문 처리를 위한 정수형 배열tc, ans : 테스트케이스 수를 저장할 tc, 각 테스트 케이스마다 정답을 저장하고 출력할 ans 함수1. btvoid bt(int level, int sum) 완전 탐색에 사용할 함수 매개변수 level = 재귀 단계, sum = 현재 단계까지의 기량의 합이다.level은 재귀 단계이기도 하면서 현재 선수를 의미하기도 한다.따라서 level이 0일 경우엔 첫번째 선수의 11개 포지션에 대한 기량을 탐색한다.만약 0보다 클 경우 해당 선수를 해..

[G4] 백준 17298번 오큰수 C++ 스택

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

[P4] 백준 15967번 에바쿰 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰 업데이트를 느리게 갱신하며 구간 누적합을 구하는 문제 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..

[G5] 백준 5972번 택배 배송 C++ 최단 경로, 다익스트라

리뷰 간단한 다익스트라를 통한 시작점 > 도착점으로 가는 최단 경로를 구하는 문제https://www.acmicpc.net/problem/5972 전역 변수n, m : 노드의 개수를 저장할 정수형 변수 n, 간선 개수를 저장할 정수형 변수 mPos : 간선 정보를 저장할 구조체, 다음 노드와 가중치가 저장되며, 우선순위 큐의 compare 함수를 정의했다.path : 각 노드의 인접리스트를 저장할 Pos타입 2차원 벡터 함수1. dijkstraint dijkstra(int start, int end) start에서 end까지의 최단 경로를 구하는 함수Pos타입 우선순위 큐 pq에 start를 삽입하고 end까지 가는길의 최단경로를 dist벡터에 최신화 해준다.pq가 빌때까지 while루프를 통해 위 작업..

[G1] 백준 3665번 최종 순위 C++ 위상 정렬

리뷰 각 순위별 간선을 생성하고, 쿼리로 입력되는 노드간 간선을 반전시킨 후 위상 정렬을 수행하는 문제https://www.acmicpc.net/problem/3665 전역 변수tc, n, m : 테스트 케이스의 개수 tc, 팀의 개수 n, 순위 변경 쿼리의 개수 mlst : 작년 순위 정보를 저장할 정수형 벡터cnt : 선순위의 개수를 저장할 정수형 벡터result : 금년 순위 정보를 저장할 정수형 벡터path : 인접 리스트를 저장할 정수형 2차원 벡터 함수1. initvoid init() 각 테스트 케이스마다 lst, cnt, result, path 벡터를 clear해주는 함수 2. input()void input() n값을 입력 받고 각 테스트 케이스 마다 lst, cnt, path의 크기를 n..

728x90
반응형