본문 바로가기

컴퓨터/알고스팟 알고리즘

 (22)
알고스팟 알고리즘: Longest Increasing Sequence(LIS) [C++] 문제 출처: https://algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 1. 코드 #include #include #include using namespace std; int solution(vector a) { int ret = 0; vector b;//최대 길이 저장 for (int i = 0; i < a.size(); i++)//기준 { int longest..
알고스팟 알고리즘: 삼각형 위의 최대 경로(TRIANGLEPATH) [C++] 문제 출처: https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com 1. 코드 #include #include #include using namespace std; int N; int solution(vector t, vector & c, int x, int y) { if (y == N - 1) return t[y][x]; if (c[y][x] != 0) return c[y..
알고스팟 알고리즘: 외발 뛰기(JUMPGAME) [C++] 문제 출처: https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com 1. 코드 #include #include using namespace std; int N;//크기 bool flag;//정답 확인 void solution(vector g, vector &c, int x, int y) { if (c[y][x] == 1) return;//이미 탐색한 구역이라면 if (flag == true) return;//정답을..
알고스팟 알고리즘: 울타리 잘라내기(FENCE) [C++] 문제 출처: https://algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 algospot.com 1. 코드 #include #include using namespace std; int main(void) { int C; cin >> C; while (C--) { int N; cin >> N; //펜스 갯수 입력 vector fence; for (int i = 0; i > temp; fence...
알고스팟 알고리즘: 쿼드 트리 뒤집기(QUADTREE) [C++] 문제 출처: https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 1. 코드 #include #include using namespace std; string reverse(string::iterator& it) { char head = *(it++); if (head == 'b' || head == 'w') return string(1, head); string upperLeft = reverse(it)..
알고스팟 알고리즘: TSP1(여행하는 외판원 문제, Traveling Salesman Problem) [C++] 문제 출처: https://www.algospot.com/judge/problem/read/TSP1 algospot.com :: TSP1 Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 www.algospot.com 1. 코드 #include using namespace std; double dis[8][8];//도시 사이의 거리 bool check[8];//이미 지나간 도시 int N;//도시의 수 double result;//결과값 //start: 시작하는 도시, cnt: 거쳐간 도시의..
알고스팟 알고리즘: BOARDCOVER [C++] 문제 출처: https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 1. 코드 #include #include #include using namespace std; //게임판을 채울 수 있는 도형의 네 가지 모습 int coverType[4][3][2] = { {{0,0},{1,0},{0,1}}, {{0,0},{0,1},{1,1}}, {{0,0},{1,0},{1,1}}, {{0,0},{1,0},{1,-1}..
알고스팟 알고리즘: 록 페스티벌(FESTIVAL) [C++] 문제 출처: https://algospot.com/judge/problem/read/FESTIVAL algospot.com :: FESTIVAL 록 페스티벌 문제 정보 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 algospot.com 1. 코드 #include using namespace std; double min_cost = 0; int N, L; //N: 공연장을 빌릴 수 있는 날, L: 섭외한 공연팀의 수 int * arr; //날마다 생기는 비용(동적할당) //문제 해결을 위한 재귀 함수 void solution(int cur, int cnt) //cur: 현재 배열의 위치,..

티스토리툴바