< 대해적시대 />
< 대해적시대 />

개발자의 기록성장

인생의 종착점은 라프텔

[C언어] 함수 포인터 개념과 활용

개인적으로 C언어의 꽃이라고 생각되는 함수 포인터 개념을 이번 포스팅에서 다뤄보려고 합니다. 1. 함수 포인터란?일반적으로 포인터란 자기 자신 이외의 메모리 주소를 담는 변수라고 표현됩니다.이와 비슷하게 함수 포인터는 함수의 주소를 담는 변수라고 표현됩니다. 함수 포인터 또한 결국 포인터이기에 변수뿐만 아니라 함수 인자로도 사용할 수 있죠우선 생김새를 배워봅시다.[함수 반환형*] (*변수명)(인자)ex) void* (*print)(char*);일반 변수처럼 똑같이 자료형이 있고 변수명이 있습니다.일반적으로 인자 형태는 변수명 뒤에 표시합니다. ※ 인자 부분을 비워둘 수도 있습니다. (비-프로토타입)이는 C언어에서만 적용되고 C++은 반드시 인자갯수, 타입을 명시해줘야합니다.2. 함수 포인터의 장단점장점 ..
반응형

개인적으로 C언어의 꽃이라고 생각되는 함수 포인터 개념을 이번 포스팅에서 다뤄보려고 합니다.

 

1. 함수 포인터란?


일반적으로 포인터란 자기 자신 이외의 메모리 주소를 담는 변수라고 표현됩니다.

이와 비슷하게 함수 포인터함수의 주소를 담는 변수라고 표현됩니다.

 

함수 포인터 또한 결국 포인터이기에 변수뿐만 아니라 함수 인자로도 사용할 수 있죠

우선 생김새를 배워봅시다.

[함수 반환형*]	(*변수명)(인자)
ex) void* (*print)(char*);

일반 변수처럼 똑같이 자료형이 있고 변수명이 있습니다.

일반적으로 인자 형태는 변수명 뒤에 표시합니다.

 

※ 인자 부분을 비워둘 수도 있습니다. (비-프로토타입)

이는 C언어에서만 적용되고 C++은 반드시 인자갯수, 타입을 명시해줘야합니다.

2. 함수 포인터의 장단점


장점

 

  • 런타임에 호출할 함수를 동적으로 결정할 수 있습니다. 즉, 코드가 실행 중에 어떤 함수를 호출할지 유연하게 선택할 수 있습니다.
  • 이벤트 기반, 비동기 프로그래밍에서 콜백 함수를 구현하는데 용이합니다.
  • 코드의 모듈화와 재사용성을 높이는 데 기여합니다. 특정 작업을 수행하는 코드를 여러 함수로 분리하여 모듈화할 수 있습니다.
  • 객체 지향 언어의 다형성을 흉내낼 수 있습니다.
  • 중복된 함수 호출 로직을 줄여 코드 크기를 절감할 수 있습니다.

단점

  • 함수 포인터 문법에 익숙하지 않은 사람, 프로젝트 참여자가 아닌 이상 코드가 복잡해질수록 가독성이 떨어집니다.
  • 인자 부분을 비워둘 수 있기에 타입 안전성이 떨어지고, 심하면 segment fault 오류를 야기할 수 있습니다.
  • 메모리를 직접 다루기에 보안 위험에 더 노출되게 됩니다.
  • C++의 다형성을 따라하기엔 역부족이며 코드 규모가 커질수록 복잡해집니다.

3. 함수 포인터 활용


예제 1) 콜백 함수 구현

#include <stdio.h>

// 콜백 함수
void onComplete() {
    printf("Operation completed!\n");
}

// 작업을 수행하고 콜백 함수를 호출하는 함수
void performTask(void (*callback)()) {
    // 작업 수행
    printf("Performing task...\n");

    // 작업이 완료된 후 콜백 함수 호출
    callback();
}

int main() {
    performTask(onComplete);  // onComplete를 콜백으로 전달
    return 0;
}

예제 2) 사용자 입력에 따라 동적으로 함수 호출

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

void Create() { printf("Create!\n"); }
void Read() { printf("Read!\n"); }
void Update() { printf("Update!\n"); }
void Delete() { printf("Delete!\n"); }
void Exit() { exit(0); }

int numOfCmd = 5;
char** cmdHandler;
void (*cmd[6])();
typedef enum {
    CREATE,
    READ,
    UPDATE,
    DELETE,
    EXIT,
    NONE
} CmdType;

void Init() {
    cmdHandler = (char**)malloc(sizeof(char*) * numOfCmd);
    cmdHandler[0] = _strdup("Create");
    cmdHandler[1] = _strdup("Read");
    cmdHandler[2] = _strdup("Update");
    cmdHandler[3] = _strdup("Delete");
    cmdHandler[4] = _strdup("Exit");

    cmd[0] = &Create;
    cmd[1] = &Read;
    cmd[2] = &Update;
    cmd[3] = &Delete;
    cmd[4] = &Exit;
}

int main() {
    Init();
    while (1) {
        char input[10];
        scanf_s("%s", input, 10); // 사용자 입력

        CmdType type = NONE;
        for (int i = 0; i < numOfCmd; i++) {
            if (strcmp(input, cmdHandler[i]) == 0) // 함수명 일치시 명령 타입 변경
                type = (CmdType)i;
        }
        if (type == NONE)
            printf("Error : Command Syntax\n"); // 일치하는 함수명이 아닌 경우 에러 처리
        else
            cmd[type](); // 일치하는 함수명 자동 호출
    }

    return 0;
}

예제3) 큐에 함수 포인터를 담아 호출 시점 분리(커맨드 패턴)

만약 멀티 스레드 환경이라면 push 부분과 execute 부분에 임계 구역 정해주면 됩니다.

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

#define QUEUE_MAX_SIZE 1024
typedef struct {
	void (*execute)(void*);
} CMD;
typedef struct {
	CMD* cmd;
} Node;
typedef struct q {
	int cur;
	int last;
	Node nodes[QUEUE_MAX_SIZE];
	int (*execute)(struct q*);
	void (*flush)(struct q*);
	int (*push)(struct q*, CMD*);
} Queue;

int Push(struct q* queue, CMD* cmd) {
	if (queue->last >= QUEUE_MAX_SIZE) // 더 이상 넣을 공간이 없을 때
		return -1;
	queue->nodes[queue->last++].cmd = cmd;
	return 0;
}

int Execute(struct q* queue) {
	if (queue->cur >= QUEUE_MAX_SIZE || queue->cur >= queue->last) // 큐가 비어있는 경우
		return -1;
	CMD* cmd = queue->nodes[queue->cur++].cmd;
	cmd->execute(cmd);
	free(cmd);
	return 0;
}

void Flush(struct q* queue) {
	while (queue->execute(queue) == 0); // 큐가 빌때까지 함수 실행 후 입출력 커서 초기화

	queue->cur = 0;
	queue->last = 0;
}

