HMAC

SHA-1(Secure Hash Algorithm)

HMAC-SHA1

이미지를 M X N 배열로 표현하는 간단한 대화형 그래픽 편집기  프로그램을 만들어보자.

 입력

한 줄에 하나씩의 1개 문자의 명령으로 구성됨.  매개변수는 스페이스로 분리됨 

픽셀좌표는 1 이상 M이하의 열, 1이상 N이하의 행 으로 표현됨. 

표의 왼쪽 위 꼭지점이 원점이며, 색은 대문자로 지정함 

출력

명령을 제외한 문자는 무시하고,  S Name 명령은 Name 으로 주어진 파일명 출력 후

현재 이미지 내용을 출력함.

graphic_editor.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct _Image {
	char *pixels;
	int r, c;
} Image;

typedef struct _Point {
	int x, y;
} Point;


Point make_point(int x, int y);

 
Image* initiate(int row, int col);
void fill_color(Image *image, Point point, char color);
void show(Image *image);
void flood(Image *image, Point point, char color);
void flood_recur(Image *image, Point point, char color, char r_color); 
void horizontal_line(Image *image, int x, int y1, int y2, char color);
void vertical_line(Image *image, int x1, int x2, int y, char color);
void rectangle(Image *image, Point left_top, Point right_bottom, char color);
void clear(Image *image, char color);


int main (int argc, char const* argv[])
{
	char cmd, color;
	char buf[MAX_SIZE], name[MAX_SIZE];
	int m, n, x1, x2, y1, y2;
	Image *image = 0;

	while (fgets(buf, 100, stdin) != NULL && strncmp(buf, "X", 1) != 0) {
	 	if (strncmp(buf, "I ", 2) == 0) {
		
			sscanf(buf, "%c %d %d", &cmd, &m, &n);
			image = initiate(n, m);
			
		} else if (strncmp(buf, "C", 1) == 0) {\
	
			clear(image, '0');
			
		} else if (strncmp(buf, "L ", 2) == 0) {
			
			sscanf(buf, "%c %d %d %c", &cmd, &x1, &y1, &color);
			fill_color(image, make_point(x1-1, y1-1), color);	
			
		} else if (strncmp(buf, "V ", 2) == 0) {
			
			sscanf(buf, "%c %d %d %d %c", &cmd, &x1, &y1, &y2, &color);
			vertical_line(image, x1-1, y1-1, y2-1, color);
			
		} else if (strncmp(buf, "H ", 2) == 0) {
			
			sscanf(buf, "%c %d %d %d %c", &cmd, &x1, &x2, &y1, &color);
			horizontal_line(image, x1-1, x2-1, y1-1, color);
			
		} else if (strncmp(buf, "K ", 2) == 0) {
			
			sscanf(buf, "%c %d %d %d %d %c", &cmd, &x1, &y1, &x2, &y2, &color);
			rectangle(image, make_point(x1-1, y1-1), make_point(x2-1, y2-1), color);
			
		} else if (strncmp(buf, "F ", 2) == 0) {
		
			sscanf(buf, "%c %d %d %c", &cmd, &x1, &y1, &color);
			flood(image, make_point(x1-1, y1-1), color);
			
		} else if (strncmp(buf, "S ", 2) == 0) {
			
			sscanf(buf, "%c %s", &cmd, name);
			printf("%s \n", name);
			show(image);
		}
	}
	
	return 0;
}

Point make_point(int x, int y) {
	return (Point){x, y};
}



// 이미지 생성 - I m n 
Image* initiate(int row, int col) {
	Image *image = (Image*)malloc(sizeof(Image));
	
	image->pixels = (char*)malloc(row*col); 
	image->r = row;
	image->c = col;
	
	clear(image, '0');
	
	return image;
}

// 주어진 픽셀에 칠하기 - L x y c
void fill_color(Image *image, Point point, char color) {
	image->pixels[point.y*image->c +  point.x] = color;
}

