mminky's

[ 문제 ]

A tromino is a group of three unit squares arranged in an L-shape. Consider the following tiling problem: The input is an array of unit squares where is a positive power of 2, with one forbidden square on the array. The output is a tiling of the array that satisfies the following conditions: Every unit square other than the input square is covered by a tromino. No tromino covers the input square. T(n) = 7T ( 5 + n ) 10n for n > 1 T(1) = 1 n S(n) = 2 n − 1 S(n) n m × m mCOMPUTER ALGORITHMS - HW #2 2 No two trominos overlap. No tromino extends beyond the board. Write a divide-and-conquer algorithm that solves this problem.

[ 해결 코드 ]

(미해결 ㅠ 에러가 조금 있는 것 같다ㅠㅠ)

#include<stdio.h>
#define m 128 //2^7
int arr[m][m];
int tile_num=0;
void put_tile(int x1, int y1,	int x2, int y2,
	int x3, int y3) {
	tile_num++;
	arr[x1][y1] = tile_num;
	arr[x2][y2] = tile_num;
	arr[x2][y2] = tile_num;
}

void calculate_tiling(int n, int x, int y) {
	int a=0, b=0;

	// 2*2 만 남았을 때 빈 칸 빼고 다 타일 놓기
	if (n == 2) {
		tile_num++;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[x + i][y + i] == 0) {
					arr[x + i][y + i] = tile_num;	
				}
			}
		}
		return 0;
	}

	//빈 칸(a,b) 찾기
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (arr[i][j] != 0) {
				a = i, b = j;
			}
		}
	}

	//2 1
	//3 4

	//빈 칸이 1사분면 (+,+)
	if (a >= x + (n / 2) && b >= y + (n / 2))
		put_tile(x + (n / 2) - 1, y + (n / 2),
			x + (n / 2), y + (n / 2) - 1,
			x + (n / 2) - 1, y + (n / 2) - 1);

	//빈 칸이 2사분면 (-, +)
	else if (a < x + (n / 2) && b >= y + (n / 2))
		put_tile(x + (n / 2), y + (n / 2) -1,
			x + (n / 2), y + (n / 2),
			x + (n / 2) - 1, y + (n / 2) - 1);


	//빈 칸이 3사분면 (-, -)
	else if (a < x + (n / 2) && b < y + (n / 2))
		put_tile(x + (n / 2), y + (n / 2) - 1,
			x + (n / 2), y + (n / 2),
			x + (n / 2) - 1, y + (n / 2) );


	//빈 칸이 4사분면 (+, -)
	else if (a >= x + (n / 2) && b < y + (n / 2))
		put_tile(x + (n / 2) -1, y + (n / 2),
			x + (n / 2), y + (n / 2),
			x + (n / 2) - 1, y + (n / 2) - 1);

	//divide and conquer
	calculate_tiling(n / 2, x, y + (n / 2));
	calculate_tiling(n / 2, x, y);
	calculate_tiling(n / 2, x + (n / 2), y);
	calculate_tiling(n / 2, x + (n / 2), y + (n / 2));

	return 0;
}

int main()
{
	//빈 셀
	arr[0][0] = -1;

	int n = 8; //128=2^7 -> 7+1=8
	calculate_tiling(n, 0, 0);

	//결과출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ",arr[i][j]);
		}
		printf("\n");
	}

	return 0;
}

[ 결과 ]

[ 참고 사이트 ]

www.geeksforgeeks.org/tiling-problem-using-divide-and-conquer-algorithm/

[ 문제 ]

Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and disks of different sizes. The object is to move the disks that are stacked, in decreasing order of their size, on one of the three pegs to a new peg using the third one as a temporary peg. The problem should be solved according to the following rules: 1 when a disk is moved, it must be placed on one of the three pegs; 2 only one disk may be moved at a time, and it must be the top disk on one of the pegs; and 3 a larger disk may never be placed on top of a smaller disk. (a) Show for your algorithm that . Here denotes the number of steps (moves), given an input of disks.)

[ 해결 코드 ]

