merge sort

알고리즘 문제를 풀때 (라이브러리 사용에 제약 이 있을 경우), 간단하게 quick sort로 해서 풀어 왔는데, 아래 막대기 문제는 quick sort 때문에 time out이 발생했다. quick sort는 Data Set에 따라서, 피벗 위치를 어디로 잡느냐에 따라서 최악의 경우가 발생할 수 있다. 그래서 이런 경우를 감안하면 merge sort를 활용해야 할듯 하다. Test Set 을 모르는 상태로, Time out을 당하지 않아야 하기 때문이다. merge sort는 아래 코드 처럼 data를 무조건 절반 분할하여 비교하기 때문에, Test Set의 종류에 무관하게 걸리는 시간은 똑같다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1897&sca=30a0

void msort(int s, int e)
{
 if (s >= e)return;
 int i,j, k, m;
 i = k = s;
 m = (s + e) / 2;
 j = m + 1;
 msort(s, m); //분할부터 한다.
 msort(j, e);

 /////////////분할이 완료 된 후 병합한다.//////////
 while (i <= m ||j <= e)
 {
  if (i > m || (j <= e && arr[j] > arr[i]))//sort조건
  {
   temp[k++] = arr[j++];
  }
  else
  {
   temp[k++] = arr[i++];
  }
 }
 
 ////////////임시 배열에 저장된 값을 복사한다//////////////////
 for (int i = s; i <= e; i++)
  arr[i] = temp[i];
}

알고리즘 문제를 풀때 템플릿 까지 쓸 일이 있을까 싶은데..위에 문제는 자료형 두개에 대해, 각각의 비교 함수로 sorting 해서 문제를 풀었다. 그래서 template으로 바꾸었다.

bool cmppoll(int i, int j) //막대기 비교
{
 if (arrPoll[i].t > arrPoll[j].t)
 {
  return true;
 }
 else if (arrPoll[i].t == arrPoll[j].t)
 {
  if (arrPoll[i].d > arrPoll[j].d)
  {
   return true;
  }
 }
 return false;
}
bool cmpmap(int a, int b) //map 비교 
{
 if (map[a] < map[b])
 {
  return false;
 }
 return true;
}

template <typename T >
void msort(int s, int e, T *arr, T *tmp, bool(cmp)(int, int))//s,e, 원본 배열, 임시 배열, 비교 함수(비교할 인덱스1,2)
{
 if (s >= e)return;

 int i, k, m, j;
 i = k = s;
 m = (s + e) / 2; 
 j = m + 1;
 msort(i, m, arr, tmp, cmp);
 msort(j, e, arr, tmp, cmp);

 while (i <= m || j <= e)
 {
  if (i > m || (j <= e && cmp(i, j)))
  {
   tmp[k++] = arr[j++];
  }
  else
  {
   tmp[k++] = arr[i++];
  }
 }

 for (int i = s; i <= e; i++)
  arr[i] = tmp[i];
}

hustoj 알고리즘 문제 추가 방법

 관리자 권한을 받은 후에는 add 문제 번호를 클릭하면 아래 페이지가 나옵니다. time limit이나 memory limit을 바꿔야할 때는 바꿔주고 description을 아래 처럼 적어 줍니다.

다음 아래를 보면 sample input, output 입력 란이 있는데 아래처럼 적어주면 문제 화면에 sample 이 보입니다. 그리고 그 밑 test input, output 은 test case 1개만 넣는다면 그곳에 넣어주면 됩니다. 추가 test case를 여러개 넣고 싶다면 문제 생성 하고 나서 편집에서 input, output txt 파일들을 여러개 추가 할 수 있습니다.

이제 기본적인것은 입력이 다 되었고, 아래그림에서 부가 설명이나 special judge(답이 여러개 일때) 옵션등을 체크해 주고 submit을 누르면 문제가 생성됩니다.

온라인 저지 site

 온라인 저지 사이트 한번 만들어 봤습니다. 기존 워드프레스 web server인 넷북을 구글블로그스팟으로 통합하고, 리눅스서버로 변경한 후에 hustoj를 설치 해봤습니다. php에 익숙하지 않아서.. 오래 걸리긴 했지만.. 잘돌아 갑니다. 넷북이라.. test case가 큰 경우도 한번 test해봐야겠네요.. 이건 나중에..ㅎ

http://deepaivision.com/JudgeOnline/

블로그 통합했어요~

 기존 개인서버에서 돌리던 워드프레스 사이트는.. 넷북을 서버로 쓰다보니 성능이 안따라 주네요. 지금은 구글블러거에 기존 도메인 연결해 놓았습니다. 일단 글을 적거나 하는것은 이곳에다가 하고, 기존에 있던 서버는 우분투로 갈아 탔습니다. 기존 서버에다가 hustoj로 온라인 채점 구현해볼까 합니다.

알고리즘 학습 자료

