별집사의 IT세상

인터넷이 발달하여 사람들이 웹서핑을 많이 하는데, 웹브라우져를 켜서 보통은 19번의 클릭을 한다고한다. 페이지를 전환하는 상태가 아래 그래프와 같이 주어진다면, 1번 페이지에서 2번, 3번, 4번 페이지로 갈 때의 가장 짧은 페이지 클릭 횟수는 1,1,2이고, 2번 페이지에서 1번, 3번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 3,2,1이고, 3번 페이지에서 1번, 2번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 1,2,3이고, 4번 페이지에서 1번, 2번, 3번 페이지로 가는 가장 짧은 페이지 클릭 횟수는 2,3,1이다. 이때, 가장 짧은 페이지 클릭 횟수의 합을 모두 구하면 1+1+2+3+2+1+1+2+3+2+3+1=22 이다.이 그래프에서 모든 쌍은 12쌍이 나오기 때문에 ..

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들의 크..

알고리즘을 짤 때 많이 쓰이는 큐와 스택 스택은 의미처럼 박스에 차곡차곡 쌓는다고 생각하면 된다. 열려있는 구멍은 위 뿐이라 뺄 때도 제일 나중에 들어간 값이 나오게 된다. 즉 LIFO(Last In First Out) 보통 맨 위의 위치를 TOP으로 설정하고, 꺼내는 함수를 Pop, 넣는 함수를 Push로 한다. int stack[n]; int TOP = 0; void Push(int data){ if(TOP==n){ printf("Stack is Full\n"); } else{ stack[TOP++] = data; } } int Pop(){ if(TOP){ printf("Stack is Empty\n"); return -1; } else{ return stack[--TOP]; } } 큐는 구멍이 위와..

입력조건 출력조건 입력 출력1 4 13 2 4 6 8Case #1 12 dp를 이용해 해당 이수 학점을 들을 수 있을 때는 1, 없을 때는 0으로 저장하였다. 해당 학점(temp)에서 각 학점(sub[i])을 뺐을 때 나오는 학점을 들을 수 있다면,(dp[temp-sub[i]]==1) 해당 학점도 들을 수 있게 된다. 1학점부터 M학점까지 계산하였고, M에서 최대한 가까운 값을 출력하였다. 최적화로 생각해 볼 것은 각 케이스마다 배열을 동적 할당하여 메모리를 줄이는 방법과, 문제에 설명이 안되있지만 과목이 크기순으로 정렬을 확인하는 점이다. 문제에 제대로 설명이 안되어 있는데, 과목을 중복으로 들어도 되게 코딩을 했는데 통과한 걸 보면 중복으로 들어도 되나보다(대학 강의를 어떻게 중복으로 듣나..) #i..

입력 조건 출력 조건 입력 출력1 3 3 2 3 2 3 2 3 2 3Case #1 2 뒤에서 연속된 0의 최대 개수일때 열린다고 했으므로 고등학교 시절 뒤에 0이 최대로 오는 문제와 같이 생각해보면 된다. 각 경비를 곱한다고 했으므로 각 경비를 소인수 분해하여 2의 개수와 3의 개수만 저장하고 마지막까지 갔을 때 두개의 페어가 최대값이 되는 경우를 찾으면 된다. 해당 문제에서는 상, 하, 좌, 우로 이동할 수 있다고 나와있지만, 최단거리로 가야된다고 했으므로 실질적으로 이동가능 한 경우는 하, 우 뿐이다. 처음에 고민했던 부분은 최대값이 각 지점까지 왔을 때 최대값과 같은 가 였는 데 이는 간단한 예로 아님을 확인 할 수 있다. 만일 3*3의 미로에서 배열 1,1로 오는 2가지 경우의 수를 예로 들어보자..

5분도 안걸리는 너무 쉬운 문제; 문제선정을 잘 못함.. 계산하기 쉽게 1~9까지의 세제곱수를 행렬로 미리 계산해놓고 같은 쭉 같은 값 나올때마다 출력하면 된다. #include int main() { int cube[10]; int N; int i; int sum; int a, b, c; int count = 0; for (i = 0; i < 10; i++) { cube[i] = i * i * i; } scanf("%d", &N); for (i = 100; i 999) { break; } a = i / 100; b = (i % 100) / 10; c = (i % 10); sum = cube[a] + cube[b] + cube[c]; if (sum == i) { printf("%d\n", i); coun..

행, 열 중 하나를 기준으로 더해본 후 세가지 경우로 나누어서 생각한다. (여기서는 행을 기준으로 생각) 1. 각 행의 합이 모두 짝수이다 2. 각 행의 합이 하나만 홀수이다 3. 각 행의 합이 두개 이상 홀수이다 이 상황에서 앞의 기준의 반대(행이 기준이였으면 열)를 위와 마찬가지로 세가지로 나눌 수 있다. (여기서는 열을 기준으로 생각) 1. 각 행의 합이 모두 짝수이고 각 열의 합도 모두 짝수이다 -> OK 2. 각 행의 합이 하나만 홀수이고, 각 열의 합도 하나만 홀수이다 -> Change bit 3. 각 행의 합이 두개 이상 홀수이거나, 각 열의 합이 두개 이상 홀수이다. -> Corrupt #include int main() { int a[101][101]; int N; int i, j; in..

코드그라운드 노말 44번문제 입력 출력 관리자를 1, 2 대신 0, 1로 지정하고(코딩의 편의를 위해) 초기에 모든 영역의 관리자를 0으로 초기화 해준다. 인접하는 지역 번호를 받으면서 인접 지역의 관리자를 반대로 저장하였다 ( 0 = !1, 1 = !0) 모든 경우의 인접 지역 관리자를 조사하여 같은 관리자가 있는 경우 result를 0으로 변경하고 종료한다. #include #include int main(void) { setbuf(stdout, NULL); int TC; int test_case; int N, M; // 200, 1000 int start[1000]; int end[1000]; int num[201]; int i; int result; scanf("%d", &TC); for (tes..

대단한 능력을 가진놈이다. 공부한 과목 K개의 최대 합계 점수를 구하면 되기 때문에 높은 순서로 정렬해서 K개만큼 더하면 된다. 단 N의 최대값이 20만개라 시간초과 걸리는 것만 조심하면 된다. 간단하게 C 내부의 stdlib.h에 있는 qsort 이용해서 정렬하면 쉽게 해결 주어진 코드 외에 작성 하는 코드는 네 줄이면 된다. int cmp(const void* a, const void* b) { return *(int*)b - *(int*)a; }; qsort(val, N, sizeof(int), cmp); for (i = 0; i