#include<stdio.h>
int count = 0;
int hanoi(int disk_num, char from_peg, char to_peg, char tmp_peg) {
	if (disk_num == 1) {
		printf("Move disk#1 from %c to %c \n",from_peg, to_peg);
		count++;
		return;
	}
	hanoi(disk_num - 1, from_peg, tmp_peg, to_peg);//한  번에 한개(1)씩 옮김
	printf("Move disk#%d from %c to %c \n", disk_num,from_peg, to_peg);
	count++;
	hanoi(disk_num - 1, tmp_peg, to_peg, from_peg);

}
int main()
{
	int n = 3;
	int result;
	result = hanoi(n, 'A', 'C', 'B');
	printf("%d", result);
	return 0;
}

[ 결과 ]

n=3 이므로 2^3 - 1 = 7

총 7번이 실행된다.

[ 해결 아이디어 ]

[ 참고 사이트 ]

www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

공백을 기준으로 문자열을 받는 다음의 코드에 익숙해졌다.

a,b=input().split()

그러다 엔터(\n)를 기준으로 문자열을 받는 문제에서 헷갈리게 되었다.

a,b=input().split('\n') 를 입력해봤지만 작동하지 않았다.

하지만 다시 생각해보니 그냥 하나씩 입력받으면 되는 거였다..

[결론]

엔터를 기준으로 문자를 입력받고 싶으면 input 두 번 하자!

a=input()
b=input()

[ 연관 문제 ]

백준 사분면 문제 이다.

www.acmicpc.net/problem/14681

[ 해결 코드 ]

a=input()
b=input()
a=int(a)
b=int(b)

if(a>0 and b>0):
    print('1')
elif(a<0 and b>0):
    print('2')
elif(a<0 and b<0):
    print('3')
else:
    print('4')

비주얼 스튜디오에서

c언어에서 scanf 등을 이용할 때 발생한다.

나의 경우도 fopen을 할 때 발생을 했다.

그래서 다음의 코드를 입력해주었다.

하지만 해결되지 않았다.

#define _CRT_SECURE_NO_WARNINGS

그래서 전처리기 설정을 변경하기로 했다.

프로젝트 > (프로젝트명)속성 을 클릭한다.

그리고 C/C++ > 전처리기 > 다음의 코드를 추가한 후 > 확인 클릭

 _CRT_SECURE_NO_WARNINGS

잘 작동이 됩니다 :)

우선 아나콘다 프롬프트를 실행한다.

cd 명령어를 이용해 원하는 폴더로 이동한다.

이 폴더에서 저장되고 동작되기 때문에 빈 폴더를 추천한다!

주피터 노트북을 입력하면 자동으로 실행된다.

jupyter notebook

인터넷 창이 하나 실행되면서 주피터 노트북이 실행된다.

코드 파일(.ipynb)과 폴더 안에 들어있는 여러 파일들이 보인다.

Untitled.ipynb 파일을 클릭한 후 다음과 같이 코드를 입력한다.

실행은 간단히 ctrl + Enter를 누르면 한 줄씩 실행이 된다.

상단에 있는 버튼들로 셀 추가/ 삭제가 가능하다.

( + ) : 코드 셀 추가

( 가위 ) : 코드 셀 삭제

* 3항 연산자

x if ~ else y : ~ 이면 x를, 그렇지 않으면 y를 이용한다.

a,b=input().split()
a=int(a)
b=int(b)
c=(a if(a>=b) else b) #큰 수를 c에 저장
print(int(c))

(참고 : codeup.kr/problem.php?id=6063 )

* 최대공약수 구하기

Write an algorithm that finds the greatest common divisor of two integers.

#include<stdio.h>

int main()
{
    int a, b; //2 integers
    int gcd;
    printf("Enter 2 int:");
    scanf_s("%d %d", &a,&b);
    for (int i = 1; i <= a; i++) {
        if (a % i == 0 && b % i == 0)
            gcd = i;
    }
    printf("%d", gcd);
    return 0;
}

[ Output ]

* output 예상하기, 구하기

#include <iostream>

using namespace std;
int main(void) {
	int i=1, j=0, n=6;
		while (j <= n / 2) {
			i = 1;
			while (i <= j) {
				cout << j << i;
				i++;
			}
			j++;
		}
	return 0;
}

[ Output ]

* O(log2n)인 지수 승 함수 (my_pow)

ive a algorithm that computes the remainder when is divided by . For simplicity, you may assume that is a power of . That is, for some positive integer .