// 이미지 출력 
void show(Image *image) {
	int i;
	
	for (i = 0; i < image->r * image->c; i++) {
		putchar(image->pixels[i]);
		
		if (i % image->c == image->c - 1) {
			putchar('\n');
		}
	}
}

// 점람 채우기 
void flood(Image *image, Point point, char color) {
	char r_color = image->pixels[point.y*image->c +  point.x];
	flood_recur(image, point, color, r_color);
}


void flood_recur(Image *image, Point point, char color, char r_color) {
	int x = point.x;
	int y = point.y;
	int index = y*image->c + x;
	
	// 경계를 벗어났거나 같은 영역이 아니면 종료 
	if (image->pixels[index] != r_color || x < 0 || y < 0 || x >= image->c || y >= image->r) {
		return;
	}
	image->pixels[index] = color;
	
	flood_recur(image, make_point(x, y+1), color, r_color);
	flood_recur(image, make_point(x+1, y), color, r_color);
	flood_recur(image, make_point(x, y-1), color, r_color);
	flood_recur(image, make_point(x-1, y), color, r_color);
}


// 수평 직선  - H
void vertical_line(Image *image, int x, int y1, int y2, char color) {
	Point left_top, right_bottom;
	
	left_top.x = right_bottom.x = x;
	left_top.y = y1;
	right_bottom.y = y2;
	
	rectangle(image, left_top, right_bottom, color);
}


// 수직 직선  - V
void horizontal_line(Image *image, int x1, int x2, int y, char color) {
	Point left_top, right_bottom;
	
	left_top.x = x1;
	right_bottom.x = x2;
	left_top.y = right_bottom.y = y;
	
	rectangle(image, left_top, right_bottom, color);
}

// 사각형 그리고 채우기 - K
void rectangle(Image *image, Point left_top, Point right_bottom, char color) {
	int i, j;
	
	for (i = left_top.y; i <= right_bottom.y; i++) {
		for (j = left_top.x; j <= right_bottom.x; j++) {
			image->pixels[i*image->c + j] = color;
		}
	}
}


void clear(Image *image, char color) {
	int i;
	for (i = 0; i < image->r * image->c; i++) {
		image->pixels[i] = color;
	}
}

LCD 디스플레이 형태로 숫자를 출력하되 크기 입력 s에 의해 출력하는 숫자의 크기를 조절할 수 있다.

이 때 각 숫자는 s+2개의 열과  2s+3 개의 행 크기를 차지하게  된다. 행문자는 ' | ',  열 ' -' 를 사용. 

각 자리 수 사이에는 1칸씩 공백을 둔다. 

입력 : s n  (크기 s, 출력할 정수 n)

출력 :  LCD 디스플레이 형태로 n을 출력 

문제해결

두 가지 방법으로 해결법을 찾아 보았다. 첫번째는 0 ~ 9 까지 각 수를 인자 s에 따라 출력하는 

일반적인 방법이다. 두번 째는 LCD 패널을 7가지 구성요소로 분리하고, 각 요소를 7개의 함수로 

만들고, 0~9중 해당하는 수가 입력된 경우에만 해당 요소를 출력하는 방법이다. 

lcd_display.c

/*
	입력 : s(크기) , n(출력할 수)
	출력 : LCD Display 형태로 n를 출력 
	조건 : s+2 열, 2s+3 행을 사용 
*/

#include <stdio.h>
#include <stdlib.h>

#define ROW(s) (2*s + 3)
#define COL(s) (s+2)

#define ROW_CHAR '@'
#define COL_CHAR '@'
#define SPACE ' '

void f0(int n, int s);
void f1(int n, int s);
void f2(int n, int s);
void f3(int n, int s);
void f4(int n, int s);
void f5(int n, int s);
void f6(int n, int s);

void lcd_display(int s, char *buf);

int main (int argc, char const* argv[])
{
	int s;
	char buf[10];
	
	scanf("%d %s", &s, buf);
	
	lcd_display(s, buf);

	return 0;
}