void QueueInit(struct q* queue) {
	queue->cur = 0;
	queue->last = 0;
	queue->push = &Push;
	queue->execute = &Execute;
	queue->flush = &Flush;
}

// 임시 상태 enum
typedef enum {
	IDLE,
	JUMP,
	WALK,
	RUN,
	ATTACK,
	NONE
} StateType;

typedef struct {
	CMD base; // 반드시 멤버 변수 0번째에 넣어주어야함
	int a;
	int b;
} CMD1;

typedef struct {
	CMD base;
	StateType state;
} CMD2;

void SumAndPrint(void* _cmd) {
	CMD1* cmd = (CMD1*)_cmd;

	int a = cmd->a;
	int b = cmd->b;
	printf("SumAndPrint : %d + %d = %d\n", a, b, a + b);
}

StateType type = NONE;
void ChangeState(void* _cmd) {
	CMD2* cmd = (CMD2*)_cmd;

	printf("ChangeState before : %d\n", type);
	type = cmd->state;
	printf("ChangeState After : %d\n", type);
}

int main() {
	Queue queue;
	QueueInit(&queue);

	{
		CMD1* cmd = (CMD1*)malloc(sizeof(CMD1));
		cmd->base.execute = &SumAndPrint; // 구조체의 0번째 주소에 함수를 넣기에 자료형이 변환되어도 함수 위치는 변하지 않음
		cmd->a = 5;
		cmd->b = 35;
		queue.push(&queue, cmd);
	}
	// 처리 중 .
	{
		CMD2* cmd = (CMD2*)malloc(sizeof(CMD2));
		cmd->base.execute = &ChangeState;
		cmd->state = RUN;
		queue.push(&queue, cmd);
	}
	// 처리 중 ..
	{
		CMD1* cmd = (CMD1*)malloc(sizeof(CMD1));
		cmd->base.execute = &SumAndPrint;
		cmd->a = -10;
		cmd->b = 2;
		queue.push(&queue, cmd);
	}
	// 처리 중 ...
	{
		queue.execute(&queue);
	}
	// 처리 중 ...
	{
		queue.flush(&queue);
	}
	return 0;
}

 

참고 자료


https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Declaring-Function-Pointers.html

 

Declaring Function Pointers (GNU C Language Manual)

22.5.1 Declaring Function Pointers The declaration of a function pointer variable (or structure field) looks almost like a function declaration, except it has an additional ‘*’ just before the variable name. Proper nesting requires a pair of parenthese

www.gnu.org

 

반응형

[C언어] 비트 연산자를 활용하여 계산기 만들기

※사칙 연산(+, -, *, /)만 다룹니다.논리회로는 귀찮아서 따로 그리지 않았습니다. 1. 반가산기와 전가산기컴퓨터는 전가산기를 통해 덧셈을 수행합니다.그 과정에서 반가산기를 사용하기에 반가산기를 포함하여 설명드립니다. 이진수 덧셈과 십진수 덧셈은 다를게 없습니다. 10진수 두 수 7과 4가 있다고 칩시다.이 두 수의 이진수 덧셈과 십진수 덧셈과정을 봅시다. 각 수를 A와 B라고 부르겠습니다.10진수인 경우A, B 각각 일의 자리부터 더한다.A의 현재 자릿수에 1을 B의 현재 자리수만큼 덧셈을 반복한다.더하는 도중 현재 자릿수가 9를 초과할 시 현재 자릿수를 0으로 만들고 다음 자릿수를 1올림한다. (올림 발생)올림 발생 후 나머지를 더한다.이 네가지대로 더한다면 A가 7이고 B가 4니까7에 1을 4..
반응형

※사칙 연산(+, -, *, /)만 다룹니다.

논리회로는 귀찮아서 따로 그리지 않았습니다.

 

1. 반가산기와 전가산기


컴퓨터는 전가산기를 통해 덧셈을 수행합니다.

그 과정에서 반가산기를 사용하기에 반가산기를 포함하여 설명드립니다.

 

이진수 덧셈과 십진수 덧셈은 다를게 없습니다.

 

10진수 두 수 7과 4가 있다고 칩시다.

이 두 수의 이진수 덧셈과 십진수 덧셈과정을 봅시다.

 

각 수를 A와 B라고 부르겠습니다.

10진수인 경우

  1. A, B 각각 일의 자리부터 더한다.
  2. A의 현재 자릿수에 1을 B의 현재 자리수만큼 덧셈을 반복한다.
  3. 더하는 도중 현재 자릿수가 9를 초과할 시 현재 자릿수를 0으로 만들고 다음 자릿수를 1올림한다. (올림 발생)
  4. 올림 발생 후 나머지를 더한다.

이 네가지대로 더한다면 A가 7이고 B가 4니까

7에 1을 4번 더하는거니까

3번에서 나온것처럼 10이 되고

4번을 수행하면 11이 됩니다.

 

만약 A가 15여서 한쪽만 자릿수가 더 높아서 B의 십의 자리가 없다면?

A의 십의 자리에 B의 십의 자리를 0만큼 더하면 됩니다. 

 

10진수에서 했던것 처럼 현재 자릿수 덧셈 공식을 똑같이 적용해봅시다.

2진수인 경우 (0111, 0100)

  1. A^0 와 B^0을 더한다(1 + 0) → 1
  2. A^1 와 B^1을 더한다(1 + 0) → 1
  3. A^2 와 B^2을 더한다(1 + 1) → 0 (올림 발생)
  4. A^3 와 B^3을 더한다(0 + 0 + 이전 올림) → 1
  5. 결과 1011 → 10진수 11

 

이 과정을 좀더 깊게 살펴봅시다.

7 4 올림
1 0 1 0
1 0 1 0
1 1 0 1
0 0 0 0

 

표를 보면 합이 0011, 올림이 0100이 됩니다.

 

은 어떤 비트연산을 써야할까요?

XOR를 사용하면 될것 같군요. 따라서 식은 A ^ B가 되겠습니다.

 

올림은 어떤 비트연산을 써야할까요?

AND를 사용하면 될것 같군요. 따라서 식은 A & B가 되겠습니다.

 

그럼 10진수도 똑같이 해볼까요?

347과 921이 있다고 칩시다.

347 921 올림
7 1 8 0
4 2 6 0
3 9 2 1
0 0 0 0

여기서 똑같이 올림이 발생했으니 다음 자릿수로 올림을 적용하면?

1268 이라는 결과값이 나오게 됩니다!

2진수와 덧셈과정이 왜 똑같다는지 아시겠죠??

 

자 그럼 방금 보셨던 내용이 반가산기인데요.

 

반가산기(半加算器, half adder)는 이진수의 한자리수를 연산하고, 자리올림수는 자리올림수 출력(carry out)에 따라 출력한다. ANDORNOT의 세 가지 종류의 논리회로만으로 구성할 수 있다.

- 위키백과 -

 

왜 반가산기(Hallf Adder)라고 불릴까요??

