https://www.algospot.com/judge/problem/read/JUMPGAME 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다. 균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 ..

소수 찾기 프로그램 방법 n-1까지 구하기 O(n) n-1 까지 소수를 모두 구하는 다이나믹 프로그래밍으로 알고리즘 짜기 소수 배열을 만들어서 소수 배열만 돌면서 나누어지는지 판단 O(n) 소수 배열을 만드는 데에 O(n) => 메리트 없음 루트 n까지 돌리면서 짝수 제외하기 O(sqrt(n)) 조건 추가 몇 개의 소수( 3, 5 )를 가지고 해당 수의 배수이면 뛰어넘기 3, 5 계산 시 나누어떨어지지 않았으면 해당 수의 배수에도 나누어떨어지지 않음 구현 시 주의 해당 수가 3으로 나누어떨어지는지, 5로 나누어떨어지는지를 계산하려면 모듈러 연산을 사용해야하는데 시간이 오래 걸림 변수 하나씩 지정하고 1씩 더하는 방법으로 구성 3과 5의 공배수가 나오면 먼저 거치는 3의 if문에서 continue 됨으로 ..

Quick sort '알고리즘' 전공 수업시간에 나온 과제인 '1000만개 데이터 정렬 후 해시 값 구하기'를 하면서 정리한 내용이다. 분할 정복 방법을 통해 구현되는 정렬 방법 시간 복잡도 최악 : O(n^2) 평균 : O(nlogn) 설계를 통해서 개선 가능한 부분 구현 과정 pivot을 선택한다. 위쪽 포인터가 낮은 쪽으로 가면서 피벗보다 작은 수를 찾는다. 아래쪽 포인터가 높은 쪽으로 가면서 피벗보다 큰 수를 찾는다. 두 포인터가 가리키는 요소를 교환한다. 2-4를 반복한다. 두 포인터가 교차한다면 현재 피벗과 해당 위치의 값을 교환한다. 피벗과 피벗보다 작은 section, 피벗보다 큰 section으로 나누고 각 section에 대해 1-5를 실행한다. section의 크기가 0 또는 1이면 ..

https://www.acmicpc.net/problem/18809 첫번째 코드 #include #include #include #include using namespace std; struct seed { int y, x; }; int map[50][50]; vector landToSeed; vector Green; vector Red; int N, M, G, R; vector g; vector r; int dir_y[4] = {0,1,0,-1}; int dir_x[4] = {1,0,-1,0}; void printVector(vector& a) { // int에 land도 넣을수 있을까? vector::iterator iter; for (iter = a.begin(); iter != a.end(); i..

QuickSort 논문 brief Part One: Theory 이 sorting은 두 개의 간단한 보조문제로 나뉘어 해결될 수 있는데, 각 문제는 이미 알려진 방식으로 풀 수 있다. Partition : key값을 dividing line에 따라 위 아래로 나누어 이분하는 것 실제로 이 dividing line은 흔치 않고, 있다 할지라도 찾기 힘든데 dividing line이 존재하고 그것의 위치만 안다면 item들을 재정렬하기는 쉬워진다. partition 과정 정렬되어야하는 아이템의 키 중 특정 키를 고른다. 이 키는 bound 라 불린다. dividing line 아래에는 bound보다 작거나 같은 key값이, 위쪽에는 큰 key 값이 오게 한다. dividing line의 위치는 미리 알 필요..

/* 2020-03-19 우희은 삽입정렬 알고리즘 */ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int buffer[10000000]; // 전역 변수로 넣어야 stack overflow가 나지 않음 void fileOpen() { FILE *fp = fopen("d://algorithm/unsorted10000000.txt", "r"); int i = 0; int tmp = 0; if (fp == NULL) { printf("파일을 열 수 없습니다.\n"); } while (fscanf(fp, "%d ", &tmp)!=EOF) { buffer[i++] = tmp; } fclose(fp); } void insertSortin..

첫번째 과제이다. 시간 복잡도가 f(n)인 알고리즘의 소요시간이 1 nanosecond == 10^(-9) second 이라고 할 때, 왼쪽에 표시된 시간 복잡도를 가지고 있는 알고리즘에 대해 위쪽의 시간 내에 알고리즘이 완료되려면 최대로 어떤 N까지 계산할 수 있을지 알아보자. 대표로 하나를 계산해보면 1sec는 10^(9) nanosec 이므로 n^2의 시간복잡도를 갖는 알고리즘에서 n^2 = 10^(9) 로 두고 풀면 1sec 만에 계산될 수 있는 n 값이 나온다. n 값은 모두 정수로 가정하였다.

https://www.acmicpc.net/problem/18808 #include #include using namespace std; int n, m, k; int turn; int st_l, st_w; struct sticker { int x_len, y_len; }; void rotateSticker(vector& stic) { int width = stic[0].size(); int length = stic.size(); vector tmp(width, vector(length)); for (int i = 0; i < length; i++) { for (int j = 0; j < width; j++) { tmp[j][length-1-i] = stic[i][j]; } } stic = tmp; } ..