본문 바로가기

알고리즘/알고리즘 트레이닝(초록)10

CSES PS - nearest smaller values(NSV) https://cses.fi/problemset/task/1645/ 하나의 새로운 알고리즘, O(n) 카르테시안 트리라는 자료구조 구현의 기본 아이디어라고 함. https://wcipeg.com/wiki/All_nearest_smaller_values 영어설명 monotonic stack이라고도 함. https://www.acmicpc.net/problem/17298 다른 기본문제 최대 2e5개의 숫자를 입력받으면서, 처음부터 입력받은 그 시점까지 입력받은 숫자보다 작은 수 중에 가장 가까운 값의 인덱스를 반환하라. 1. k> n; stack s; s.push(0); for (int i = 1; i > a[i]; //입력받은 배열의 값보다 큰 값들은 없애버림 while (a[s.top()] >= a[i].. 2020. 1. 16.
CSES PS - Towers (그리디, sorting) https://cses.fi/problemset/task/1073 sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다. 큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나) n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.) i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다. int main() { FAST; int n; cin >> n; multiset st; while (n--) { int a; cin >> a; auto.. 2020. 1. 13.
CSES PS - Grid Paths https://cses.fi/problemset/task/1625/ 백트래킹 문제. 아이디어가 안떠올라서 답확인함. 7*7 공간에서 (0,0) ~ (6,0)까지 갈 때 경로가 ?,L,R,U,D 총 48자로 주어진다. 이때 ?대신 아무 방향이나 사용할 수 있을 때 가능한 경로의 수를 모두 구하는 문제. ?가 48개 있을 때 백트래킹 없이 dfs하면 4^48만큼의 시간이 걸리므로 백트래킹이라고 생각하지 않았다. U 9개 D 15개, R 12개, L 12개의 적절한 순열인 줄 알았지만 아니었다. (빨간색은 방문할 수 없는 지점(벽너머거나, 방문했거나), 파란색은 방문할 수 있는 지점(y>0 && y 0 && cy < 6 && !visited[cy - 1][cx] && !visited[cy + 1][cx]) r.. 2019. 12. 22.
CSEC PS - chessboard and Queens https://cses.fi/problemset/list/ 코드가 깔끔한거같아서 올려봄 n-queen문제와 흡사함. 8*8 체스판에 8개의 퀸을 서로 공격할 수 없도록 두는 경우의수를 출력하는 문제. 퀸을 둘 수 없는 곳을 (*)로 표시해서 약간의 변형을 줬다. (풀이는 똑같음) column, diag1, diag2에 대해 이미 사용중인 것이 있다면 가지치기를 하며 재귀 #include #include #include using namespace std; typedef long long ll; bool unable[8][8]; int ans = 0; void go(int k, int col, ll d1, ll d2) { if (k == 8) { ans++; return; } for (int i = 0; .. 2019. 12. 21.

티스토리툴바