이유는 올림만 있지 그 올림을 실제로 적용시키지는 않기 때문인데요.

 

이제 올림을 실제로 적용시키는 전가산기의 과정을 봅시다.

 

전가산기 과정

  1. A와 B를 반가산기로 더한다.
  2. 반가산기로부터 나온 합(S)과 올림(C)을 반가산기로 더한다.
  3. 올림이 없을때까지 1-2를 반복한다.

자 이 과정을 표로 표현해봅시다.

7 4 이전 올림(Cin) 합(S) 올림(Cout)
1 0 0 1 0
1 0 0 1 0
1 1 0 0 1
0 0 1 1 0

첫 행부터 봐봅시다.

첫 번째 행 1 0 0 이기에 합이 1 올림 0

두 번째 행 1 0 0 이기에 합이 1 올림 0

세 번째 행 1 1 0 이기에 합이 0 올림 1

네 번째 행 0 0 1 이기에 합이 1 올림 0

 

최종 합 1011이 나오게 되는데

맨 처음 이전 올림은 당연히 없으니까 0

네 번째 행인 2^3 번째는 이전 올림이 있었기에 1이 되었죠

 

전가산기 과정 2번을 보면 합과 올림을 반가산기로 더한다는게

이전 올림(Cin)과 반가산기 합의 공식 A ^ B를 합하라는 것입니다.

 

여기서의 합의 공식은 A ^ B ^ Cin이 되겠습니다.

 

그렇다면 올림은 어떻게 될까요?

A B 이전 올림(Cin) 합(S) 올림(Cout)
0 0 0 0 0
1 0 0 1 0
0 1 0 1 0
0 0 1 1 0
1 1 0 0 1
1 0 1 0 1
0 1 1 0 1
1 1 1 1 1

 

전가산기의 진리표입니다.

여기서의 이전 올림은 표의 현재 올림과 상관없습니다.

 

올림 공식을 어떻게 짜면 좋을까요?

처음 반가산기에서의 올림 공식은 A & B이었습니다.

유심히 살펴보면 A, B, Cin 이 셋중 두개 이상 1인 경우 올림이 발생합니다.

식으로 유도해보면

Cout = (A & B) | (A & C) | (B & C)

이렇게 식을 짤 수 있습니다.

 

따라서 합과 올림의 식은 다음과 같습니다.

S = A ^ B ^ Cin

Cout = A & B | A & C | B & C

 

2. 덧셈 구현


int Add(int a, int b) {
    while (b != 0) {
        int c = a & b;
        a = a ^ b;
        b = c << 1;
    }
    return a;
}

c를 올림으로 사용하고

a를 합으로 사용하고

b를 마지막에 이전 올림을 적용 시켜줍니다.

 

이 과정을 반복하면 일반 + 연산과 동일한 기능을 하게되는데요.

설명드렸던 전가산기 과정을 보시면

  1. A, B를 반가산기로 더한다.
  2. 나온 합과 이전 올림을 더한다.
  3. 올림이 없을 때까지 반복한다.

int c = a & b가 올림

a = a ^ b 가 합

b = c << 1이 올림 적용

 

흐음.. Cin이 어디에 있는거지?? 라는 생각이 들면

while 2번째 부터 생각해 보세요

a는 이전 합을 구했고

b는 이전 올림을 적용한 상태입니다.

 

그래서 두 번째 반복부터 S = (a(A ^ B) ^ b(Cin)) 형태로써 완벽하게 합을 구할 수 있게 되는것이죠

 

이 과정을 b가 0이 아닐때 까지 == 올림이 없을 때까지 반복하면 덧셈 구현 끝입니다!

 

3. 뺄셈 구현


int Subtract(int a, int b) {
	return Add(a, -b);
}

뺄셈은 간단하죠 b를 음수로 만든 뒤 더하면 끝입니다.

 

물론 비트연산을 사용해 다르게 구현할 수 있습니다.

int Subtract(int a, int b) {
	return Add(a, ~b + 1);
}

다르게 구현하면 이 방식으로 구현할 수 있는데요

~ 기호는 not으로써 모든 0비트를 1로, 모든 1비트를 0으로 바꿉니다.

따라서 양수인 수는 음수, 음수인 수는 양수가 되는데요.

 

그렇다면 왜 1을 더하는가?

int 자료형의 범위를 보면 -2,147,483,648 ~ 2,147,483,647

최소값과 최대값이 절댓값 적용했을 때 1차이가 납니다.

 

그 이유는 0이 양수쪽에 포함되어있기 때문입니다.

따라서 not을 적용했을 때 1의 오차가 포함되어있기 때문에 1을 더해주면

~b + 1 == -b 식과 같기 때문에 a + ~b + 1을 해주면 뺄셈 구현 끝입니다.

 

4. 곱셈 구현


int Multiply(int a, int b) {
	bool negativeResult = false;
	if ((a < 0 && b > 0) || (a > 0 && b < 0))
		negativeResult = true;

	a = abs(a);
	b = abs(b);

	int t = 0;
	while (b != 0) {
		if (b & 1)
			t = Add(t, a);
		a <<= 1;
		if ((b >> 1) == b) // b가 INT_MIN으로 들어온 경우 >> 반복해도 항상 INT_MIN이기에 예외처리
			break;
		b >>= 1;
	}

	if (negativeResult)
		t = ~t + 1;
	a = t;
    	return a;
}

음수인경우 예외처리 같은 짜잘한 부분은 제치고 메인인 while문을 봐주시기 바랍니다.

 

2진수 곱셈 과정 또한 10진수 곱셈 과정하고 같습니다.

15와 27의 곱셈 과정을 풀어 보겠습니다.

    15
x   27
--------
    15
    15
    15
    15
    15
    15
    15
--------
   105
   15
   15
--------
   405

곱셈은 다들 아시다시피

A를 B번 더하는것 입니다.

 

따라서 15 * 27은 15를 27번 더한것이죠

곱셈 과정을 보시면 처음에 15를 7번 더하고

십의 자리수인 2번 만큼 또 15를 더해주는데 이때 십의 자리이기 때문에

15는 한칸 앞으로 땡기고 20은 뒤로 땡겨서 2로 만든뒤 150을 2번 더한다면

150 + 150 이 되게 됩니다.

 

단순하게 표현하면 아래와 같습니다.

15 * 7 = 105

150 * 2 = 300

105 + 300 = 405

 

이 과정을 정리해보면

 

곱셈 과정

  1. A를 B번 더하는것이 곱셈
  2. B의 일의 자리수만큼 A를 더한다.
  3. 더한 뒤 B의 B가 0이 아니라면 A를 10 곱하고 B를 10 나눈다.
  4. 2-3을 반복한다.

똑같이 15와 27을 2진수로 위 곱셈과정을 적용하여 곱해보겠습니다.

(각각 1111, 11011)

     1111
x   11011
----------
     1111
    1111
----------
   101101
  1111
----------
 10100101
 1111
----------
110010101 // 405

곱셈 과정을 보시면 10진수를 기준으로 말씀 드렸기에