void lcd_display(int s, char *buf) {
	int i;
	char *p = buf;
	
	if (s == 0 && atoi(buf) == 0) {
		return ;
	}

	p = buf;
	while (*p != '\n' && *p != '\0') {
		f0(*p-'0', s);
		p++;
	}
	putchar('\n');
	
	for (i = 0; i < (ROW(s)-1)/2; i++) {	
		p = buf;
		while (*p != '\n' && *p != '\0') {
			f1(*p-'0', s);
			p++;
		}
		putchar('\n');
	}
	
	p = buf;
	while (*p != '\n' && *p != '\0') {
		f3(*p-'0', s);
		p++;
	}
	putchar('\n');

	for (i = 0; i < (ROW(s)-1)/2; i++) {
		p = buf;
		while (*p != '\n' && *p != '\0') {
			f4(*p-'0', s);
			p++;
		}
		putchar('\n');
	}
		
	p = buf;
	while (*p != '\n' && *p != '\0') {
		f6(*p-'0', s);
		p++;
	}
	putchar('\n');
}


// 가장 첫행 
void f0(int n, int s) {
	int i;
	char ch = COL_CHAR;
	
	if (n == 1 || n == 4){
		ch = SPACE;
	} 
	for (i = 0; i < COL(s)-1; i++) {
		putchar(ch);
	}
	putchar(SPACE);
}

void f1(int n, int s) {
	int i;
	char ch = ROW_CHAR;
	
	if (n == 1 || n == 2 || n == 3 || n == 7) {
		ch = SPACE;
	}
	putchar(ch);
	for (i = 0; i < COL(s)-3; i++) {
		putchar(SPACE);
	}
	f2(n, s);
}

void f2(int n, int s) {
	char ch = ROW_CHAR;
	
	if (n == 5 || n == 6){
		ch = ' ';
	}
	putchar(ch);
	putchar(SPACE);
}
// 중간 행 
void f3(int n, int s) {
	int i;
	char ch = COL_CHAR;
	
	if (n == 0 || n == 1 || n == 7){
		ch = ' ';
	}
	for (i = 0; i < COL(s)-1; i++) {
		putchar(ch);
	}
	putchar(SPACE);
}

void f4(int n, int s) {
	int i;
	char ch = ROW_CHAR;
	
	if (n == 1 || n == 3 || n == 4 || n == 5 || n == 7 || n == 9){
		ch = SPACE;
	}
	putchar(ch);
	for (i = 0; i < COL(s)-3; i++) {
		putchar(SPACE);
	}
	f5(n, s);
}

void f5(int n, int s) {
	char ch = ROW_CHAR;
	
	if (n == 2){
		ch = ' ';
	}
	putchar(ch);
	putchar(' ');
}

// 끝행 
void f6(int n, int s) {
	int i;
	char ch = COL_CHAR;
	
	if (n == 1 || n == 4 || n == 7){
		ch = SPACE;
	}
	for (i = 0; i < COL(s)-1; i++) {
		putchar(ch);
	}
	putchar(SPACE);
}

여행에 참석한 학생들이 식비, 호텔비, 택시비,  비행기표를 한명씩 부담하고, 나중에 1센트 단위 내에서  

쓴 돈이 같아지고, 돈을 주고 받을 때 서로 전달 해야하는 최소액수를 구해보자.

입력

여행에 참석한 학생 수와 각 학생이 부담한 비용을 입력으로 받는다. 단 학생수는 1000명 이하이고, 

어떤 학생도 10,000.00 달러 이상 지출하지 않는다. 단위는 달려이고, 0이 입력되면 종료한다.

출력

각 학생이 사용한 금액이 같아지기 위해 전달되어야 하는 금액의 총합

ex)

입력

3

15.00

15.01

3.00

3.01

0

 

출력

$11.99

해결과정

각 학생이 소비한 금액의 평균을 구해서, 평균액보다 적은 돈을 낸 사람에 대해  평균액과 낸 금액의 차에 합을  