알고리즘 관련해서 책을 사시려고 추천해 달라는 분들이 계시는데.. 이쪽 분야 전문가에게 물어보니.. 시중에 나온 책들 보다 아래 자료가 훨씬 낳다고 합니다.  알고리즘에 대한 자료는 중급 2단원~ 고급 1,2단원에 나오니 아래 자료 참고하세요. 시중에 출판도 되었다고 하네요. koi pdf자료

 위 책에 대해 동영상강의도 있습니다. ~
koi 알고리즘 동영상 강의 리스트

독 확산 시간

디아블로 주술사에게 새로운 스킬이 주어졌다. 자기가 있는 위치에서 이 새로운 독 스킬을 쓰면 1초에 한번 확산하며 독이 퍼진다. 화면 전체에 퍼지면, 화면에 있는 모든 적들이 쓰러지는 궁극의 스킬이다.  독은 독이 퍼진 곳으로 부터 상,하, 좌, 우 확산할 수 있으며, 벽이 있는 곳은 확산 할 수 없다.  이 스킬을 썼을 때 화면에 모든 독이 퍼지는 시간을 출력 하라.

화면의 해상도는 N은 가로, M은 세로 라고 할때 4<M,N<1000 이다.

입력은 M 과 N 이 첫째 줄에 나오고, 사이에는 공백이 있다.
다음 줄은 주술사의 현재 위치가 X, 공백, Y 순으로 입력된다.
이후 줄 부터는 G와 B가 공백없이 입력된다. G는 초원이고, B는 벽이다.
아래 그램에서 주술사의 위치는 0,0이다.

G(주술사)	G	G	G
B	G	G	G
G	B	G	G
G	G	G	G

입력
4 4
0 0
GGGG
BGGG
GBGG
GGGG

출력
8

독 확산 시간 풀이 BFS – 주석추가

1. #include <stdio.h>
2. #pragma warning(disable:4996)
3. #include <queue>
4. using namespace std;
6. int N;//가로
7. int M;//세로
9. struct point
10. {
11. int x;
12. int y;
13. };
14. point sp; //시작위치
16. char map[1000][1000];//입력된것을 저장할 배열
17. char sel[1000][1000]; //방문 햇는지 정보를 저장할 배열
19. void resetsel()//방문정보를 reset할 함수. 지금은 필요 없지만 test set이 여러개 들어온다면 필요함.
20. {
21. for (int i = 0; i < M; i++)
22. {
23. for (int j = 0; j < N; j++)
24. {
25. sel[i][j] = 0;
26. }
27. }
28. }
30. int xx[4] = { -1, 1, 0, 0 };//4방향으로 확산하기 위한 벡터를 미리 만들어 놓습니다.
31. int yy[4] = { 0, 0, -1, 1 };
32. //que는 그냥 std를 씁니다.
33. queue<point> qpoint;
36. int Bfs()
37. {
38. int qsize = qpoint.size();
40. for (int i = 0; i < qsize; i++)//현재 que에 들어있는 만큼 확산
41. {
42. point p = qpoint.front(); //앞에것을 가쟈오고
43. qpoint.pop(); // 앞에것을 버립니다. 직접구현할때는 한번에 해도 됩니다.
44. sel[p.y][p.x] = 1;
45. for (int dir = 0; dir < 4; dir++) //확산하는 방향은 미리 정해놓은 벡터로 4방향만
46. {
47. point np;//새로운 포인트
48. np.x = p.x + xx[dir];
49. np.y = p.y+yy[dir];
50. if (np.x < 0 || np.y < 0 || np.x >= N || np.y >= M) continue; //map범위를 벗어나면 아무것도 안합니다.
51. if (sel[np.y][np.x] == 1) continue; //이미 방문한 곳이면 아무것도 안함.
52. if (map[np.y][np.x] == 'B')continue; //포인트가 벽이라면 아무것도 안함.
53. qpoint.push(np);//방문해야 하는곳이 맞다면 queue에 추가합니다.
54. }
55. }
57. //모두 완료 했다면 추가된 queue가 없을겁니다. 그럼 0리턴
58. return qpoint.size();
59. }
61. #define T (1)// 원래 문제는 Test Set이 여러개 들어옵니다.
62. int main(void)
63. {
64. freopen("input.txt", "r", stdin);
65. // Test Set 도 여러개고, 파일 용량이 크니, 복사하여 붙여넣기도 어렵고, 직접타이핑 넣는거는 불가능이요~
66. //그러니 freopen은 필수..
68. //입력 받는 부분
69. for (int t = 0; t < T; t++)
70. {
71. scanf("%d %d", &N, &M);
72. scanf("%d %d", &sp.x, &sp.y);
73. }
75. for (int i = 0; i < M; i++)
76. {
77. for (int j = 0; j < N; j++)
78. {
79. scanf(" %c", &map[i][j]);
80. }
81. }
83. resetsel();//방문정보를 reset할 함수. 지금은 필요 없지만 test set이 여러개 들어온다면 필요함.
85. qpoint.push(sp);//첫 시작 포인트를 넣습니다.
86. int cnt = 0;
87. while (Bfs()) //Bsf에서 리턴이 0 일때까지 확산합니다.
88. {
89. cnt++;
90. }
92. printf("%d", cnt);
94. return 0;
95. }