10을 곱하고 나누는 부분을 2를 곱하고 나누는것으로 재해석 하면 됩니다.

 

보시면

a * b^0 == 1111

a * b^1 == 11110

( a * b^1 ) + ( a * b^0 ) = 101101

으로 되었는데 a * b^1 부분에서 11110이 된것을 곱셈과정 똑같이 적용해 보세요.

 

  1. (a * 2) * (b^1 / 2)
  2. (11110) * (1)
  3. 11110

와우! 똑같이 11110이 나왔네요

이 값을 전 곱셈 과정 결과인 1111과 더하고

101101이 되고 b^2, b^3 ... 또한 같은 방식으로 곱셈 연산을 하면 됩니다.

 

다시 본문인 while 반복문 코드로 돌아가보면

b & 1로 현재 곱해야 하는지를 체크한뒤

a를 왼쪽, b를 오른쪽 쉬프트 연산을 해줍니다.

b가 0이 아닐 때까지 반복해주면 곱셈연산 끝입니다.

 

두 수를 양수화 시키는 이유는 단순히 계산하기 편하니까 입니다.

큰 이유 없습니다.

 

5. 나눗셈 구현


10진수 나눗셈 과정과 2진수 나눗셈 과정은 완전히 같습니다.

10진수 나눗셈 과정

  1. 제수가 피제수 이하이면서 가장 근접한 값을 가질 때까지 10을 곱한다.
  2. 제수에 10을 곱했던 반복횟수만큼 1을 10씩 곱한다.
  3. 피제수를 곱한 제수만큼 반복해서 뺀다.
  4. 1을 10씩 곱한 수 * 뺀 횟수를 몫에 더한다
  5. 제수가 피제수보다 작을 때까지 1-4을 반복한다.

2진수 나눗셈이라면 여기서 10을 2로 바꾸면 됩니다.

그 식을 적용해서 한번 풀어봅시다.

출처 : 내꺼임

해당 사진에서 쓰인 나눗셈 식은 long division 이라고 해서 저희가 학교에서 흔히 배웠던 나눗셈 방식 중 하나입니다.

보시면 768 / 23 을 하는데 10진수와 2진수의 나눗셈 과정이 똑같죠?

 

2진수 쪽 나눗셈 보시면 10111이 768의 2진수보다 작으면서 최대한 근접한 값을 가질 때 까지 2를 곱해 왼쪽으로 이동시킨뒤 빼주는걸 반복하고 제수가 피제수보다 크니 종료되는것이죠.

위쪽에서 설명드린 나눗셈 과정을 보시고 오면 이해가 잘 되실겁니다.

 

int Divide(int* a, int b) { // a를 나머지로 사용하기에 *a 로 받음
	if (b == 0)
	{
		fprintf(stderr, "Error : Division by zero"); // 0으로 나눌 시 예외처리
		exit(1);
	}

	if (*a == INT_MIN && b == INT_MIN) { // 둘 다 INT_MIN 인경우 예외처리
		*a = 0;
		return 1;
	}

	if (b == INT_MIN) // 나누는수가 INT_MIN이고 나눌 수가 INT_MIN이 아니면 몫은 0, 나머지는 a 그대로
		return 0;

	if (*a == INT_MIN) {
		if (b == -1) { // INT_MIN / -1 오버플로우 예외 처리
			fprintf(stderr, "Error : Integer Overflow");
			exit(1);
		}

		int t = HALF_INT_MIN; // INT_MIN / 2

		if (abs(b) > abs(t)) { // b의 절댓값이 INT_MIN / 2 (2^30)절댓값보다 큰 경우 
			*a = Add(*a, abs(b));
			if (b < 0)
				return 1;
			return -1;
		}

		int n = Divide(&t, b);
		n = Multiply(n, 2);
		t = Multiply(t, 2); // (INT_MIN / b) == (((INT_MIN / 2) / b) * 2)
		if (abs(t) >= abs(b)) { // 몫과 나머지 정리
			n = Add(n, 1);
			t = -(abs(t) - abs(b));
		}
		*a = t;
		return n;
	}

	bool negativeResult = false;
	if ((*a < 0 && b > 0) || (*a > 0 && b < 0))
		negativeResult = true;
	bool negativeA = *a < 0;

	*a = abs(*a);
	b = abs(b);

	int ret = 0;
	while (*a >= b) {
		int t1 = b;
		int t2 = 1;
		while (*a >= (t1 << 1) && (t1 << 1) > 0) {
			t1 <<= 1;
			t2 <<= 1;
		}
		ret = Add(ret, t2);
		*a = Subtract(*a, t1);
	}
	if (negativeResult)
		ret = -ret;
	if (negativeA)
		*a = -*a;
	return ret;
}

짜잘한 예외처리는 제치고 중요한 while을 보시면 

반복문에 들어오기전 절댓값으로 바꿔준뒤 제수가 피제수보다 작을 때까지 반복합니다.

 

이후 제수의 값과 1이란 값을 변수2개에 넣어준 뒤

제수 이하이면서 최대한 근접한 값을 가질때까지 두 변수를 왼쪽 시프트를 해줍니다.

(t1 << 1) > 0은 부호비트 오버플로우 방지 조건

 

이후 시프트된 두 변수를 각각 결과값(몫)에 더하고 피제수(나머지)를 빼주는걸 반복한뒤

각각 조건에 맞게 음수부호로 바꾼 뒤 반환하면 됩니다.

 

참고자료

https://moduweb.tistory.com/7

https://www.youtube.com/watch?v=VKemv9u40gc&ab_channel=NesoAcademy

https://www.youtube.com/watch?v=xHWKYFhhtJQ&t=100s&ab_channel=KhanAcademy

 

반응형

[C] strdup, strjoin, split 구현

stdup의 경우 기존에 C에 있던 함수이기 때문에 많은 분들이 익숙하시겠지만 join과 split의 경우 C언어에 없는 함수이기 때문에 많이 생소하실 겁니다. 다른 언어에서 주로 사용되는 join과 split의 경우 문자열을 이어주고, 특정 문자 기준으로 나누어 주고 해주는 함수이죠 좀 더 자세히 알고 싶으시면 파이썬 join과 split에 대해서 검색해 보시면 됩니다. Strdup#include const char *(const char *s1);함수 내에서 힙메모리에 s1 문자열 크기의 공간을 할당 후 문자열을 복사시키고 반환해주는 함수입니다. #include #include #include const char *my_strdup(const char *s1) { char *ret; int len =..
반응형

stdup의 경우 기존에 C에 있던 함수이기 때문에 많은 분들이 익숙하시겠지만
 
join과 split의 경우 C언어에 없는 함수이기 때문에 많이 생소하실 겁니다.
 
다른 언어에서 주로 사용되는 join과 split의 경우 문자열을 이어주고, 특정 문자 기준으로 나누어 주고 해주는 함수이죠
좀 더 자세히 알고 싶으시면 파이썬 join과 split에 대해서 검색해 보시면 됩니다.
 