구하면 된다. 이 때 1센트 이내에  차이가 있어야 하기 때문에  평균액을 구할 때 소수 셋째짜리에서 반올림을 수행한다.

반올림을 위해, 평균액에 1000을 곱하고, 1의 자리에서 반올림 후 다시 1000으로 나눠주는 과정을 거치게 된다. 

trip_fee.c

/*
	입력 : 여행에 참여한 학생수 (정수 n <= 1000), 각 학생이 낸 경비 
	출력 : 각 학생이 사용한 금액이 같아지기 위한 금액 총합 	
*/

#include <stdio.h>
#include <stdlib.h>

double total_fee(double* fees, int n);

int main (int argc, char const* argv[])
{
	int i, n;
	double total, *fees;
	
	scanf("%d", &n);
	fees = (double*)malloc(n * sizeof(double));
	
	for (i = 0; i < n; i++) {
		scanf("%lf", fees + i);
	}
	
	total = total_fee(fees, n);
	
	printf("$%.2lf \n",  total);
	
	free(fees);
	
	return 0;
}


double total_fee(double* fees, int n) {
	int i, share, rem;
	float sum, d_share, total; 
		
	sum = d_share = total = 0.0;
	for (i = 0; i < n; i++) {
		sum += fees[i];
	}
	share = (sum * 1000) / n;
	
	if ((rem = share % 10) >= 5) {
		share += 10;
	}
	share -= rem;
	d_share = share / 1000.0;

	for (i = 0; i < n; i++) {
		if (fees[i] > d_share) {
			total += fees[i] - d_share;
		}
	}
	
	return total;
}

윈도우의 지뢰찾기 게임을 기억할 것이다. M x N 크기 지뢰밭 각 셀은 인접한 셀에 몇개의 지뢰가 존재하는지

나타내는 수를 가지고 있다.  *를 지뢰하고 하면...

 * . . .

  . . . . 

 . * . .

  . . . .

와 같은 지뢰밭은 다음과 같은 값을 가지게 된다.

* 1 0 0

2 2 1 0

1 * 1  0

1 1 1 0

입력 : 행의 개수 n, 열의 개수 m /   n행 m열의 지뢰밭 

출력 : 인접한 8개의 이웃에 있는 지뢰의 개수가 계산된 지뢰밭  출력

ex) 

입력  

4 4

* . . . 

. . . . 

. . . .

. * . .

 

출력

* 1 0 0

2 2 1 0

1 * 1 0

1 1 1 0

문제해결

지뢰가 아닌 모든 셀에 대해서 이웃하는 지뢰의 개수를 카운팅한다. 카운팅은 상 하 좌 우 인덱스를 변화시켜 지뢰의 개수를 

카운팅하되 행과 열에 대한 바운더리를 초과하지 않도록 검사를 수행한다.

mine_sweeper.c

/*
	입력 : 행과 열의 개수 n m / 지뢰밭 
	출력 : 이웃하는 지뢰개수가 계산된 지뢰밭 
*/

#include <stdio.h>
#include <stdlib.h>

#define MINE '*'
#define EMPTY '.'
#define MAX_BUF 200

typedef struct _Mine {
	int n, m;
	char *mines;
} Mine;


Mine *input();
void construct_mine(Mine *_mine);
void destruct_mine(Mine *_mine);

int count_mines(Mine *mine, int r, int c);
void output();


int main (int argc, char const* argv[])
{
	Mine *mine;
	
	while (mine = input()) {
		construct_mine(mine);
		output(mine);
		destruct_mine(mine);
	} 
	
	return 0;
}

