keicoon15

https://algospot.com/judge/problem/read/JOSEPHUS algospot.com :: JOSEPHUS 조세푸스 문제 문제 정보 문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하 algospot.com 단순 리스트 문제임. 처음엔 리스트 함수들을 자세히 정의해서 제출하니 시간초과됨. 다시 단순하게 변경하여 제출해서 통과됨. 다만, 너무 단순하게 생각해서 시간이 꽤나 나오는게 아쉬움. 다음에 다시 도전해서 나이스하게 변경하면 좋겠음. typedef struct node{ int value; node *prev; node *next; }queue; queue *He..

https://algospot.com/judge/problem/read/FIXPAREN algospot.com :: FIXPAREN Mismatched Parenthesis 문제 정보 문제 You are working on a sequence of parentheses. There are four types of parentheses and the symbols used are ( ), { }, [ ], . We call '(', '{', '[', and '' the ri algospot.com stack을 사용하여 풀 수 있었다. #include #include using namespace std; char STR1[120]; char STR2[4]; char STR3[4]; char Return..

https://algospot.com/judge/problem/read/POTION algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 algospot.com 1000이하의 소수를 구함. 소수 배열로 입력값 r[i]를 최대공약수로 나눔(소수로 만듬) 입력값 p[i]와의 최대 비율값을 구함. 그 차이를 계산함. #include #include using namespace std; int n; int r[1000]; int p[1000]; int a[1000]; vector num; void Calculate(int rate) {..

https://algospot.com/judge/problem/read/COINS algospot.com :: COINS Coin Change 문제 정보 문제 우리 나라에는 10원, 50원, 100원, 500원의 네 가지 동전이 있다. (1원짜리와 5원짜리는 거의 안 쓰니까 없는 걸로 하지요) 이 동전들을 이용해 110원을 거슬러 주는 방법은 몇 algospot.com DP문제임. 최대 M값이 5000이므로 모든 경우의 수를 계산하여 품. 가장 작은 동전의 종류부터 DP배열에 더해감. DP배열은 이전에 계산된 DP배열 값에 새로 추가된 동전 DP값을 더하여 만듬. #define MAX_COIN 5000 using namespace std; int main() { int T; for (scanf("%d",..

https://algospot.com/judge/problem/read/INSERTION algospot.com :: INSERTION 삽입 정렬 뒤집기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽 algospot.com 삽입정렬의 초기값을 구하는 문제임. 1번의 Step마다 내부 Index를 참조하고 삭제해야함. STL의 vector나 list를 사용하면 시간초과가됨. 재정의하여 내부 참조는 꼼수를 사용하여 해결함. #include #include typedef struct node{ node * prev; node * next; int value; }NODE; int I[50..

https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 기존 쿼드트리 : 0 -> 1 -> 2 -> 3 상하반전 쿼드트리 : 2 -> 3 -> 0 -> 1 #define SIZE 32 typedef struct leaf{ int depth; char value; leaf *parent; leaf *child[4]; }QTREE; bool MAP[SIZE][SIZE]; int CARD[4] = { 2, 3, ..

https://algospot.com/judge/problem/read/GRID algospot.com :: GRID Tiling a Grid With Dominoes 문제 정보 문제 We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and algospot.com #점화식으로 해결함. 기존의 f(N)의 값에서 f(N+1)을 구하는 식은 다음과 같음. f(N+1) = f(N) // 그냥 2x1타일..

https://algospot.com/judge/problem/read/CLEANER algospot.com :: CLEANER 어떤 과학의 인공지능 청소기 문제 정보 문제 어떤 최첨단 과학 도시에 살고 있는 일방통행 씨는 직사각형 모양의 방에서 살고 있었다. 최첨단 과학 도시임에도 불구하고 손수 청소를 하던 그는 algospot.com 백트래킹 모든 탐색으로 해결함. 다만, 느리다ㅜ #include int MAP[7][7]; int N, M, RESULT; void MOVE(int INDEX, int T) { if (INDEX == N*M - 1 && INDEX == T) { ++RESULT; return; } else if (MAP[INDEX / M][INDEX % M] == T) { int V; V..

https://algospot.com/judge/problem/read/NQUEEN algospot.com :: NQUEEN N-Queen 문제 정보 문제 N-Queen 퍼즐은 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 퍼즐이다. (퀸은 체스에서 가장 강력한 기물로, 자신의 위치에서 상하좌우, 그리고 대각선 algospot.com 완전 탐색을 진행함. N*N의 탐색은 TimeOut QEEN의 특성으로 한 줄에는 1개의 QEEN이 놓아져야함. 그래서 N까지 탐색하면 됨. #include #include int MAP[13][13]; int N, VALUE; bool INPUT(bool type,int c, int r) { if (type && MAP[c][r] != 0) r..

https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 모든 조합에서 조건을 만족하는 전체 경우의 수를 구함. bool friendMap[10][10]; int n, m; int countPairings(bool taken[10]) { int first = -1; for (int i = 0; i 0; CASE--) { memset(friendMap, 0, sizeof(friendMap)); for (scanf("%d %d", &n..