Strdup


#include <stdlib.h> 	const char *(const char *s1);

함수 내에서 힙메모리에 s1 문자열 크기의 공간을 할당 후 문자열을 복사시키고 반환해주는 함수입니다.
 

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

const char *my_strdup(const char *s1) {
    char *ret;
    int len = strlen(s1); // s1 string length

    ret = (char *)malloc(len + 1); // allocate memory
    if (ret == NULL) { return NULL; } // null guard

    for (int i = 0; i < len; i++) { ret[i] = s1[i]; }
    ret[len] = 0;

    return (const char*)ret;
}

int main(int ac, char *av[]) {
    const char *str = my_strdup(av[1]);
    if (str == NULL) { return 0; }

    printf("%s\n", str);
    free((void *)str);

    return 0;
}

strlen으로 길이를 받고 그 길이만큼 공간을 할당 후 for문으로 길미만큼 복사를 반복시켜주고 반환하면 끝입니다.
 
 

Strjoin


const char *strjoin(const char *s1, const char *s2);

 
두 문자열을 이어붙여 주는 strjoin은 C언어에서 지원해 주지 않는 함수이기에 man으로 검색해도 나오지 않습니다.
저희가 만들 strjoin함수의 형태는 아래와 같습니다.
 

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

const char *strjoin(const char *s1, const char *s2) {
    char *ret;

    int len1 = strlen(s1); // s1 length
    int len2 = strlen(s2); // s2 length
    ret = (char *)malloc(len1 + len2 + 1); // allocate memory
    if (ret == NULL) { return NULL; } // null guard

    for (int i = 0; i < len1; i++) { ret[i] = s1[i]; }
    for (int i = 0; i < len2; i++) { ret[i + len1] = s2[i]; }
    ret[len1 + len2] = 0;

    return ret;
}

int main(int ac, char *av[]) {
    const char *str = strjoin(av[1], av[2]);
    if (str == NULL) { return 0; }

    printf("%s\n", str);
    free((void *)str);

    return 0;
}

strdup 구현과 비슷합니다
두 문자열 총 크기만큼 할당하고 s1, s2를 차례대로 복사시켜주면 간단하게 구현할 수 있습니다.
 

Split


split 함수도 strjoin과 마찬가지로 C언어에서 지원해 주지 않는 함수입니다.
구현 방법은 아래와 같습니다.
 

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

// free allocated memory
const char **free_all(char **s) {
    for (int i = 0; s[i]; i++) { free(s[i]); }
    free(s);

    return NULL;
}

int count_units(const char *s1, int c) {
    int ret = 0;
    int i = 0;
    
    while (s1[i]) {
        if (s1[i] == c) {
            while (s1[i] && s1[i] == c) { i++; }
        } else {
            ret++; // count unit
            while (s1[i] && s1[i] != c) { i++; }
        }
    }
    return ret;
}

char *get_unit(const char *s1, int c, int *i) {
    char    *ret;
    int     pos, j = 0;

    while (s1[*i] && s1[*i] == c) { *i += 1; }
    pos = *i; // flag start unit pos
    while (s1[*i] && s1[*i] != c) { *i += 1; }

    ret = (char *)malloc(*i - pos + 1);
    if (ret == NULL) { return NULL; }

    while (pos != *i) { ret[j++] = s1[pos++]; }
    ret[j] = 0;
    return ret;
}

const char **split(const char *s1, int c) {
    char **ret;
    int idx = 0;

    int cnt = count_units(s1, c);
    ret = (char **)malloc(sizeof(char *) * (cnt + 1));
    if (ret == NULL) { return NULL; }
    ret[cnt] = NULL;

    for (int i = 0; i < cnt; i++) {
        ret[i] = get_unit(s1, c, &idx);
        if (ret[i] == NULL) { return free_all(ret); }
    }

    return (const char **)ret;
}

int main(int ac, char *av[]) {
    const char **str = split(av[1], av[2][0]);
    if (str == NULL) { return 0; }

    for (int i = 0; str[i]; i++) {
        printf("%s\n", str[i]);
    }

    free_all((char **)str);
    return 0;
}

맨 처음 count units 함수로 총 몇개로 문자열이 나뉘는지 파악해준뒤
get unit 함수로 파악한 개수만큼 반복해서 문자열을 파싱해 주면 됩니다.
 
만약 문자 하나가 아닌 문자열을 기준으로 split하고 싶다면
count units 부분과 get unit 함수에서 strstr 함수를 적절히 사용하면 됩니다.

반응형

[C언어] 백준 13460 구슬 탈출 2

문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으..
반응형

문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

예제 입력 1 

5 5
#####
#..B#
#.#.#
#RO.#
#####

예제 출력 1 

1

예제 입력 2 

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

예제 출력 2 

5

예제 입력 3 

7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######

예제 출력 3 

5

예제 입력 4 

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########

예제 출력 4 

-1

예제 입력 5 

3 7
#######
#R.O.B#
#######

예제 출력 5 

1

예제 입력 6 

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
##########

예제 출력 6 

7

예제 입력 7 

3 10
##########
#.O....RB#
##########

예제 출력 7 

-1

https://www.acmicpc.net/problem/13460

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

반응형

 

문제 풀기 전 로직 생각하기


상하좌우로 맵을 기울여서 구슬을 움직이는데 이때 구슬은 기울인 방향으로 더 이상 움직일 수 없을때까지 움직입니다.

 

빨강과 파랑이 같은 선상에 있으면 나중에 움직인 구슬은 먼저 움직인 구슬 - 1까지 움직여야 합니다.

이 부분은 움직이기 전 y, x 좌표를 미리 변수에 담아놓고 나중에 움직인 쪽을 -1 처리 하면 될것 같습니다.

 

파랑 구슬과 빨강 구슬이 동시에 구멍에 빠지는 경우 -1 출력을 해야하니 이 부분은

큐의 다음 인덱스가 비어있지 않은 경우 continue 하면 될겁니다.

 

한번 방문했던 곳이라도 재방문 할 수 있어야 하는데 이 점을 생각해보면 무한 루프가 염려되는데요

이 경우 두 구슬다 어느 방향으로 기울였을 때 의미가 없는 경우는 큐에 삽입하지 않도록 해야할것 같습니다.

그리고 이전에 기울였던 방향과 기울였던 반대 방향 또한 삽입하지 않도록 하면 더 좋을것 같습니다.

 

기울인 횟수가 11 이상이면 -1로 처리를 해주면 충분할 것 같구요.

이정도만 생각하고 만들면 충분할것 같습니다.

 

전체 코드


#include <stdio.h>

int h, w, red_x, red_y, red_finish = 0, blue_y, blue_x, blue_finish = 0, exit_y, exit_x, last = 0;
char	map[11][11];
int	dx[4] = {1, -1, 0, 0};
int	dy[4] = {0, 0, 1, -1};

typedef struct
{
	int	red_y;
	int	red_x;
	int	blue_y;
	int	blue_x;
	int	direction;
	int	step;
}	queue;