-> 이 문제를 풀다가 pow는 double 일 때만 된다는 것을 알게되었다.

    pow(x,n)%p 를 하고 싶었으나 %연산은 int일 때만 된다고 해서 my_pow를 만들기로 했다.

#include<stdio.h>

int my_pow(int x, int n){
    if(n==0)    //exception(n = 2^k)
        return 1;
    else {
        int root_x = my_pow(x, n / 2);
        if (n % 2 == 0) //even exp(지수)
            return root_x * root_x;
        else            //odd exp(지수)
            return root_x * root_x * x;
    }
}

int main()
{
    int x = 3, n = 5;
    int result = my_pow(x, n); //x^^n

    int p = 4;
    int mod = result % p; //(x^^n) % p
    printf("%d", mod);
     return 0;
}

[ Output ]

 ( 243 % 4 = 3 )

[ 참고자료 ]

(참고 onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/ )

* 배열을 둘로 나눴을 때 각 배열의 합의 차가 최소가 되도록 나누기

(사실 원래 문제는 이거다..ㅠ

Give an algorithm for the following problem. Given a list of distinct positive integers, partition the list into two sublists, each of size , such that the difference between the sums of the integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that is a multiple of .)

#include<stdio.h>
#include<stdlib.h>
#define arr_size 6
int main() {
	int left_sum=0, right_sum=0;
	int sum = 0;
	int num[arr_size] = { 5, 2, 1, 4, 6, 3 }; //array
	
	for (int i = 0; i < arr_size; i++)
		sum += num[i];
	//printf("%d", sum);

	right_sum = sum;
	int diff = 99999999;
	int diff_idx;
	for (int j = 0; j < arr_size; j++) {
		left_sum += num[j];
		right_sum -= num[j];
		if (abs(left_sum - right_sum) < diff) {
			diff = abs(left_sum - right_sum);
			diff_idx = j;
		}
		
	}
	printf("diff_idx: %d", diff_idx);
	return 0;
}


//원래는 딱 반을 나눴을 때 합의 차가 최소가 되도록 해야하는문제
//그냥 둘로 나눴을 때 합의 차가 최소가 되는 idx값 출력

[ Output ]

(참고 : m.blog.naver.com/PostView.nhn?blogId=puppy3698&logNo=221576346409&proxyReferer=https:%2F%2Fwww.google.com%2F )

* 주석

[한 줄 주석]

#을 입력하면 된다.

#한 줄 주석 입니다

[여러 줄 주석]

''' 을 입력하면 된다.

'''
파이썬
여러 줄
주석 입니다.
'''

* 따옴표 출력

escape 문자 \(역슬래쉬)을 이용한다.

출력을 원하는 '나 "나 \ 앞에 \을 붙인다. (\'나 \"나 \\)

'Hello World'를 그대로 출력하고 싶으면 다음과 같이 '앞에 \를 붙이면 된다.

print(" \' Hello World \' ")

print("\'Hello World\'")

\을 출력하고 싶으면 역시 \\ 이렇게 입력하면 된다.

"C:\Download\'hello'.py"를 그대로 출력하고 싶으면 다음과 같이 입력하면 된다.

print('\"C:\\Download\\\'hello\'.py\"')

* 키보드 input

a = input()하면 키보드로 입력을 받아 a라는 변수에 저장한다.

input은 줄 단위로 받아들인다.

따라서 a,b=input().split()을 하면 aa bb라는 입력에서 공백을 기준으로 나눠서

a = aa, b= bb이렇게 입력을 해준다.

a,b=input().split()
print(a)
print(b)

* 16진수로 바꾸기

print('%x'%바꿀숫자) 소문자로 출력

#우선 a를 키보드 입력받은 후 정수로 변환
a=int(input())

#a에 저장되어있는 값을 heXadecimal(16진수) 소문자 형태로 출력
print('%x'%a)

print('%X'%바꿀숫자) 대문자로 출력

print('%X'%a)
#a에 저장되어있는 값을 heXadecimal(16진수) 대문자 형태로 출력

* 비트연산자 shift

<< : 2배 곱하기

>> : 2로 나누기

비트연산자를 이용해서 *2 하기

a= input()
print( int(a) << 1 )

(참고 codeup.kr/problem.php?id=6046 )