Mine *input() {
	int m, n, i, j;
	Mine *mine;
	char buf[MAX_BUF];
	char *p_buf = buf;
	
	scanf("%d %d", &m, &n);
	getchar(); // 개행 문제를 버림 
		
	if (m == 0 && n == 0) {
		return 0;
	}
	
	mine = (Mine*)malloc(sizeof(Mine));
	mine->m = m;
	mine->n = n;
	mine->mines = (char*)malloc(m * n + 1);
	
	for (i = 0; i < m; i++) {
		p_buf = buf;
		fgets(buf, MAX_BUF, stdin);
		j = 0;
		while (*p_buf != '\0') {
			if (*p_buf == '*' || *p_buf == '.') {
				mine->mines[n*i + j] = *p_buf;
				j++;
			}
			p_buf++;
		}
	}	
	return mine;
}

// 모든 셀에 지뢰 개수를 카운팅 
void construct_mine(Mine *_mine) {
	int i, j;
	Mine *mine = _mine;
	int m = mine->m, n = mine->n;
	
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (mine->mines[i*n + j] != '*') {
				mine->mines[i*n + j] = count_mines(mine, i, j);
			}
		}
	}
}

void destruct_mine(Mine *_mine) {
	free(_mine->mines);
	free(_mine);
}


//  특정 셀의 인접한 이웃의 지뢰의 개수를 카운팅 
int count_mines(Mine *mine, int r, int c) {
	int index, count = 0;
	int m = mine->m, n = mine->n;
	char *cell = mine->mines;
	
	if (r - 1 >= 0 && c - 1 >= 0) {
		index = (r - 1)*n + c - 1;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (r - 1 >= 0) {
		index = (r - 1)*n + c;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (r - 1 >= 0 && c + 1 < n) {
		index = (r - 1)*n + c + 1;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (c - 1 >= 0) {
		index = r*n + c - 1;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (c + 1 < n) {
		index = r*n + c + 1;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (r + 1 < m && c - 1 >= 0) {
		index = (r + 1)*n + c - 1;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (r + 1 < m) {
		index = (r + 1)*n + c;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	if (r + 1 < m && c + 1 < n) {
		index = (r + 1)*n + c + 1;
		if (*(cell + index) == '*') {
			count++;
		}
	}
	return count;
}


// 결과 출력 
void output(Mine *mine) {
	int i;
	printf("Field #:");
	for (i = 0; i < mine->m * mine->n; i++) {
		if (*(mine->mines + i) == '*') {
			printf("%c ", *(mine->mines + i));
		} else {
			printf("%d ", *(mine->mines + i));
		}
		if (i % mine->n == mine->n - 1) {
			printf("\n");
		}
	}
	printf("\n");
}

정수 n에서 n이 짝수면 2로 나누고, 홀수면 3을 곱하고 1을 더한다. 이렇게 만들어지는 수를 

다시 n으로 놓고,  n=1이 될 때까지 반복해서 나오는 수들의 개수를 정수 n의 사이클 길이(cycle length)라고 한다. 

(1을 포함)

i, j 두개의 수가 주어졌을 때, 두 수 사이의 모든 수(i, j 포함)들 중 최대 사이클 길이를 구하라 

입력 : i j     (  0 <= i, j <= 1000000)

출력 : i j cycle_length

 

ex) 입력 : 1 10

       출력 : 1 10 20

3n_1.c

/*
	입력 : 정수 i, j
	출력 : 정수 i, j, 최대 사이클 길이 
*/

#include <stdio.h>

int cycle_length(int num);

int main (int argc, char const* argv[])
{
	int left_bound, right_bound, max = 0;
	int i, cycle_len;
	
	scanf("%d %d", &left_bound, &right_bound);
	
	for (i = left_bound; i <= right_bound; i++) {
		cycle_len = cycle_length(i);
		if (cycle_len > max) {
			max = cycle_len;
		}
	}
	
	printf("%d %d %d \n", left_bound, right_bound, max);
	
	return 0;
}

int cycle_length(int num) {
	int n = num, cn = 1;
	
	while (n != 1) {
		if (n % 2) {
			n = 3*n + 1;
		} else {
			n = n >> 1;
		}
		cn++;
	}
	return cn;
}