queue	q[2000];

int	promising(int ry, int rx, int by, int bx, int dir)
{
	// dir 방향으로 구슬을 기울여도 같은 결과인 경우 의미가 없으므로 pass
	if (map[ry + dy[dir]][rx + dx[dir]] == '#' && by + dy[dir] == ry && bx + dx[dir] == rx)
		return (0);
	if (map[by + dy[dir]][bx + dx[dir]] == '#' && ry + dy[dir] == by && rx + dx[dir] == bx)
		return (0);
	if (map[ry + dy[dir]][rx + dx[dir]] == '#' && map[by + dy[dir]][bx + dx[dir]] == '#')
		return (0);
	return (1);
}

void	init()
{
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (map[i][j] == 'B')
			{
				blue_y = i;
				blue_x = j;
			}
		}
	}
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (map[i][j] == 'R')
			{
				for (int k = 0; k < 4; k++)
				{
					if (!promising(i, j, blue_y, blue_x, k))
						continue ;
					q[last].red_y = i;
					q[last].red_x = j;
					q[last].blue_y = blue_y;
					q[last].blue_x = blue_x;
					q[last].step = 0;
					q[last++].direction = k;
				}
			}
		}
	}
}

void	priority(int *ry, int *rx, int *by, int *bx, int dir)
{
	// 나중에 움직인 구슬 -1 만큼 움직이게 하기
	if (*ry == *by && *rx == *bx)
	{
		if (dir == 0)
		{
			if (red_x > blue_x)
				*bx -= 1;
			else
				*rx -= 1;
		}
		else if (dir == 1)
		{
			if (red_x < blue_x)
				*bx += 1;
			else
				*rx += 1;
		}
		else if (dir == 2)
		{
			if (red_y > blue_y)
				*by -= 1;
			else
				*ry -= 1;
		}
		else if (dir == 3)
		{
			if (red_y < blue_y)
				*by += 1;
			else
				*ry += 1;
		}
	}
}

int	bfs()
{
	int	ry, rx, by, bx, ny, nx, dir, step, cur = -1;

	while (++cur < last)
	{
		red_x = q[cur].red_x;
		red_y = q[cur].red_y;
		blue_x = q[cur].blue_x;
		blue_y = q[cur].blue_y;
		dir = q[cur].direction;
		step = q[cur].step;
        // 기울인 횟수가 11 이상인 경우
		if (step >= 10)
			break ;
		ny = red_y + dy[dir];
		nx = red_x + dx[dir];
		while (ny > 0 && ny < h - 1 && nx > 0 && nx < w - 1 && map[ny][nx] != '#')
		{
			if (map[ny][nx] == 'O')
				red_finish = 1;
			ny += dy[dir];
			nx += dx[dir];
		}
		ry = ny - dy[dir];
		rx = nx - dx[dir];
		ny = blue_y + dy[dir];
		nx = blue_x + dx[dir];
		while (ny > 0 && ny < h - 1 && nx > 0 && nx < w - 1 && map[ny][nx] != '#')
		{
			if (map[ny][nx] == 'O')
				blue_finish = 1;
			ny += dy[dir];
			nx += dx[dir];
		}
		by = ny - dy[dir];
		bx = nx - dx[dir];
		priority(&ry, &rx, &by, &bx, dir);
		for (int i = 0; i < 4; i++)
		{
        	// 파랑 구슬이 빠진 경우
			if (blue_finish)
				continue ;
            // 이전 방향 또는 이전 방향의 반대 방향은 불필요한 삽입 pass
			if (i == dir || (!(dir % 2) && i == dir + 1) || ((dir % 2) && i == dir - 1))
				continue ;
            // 불필요한 삽입 pass
			if (!promising(ry, rx, by, bx, i))
				continue ;
			q[last].red_y = ry;
			q[last].red_x = rx;
			q[last].blue_y = by;
			q[last].blue_x = bx;
			q[last].step = step + 1;
			q[last++].direction = i;
		}
        // 파랑 구슬이 빠진 경우 큐가 비어있으면 다음 반복문에서 break
        // 비어있지 않다면 초기화
		if (blue_finish)
		{
			red_finish = 0;
			blue_finish = 0;
		}
        // 빨강 구슬만 빠진 경우 기울인 횟수 반환
		else if (red_finish)
			return (step + 1);
	}
	return (-1);
}

int	main()
{
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
		scanf("\n%s", map[i]);
	init();
	printf("%d\n", bfs());
	return (0);
}

 

문제 해설


맵을 입력 받은 뒤 init 함수로 들어가 구슬들의 위치를 탐색하고 큐에 삽입해줍니다.

 

큐에 삽입할 때마다 promising 함수를 이용해 불필요한 삽입은 하지 않게 구현했습니다.

promising함수에서 문제 풀기 전 로직 생각하기 부분에서 나온 두 구슬이 어떤 방향으로 움직였을 때

의미 없는 경우를 따로 삽입하지 않게 했습니다.

 

이후 bfs 함수로 들어가서 기울이기 전 구슬들의 위치를 변수에 담아주고

구슬들을 direction에 맞는 방향으로 움직여 줍니다.

 

빨강 구슬을 먼저 기울인 뒤 파랑 구슬을 기울이고

for 문으로 상하좌우를 유망성 체크해서 큐에 삽입해 줍니다.

 

이때 조건문은 파랑 구슬이 구멍에 빠졌거나 이전 방향 또는 이전 방향의 반대 방향과

불필요한 방향은 큐에 삽입하지 않도록 했습니다.

 

그리고 파랑 구슬이 구멍에 빠진 경우 큐가 비어있지 않았을 때

두 구슬이 빠지지 않았음을 다시 초기화 해주고

 

빨강 구슬만 빠진 경우 (기울인 횟수 + 1) 을 반환시켜 출력하는 방식으로 풀었습니다.

 

 

삼성 기출 문제이다 보니 푸는데 굉장히 오래걸렸었는데 풀고 나니 만족감이 밀려오네요 ㅋㅋㅋ

반응형

[C언어] 백준 10026 적록색약

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다...
반응형

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 

4 3

https://www.acmicpc.net/problem/10026

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

문제 풀기 전 로직 생각하기


R, G, B 로 구성된 문자열들이 입력으로 들어오고 각각의 알파벳 끼리 상하좌우로

연결되어 알파벳 뭉텅이들의 갯수를 구하는 문제입니다.

 

한 가지 추가된 점은 두 번째 출력 부분에선 R과 G는 서로 같은 색으로 구분되어 갯수를 좀더 다르게 구하는 것인데요.

 

이 부분은 그냥 dfs를 한번 더 돌리면 될것 같습니다.

 

dfs에서 맨 처음 함수에 들어왔던 문자와 상하좌우 문자를 비교하면 될것 같습니다. 

 

전체 코드


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

char	str[101][101];
int		n, r = 0, b = 0, g = 0, visited[101][101] = {};

void	dfs(int y, int x, char *set)
{	// strchr로 현 위치의 문자가 set에 포함 되는지 확인
	if (0 <= y && y < n && 0 <= x && x < n && !visited[y][x] && strchr(set, str[y][x]))
	{
		visited[y][x]++;
		dfs(y + 1, x, set);
		dfs(y - 1, x, set);
		dfs(y, x + 1, set);
		dfs(y, x - 1, set);
	}
}

int main()
{
	int	ret = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("\n%s", str[i]);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j])
			{
				if (str[i][j] == 'R' && ++r)
					dfs(i, j, "R");
				else if (str[i][j] == 'G' && ++g)
					dfs(i, j, "G");
				else if (str[i][j] == 'B' && ++b)
					dfs(i, j, "B");
			}
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			visited[i][j] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j] && ++ret)
			{
				if (str[i][j] == 'B')
					dfs(i, j, "B");
				else
					dfs(i, j, "RG");
			}
		}
	}
	printf("%d %d\n", r + g + b, ret);
	return (0);
}

 

문제 해설


dfs를 두번 수행하는 데요

첫 번째 dfs에서는 각각의 인덱스를 R, G, B로 구분 하면서 체크해 방문하지 않은 곳이 있다면 각각의 변수값을 카운트 해주면서 dfs를 돌려 줍니다.

 

두 번째 dfs에서는 B인 경우 그냥  dfs 돌려 주고 그게 아닌 경우 RG를 인자값으로 보내 체크해 줍니다.

 

현재 위치의 문자와 인자값으로 보낸 set을 strchr 함수를 이용해 체크해 주는 방식으로 풀었습니다. 

반응형

[C언어] 백준 1987 알파벳

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. 출력..
반응형

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1 

2 4
CAAB
ADCB

예제 출력 1 

3

예제 입력 2 

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2 

6

예제 입력 3 

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3 

10

https://www.acmicpc.net/problem/1987

 

1987번: 알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

www.acmicpc.net

 

문제 풀기 전 로직 생각하기


좌상단부터 시작해서 상하좌우를 살펴 한 번도 보지 못한 알파벳이 있는 경우 그 인덱스로 이동하고

이 과정을 최대한 길게해서 최대 거리를 구하는 문제입니다.

 

우선 ascii  값을 따로 받는 배열로 체크하면서 이동하면 될것 같습니다.

상하 좌우를 살폈을 때 전부 이전에 봤던 알파벳인 경우 전에 있던 곳으로 이동하면서

현재 있던 곳은 체크했던 배열에서 체크를 해제하면 되겠네요.

 

전체 코드


#include <stdio.h>

int h, w, result = 0;
char	str[21][21];

void	dfs(int y, int x, int ret, int vis[])
{
	if (0 <= y && y < h && 0 <= x && x < w && !vis[str[y][x]])
	{
		vis[str[y][x]]++;
		ret++;
        // 결과 값이 현재까지의 길이보다 더 작은 경우 초기화
		if (ret > result)
			result = ret;
		dfs(y + 1, x, ret, vis);
		dfs(y - 1, x, ret, vis);
		dfs(y, x + 1, ret, vis);
		dfs(y, x - 1, ret, vis);
        // 상하 좌우를 살폈는데 전부 봤었던 알파벳인 경우 이전 경로로 돌아가기 전 방문 체크 해제
		vis[str[y][x]]--;
	}
}

int main()
{
	int	temp[128] = {}, ret = 0;
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
		scanf("%s", str[i]);
	dfs(0, 0, 0, temp);
	printf("%d\n", result);
	return (0);
}

 

문제 해설


좌상단 부터 dfs를 시작해 본적이 없는 알파벳인 경우 체크하고 상하 좌우 깊이 우선 탐색해 줍니다.

깊이 우선 탐색을 하다가 상하좌우 전부 봤었던 알파벳이면 자연스럽게 방문 체크 해제 부분으로 내려와 해제를 해주고

이전 경로로 돌아가 다른 dfs를 반복해 줄겁니다.

 

이런 식으로 백트래킹을 구현했습니다.

 

코드는 생각보다 간결하게 구현되었지만 아쉬운 점은 프로그램 실행시간이 생각보다 많이 나왔다는 점이네요

반응형

[C언어] 백준 2146 다리 만들기

문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다. 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가..
반응형

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제 입력 1 

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1 

3

https://www.acmicpc.net/problem/2146

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

 

문제 풀기 전 로직 생각하기


섬끼리 잇는 다리를 짓는데 그 다리를 최소한의 거리로 지을 때의 거리를 구하는 문제입니다.

예제 1번을 보면 섬이 세 개 있고 결과값이 3으로 좌상단 섬과 아래에 있는

섬을 이을 때 거리가 3으로 써 결과값이 3이 출력된걸 볼 수 있습니다.

 

이 점을 생각해보면 섬마다 같은 섬이 아니라고 인식할 수 있게 인덱스를 부여해 주면 좋을 것 같습니다.

그리고 섬 갯수만큼 bfs를 수행해 현재 섬에서 다른 섬까지 도달 했을 때의 최소값을 구해주면 될것 같습니다.

 

출발 지점은 현재 위치가 섬이면서 상하좌우를 살펴 바다가 있으면 가장 외곽 쪽임을 알 수 있으니까

그 부분들을 출발 지점으로 삼으면 될것 같습니다.

 

도착 지점은 현재 위치가 바다면서 상하좌우를 살펴 다른 섬이 있으면 다리를 다 만들었음을 알 수 있으니까

현재 위치의 값을 저장시키면서 최소값을 찾으면 될것 같습니다.

 

전체 코드


#include <stdio.h>
#define MAX_SIZE 101 * 101 + 10
#define INF 2147483647
int	n, map[101][101], temp[101][101] = {}, result[101][101], k = 1;
int	dx[4] = {-1, 0, 1, 0};
int	dy[4] = {0, 1, 0, -1};

typedef struct
{
	int	y;
	int	x;
}	queue;

queue	q[MAX_SIZE];

void	dfs(int y, int x, int m)
{
	// 현재 위치가 섬인 경우 인덱스 번호 부여
	if (0 <= y && y < n && 0 <= x && x < n && map[y][x] && !temp[y][x])
	{
		temp[y][x] = m;
		dfs(y + 1, x, m);
		dfs(y - 1, x, m);
		dfs(y, x + 1, m);
		dfs(y, x - 1, m);
	}
}

void	insert(int N, int *last)
{
	int	f, nx, ny;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			f = 0;
			result[i][j] = -1;
			for (int l = 0; l < 4 && !f; l++)
			{
				nx = j + dx[l];
				ny = i + dy[l];
                // 현재 위치가 인덱스에 맞는 섬이면서 상하좌우중 하나라도 바다라면 출발 지점 지정
				if (0 <= nx && nx < n && 0 <= ny && ny < n && temp[i][j] == N && !map[ny][nx])
				{
					f = 1;
					q[*last].y = i;
					q[*last].x = j;
					*last += 1;
					result[i][j] = 0;
				}
			}
		}
	}
}

int	bfs(int N)
{
	int	x, y, nx, ny, cur = -1, last = 0, ret = INF;

	insert(N, &last);
	while (++cur < last)
	{
		x = q[cur].x;
		y = q[cur].y;
		for (int i = 0; i < 4; i++)
		{
			ny = y + dy[i];
			nx = x + dx[i];
			if (0 <= ny && ny < n && 0 <= nx && nx < n)
			{
            	// 다음 위치를 방문한 적이 없으면서 바다라면 
				if (result[ny][nx] == -1 && !map[ny][nx])
				{
					result[ny][nx] = result[y][x] + 1;
					q[last].x = nx;
					q[last++].y = ny;
				}
                // 현재 위치가 바다면서 다음 위치가 다른 섬이고 현 위치까지의 거리가 결과값보다 작다면 초기화
				if (!map[y][x]  && map[ny][nx] && \
						temp[ny][nx] != N && result[y][x] < ret)
					ret = result[y][x];
			}
		}
	}
	return (ret);
}

int main()
{
	int	ret = INF, tmp;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &map[i][j]);
    // 섬마다 인덱스 번호 부여하기
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (!temp[i][j] && map[i][j])
				dfs(i, j, k++);
	for (int i = 1; i < k; i++)
	{
		tmp = bfs(i);
		if (ret > tmp)
			ret = tmp;
	}
	printf("%d\n", ret);
	return (0);
}

 

문제 해설


문제 풀기 전 로직 생각하기 부분에서 나왔던 내용들을 준수하면서 구현해 봤습니다.

맵을 입력 받은 뒤 각각의 섬들을 temp 배열에서 dfs를 수행해 인덱스를 부여해 줍니다.

 

bfs를 수행하기 전 insert 함수로 출발 지점을 정해 줍니다.

출발 지점을 현 위치가 섬이면서 상하좌우중 하나라도 바다라면 큐에 삽입해 줍니다.

그 후 bfs로 다른 섬까지의 최단 경로를 큐가 빌 때 까지 구해 줍니다.

 

다른 섬까지 도착 했는지는 현 위치가 바다면서 상하좌우중 하나라도 다른 섬의 인덱스를 갖고 있으면 그 부분을 도착 지점으로 정해서

현재까지의 거리를 구해 최소값을 구해줍니다.

 

이 과정을 섬 갯수 만큼 반복을 하면 섬끼리의 최소 거리를 구할 수 있습니다.

반응형

[C언어] 백준 2206벽 부수고 이동하기

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 ..
반응형

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1 

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1 

15

예제 입력 2 

4 4
0111
1111
1111
1110

예제 출력 2 

-1

https://www.acmicpc.net/problem/2206

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

문제 풀기 전 로직 생각하기


맵의 좌상단에서 우하단까지의 최단 거리를 구하는 BFS 문제입니다.

조건이 하나 추가가 되었는데 벽을 하나 무시하고 최단 거리를 구하는 것인데요.

 

visited 배열을 이용해서 "이 경로는 내가 벽을 부수고(부수지 않고) 지나온 길이야" 라고 인식 시키면 될 것 같습니다.

그리고 이동할 때 몇가지를 기억하면서 이동시켜야 할것 같습니다.

  • 벽을 부수지 않고 이동했을 때 벽을 만난 경우 이동(이 때 벽을 부쉈다고 체크)
  • 벽을 부수지 않고 이동했을 때 벽이 아닌 곳을 만난 경우 이동
  • 벽을 부수고 벽이 아닌 곳을 만난 경우 이동
  • 벽을 부수고 벽인 곳을 만났을 때 무시

이 네 가지를 생각하면서 로직을 짜면 좀 더 쉽게 구현할 수 있을 것 같네요!

 

전체 코드


#include <stdio.h>
#define MAX_SIZE 1001 * 1001 + 10
int n, m, map[1001][1001], temp[1001][1001] = {}, visited[1001][1001][2] = {};
int	dx[4] = {-1, 0, 1, 0};
int	dy[4] = {0, 1, 0, -1};
typedef struct
{
	int	y;
	int	x;
	int	wall;
}	queue;

queue	q[MAX_SIZE];

void	bfs()
{
	int	x, y, nx, ny, wall, cur = -1, last = 0;

	q[last].x = 0;
	q[last].wall = 0;
	q[last++].y = 0;
	while (++cur < last && temp[n - 1][m - 1] == -1)
	{
		x = q[cur].x;
		y = q[cur].y;
		wall = q[cur].wall;
		for (int i = 0; i < 4; i++)
		{
			nx = x + dx[i];
			ny = y + dy[i];
			if (0 <= nx && nx < m && 0 <= ny && ny < n)
			{
            	// 벽을 부수지 않았는 데 벽을 만난 경우
				if (map[ny][nx] == 1 && wall == 0 && !visited[ny][nx][wall + 1])
				{
					temp[ny][nx] = temp[y][x] + 1;
					q[last].y = ny;
					q[last].x = nx;
					q[last++].wall = 1;
					visited[ny][nx][wall + 1]++;
				}
                // 벽이 아니면서 방문 한 적이 없는 경우 (wall이 0이든 1이든 상관 x)
				else if (map[ny][nx] == 0 && !visited[ny][nx][wall])
				{
					temp[ny][nx] = temp[y][x] + 1;
					q[last].y = ny;
					q[last].x = nx;
					q[last++].wall = wall;
					visited[ny][nx][wall]++;
				}
			}
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &map[i][j]);
			temp[i][j] = -1;
		}
	}
	temp[0][0] = 1;
	bfs();
	printf("%d\n", temp[n - 1][m - 1]);
	return (0);
}

 

문제 해설


2차원 배열 temp를 전부 -1로, 좌상단은 1로 초기화 해줍니다.

bfs함수의 가장 안쪽의 첫 번째 if 문을 보시면 벽을 만났을 때 지금 껏 벽을 부순적이 있는지를 wall 변수로 체크합니다.

이 wall 변수는 구조체 안에서 확인하게 했습니다.

벽을 부순적이 없는데 벽을 만난 경우 그 벽으로 이동할 수 있게 삽입 해주고 벽을 부순적이 있다고 큐에 wall 변수를 1로 초기화 해줍니다.

 

두 번째 if 문은 벽이 아닌곳을 만났을 때 방문한 적이 있는지 없는지 확인을 하는데요

이 때 wall 변수가 0이든 1이든 상관없습니다.

1이면 자연스럽게 visited[ny][nx][1]를 확인해서 벽을 부수고 이동했던 경로인지를 파악하기 때문이죠

0이면 그냥 이동해도 상관 없을 테고요

 

이런식으로 벽을 한번만 부수게끔 처리하면서 while로 큐가 빌 때까지 면서 우하단 방문 체크하기 전 까지 반복했습니다.

 

그 후 배열의 우하단을 출력하고 끝내는 방식으로 구현했습니다.

반응형