목차

0x00 수식의 괄호 쌍이란?

0x01 문제 해결을 위한 관찰

0x02 문제 해결 방법

0x03 연습문제


0x00 수식의 괄호 쌍이란? 

수식의 괄호 쌍이 짝이 맞는지 확인해보자. 

( 이 있으면 ) 으로 닫아야 짝이 맞다. { 이 있으면 } 이 있어야한다. 

두 번째 식에서 (12+4} 여기가 틀렸다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제다. 

0x01 문제 해결을 위한 관찰 

아래의 3개 수식 중에 올바른 괄호 쌍은 무엇 무엇이 있을까? 

결론부터 말하면 첫 번째 식만 올바른 괄호 쌍이다. 

판단 방법 중에 가장 보편적인 방법은 바로 안쪽부터 짝 맞추기를 해서 지워나가는 방법이다. 

그리고 관찰력이 뛰어나다면,  ')' 의 개수가 '(' 의 갯수를 넘지 않으면 된다는 사실도 있다. 

괄호의 종류가 () 말고도 {}, [] 이 있다면, 여는 괄호의 갯수와 닫는 괄호의 갯수 비교만으로 해결되지 않는다. 

 

우리는 머릿속으로 어떤 로직을 거쳐서 판단한 걸까? 생각의 과정을 관찰하여 코드로 구현해보자. 

스택을 이용하여 구현해보자. 

아래의 관찰을 인지해야 한다. 

"닫는 괄호는 남아있는 괄호 중에서
가장 최근에 읽은 여는 괄호와 짝을 지어 없애버리는 명령이다. " 

여는 괄호는 모두 스택에 넣는다. 

1. 스택을 하나 두고, 문자열을 읽어 나가다가 여는 괄호를 만나면 모두 스택에 넣는다. 

2. 문자열을 읽어 나가다가 닫는 괄호를 만나면 스택의 top을 확인한다. 

3. 지금 읽은 것이 닫는 괄호이고 스택의 top이 여는괄호라면?  쌍이 올바른 것이다.

4. 따라서 스택의 top인 여는 괄호를 스택에서 지운다. pop() 

 

올바르지 않은 괄호 쌍 

올바르지 않은 괄호 쌍의 경우, 과정을 살펴보자. 

1. 문자열을 읽다가 만난 여는 괄호 2개는 모두 스택에 넣는다. 

2. 닫는 괄호 ) 를 만나면, 스택의 top을 확인한다. 

현재 스택의 top은 { 이다. 

3. 스택의 top인 {와 닫는괄호 ) 는 짝이 안맞는다. 

올바르지 않은 괄호 쌍의 예시 2가지 

1. 문자열을 끝까지 읽었는데, 스택에 여는 괄호가 남아있다. 

2. 문자열을 끝까지 읽고 스택도 비었는데, 닫는 괄호가 남아있다. 

0x02 문제 해결 방법 

올바른 괄호 쌍 판단을 위해 문제 해결 방법을 정리해본다. 

 

1. 여는 괄호가 나오면 스택에 추가.

2. 닫는 괄호가 나왔을 경우, 스택의 top이 짝이 맞는 괄호라면 pop 

3. 스택에 괄호가 남아있지 않으면 올바른 괄호 쌍. 

스택이 비었을 때 top을 참조하면 런타임에러!

0x03 연습문제 

수식의 괄호쌍이 코딩테스트에서 무조건 나온다고 할 정도로 중요하진 않지만,

stack을 이용한 문제가 많기 때문에 연습문제를 꼭 풀어보자. 

백준 문제 내 코드 
4949번 균형잡힌 세상 균형잡힌 세상 내 코드
3986번 좋은 단어  좋은 단어 내 코드
9012번 괄호  
10799번 쇠막대기  
2504 괄호의 값 괄호의 값 내 코드

 


다음 시간에는 BFS를 배운다. 

공부 자료 출처 : 바킹독 알고리즘 수식의 괄호 쌍

728x90

'알고리즘 > 실전 알고리즘' 카테고리의 다른 글

0x0A강 - DFS  (0) 2021.12.07
0x09강 - BFS  (0) 2021.12.07
0x07강 - 덱  (0) 2021.11.24
0x06강 - 큐  (0) 2021.11.23
0x05강 - 스택  (0) 2021.11.23

스택이란?

 

스택에 10, 20, 30 순서로 숫자를 3개 넣어봅니다. (push 연산)

가장 먼저 들어간 10이 맨 아래에 있게 됩니다. 

 

스택의 push 연산

 

10을 즉시 꺼낼 수 없고, 30 부터 꺼내야 마지막으로 10을 얻을 수 있습니다. (pop 연산)

 

스택의 pop 연산

 

이처럼 '가장 먼저 들어간 요소가 가장 마지막에 나오는 구조 입니다. 

그래서 FILO (First In Last Out) 라고 부릅니다. 

자동메모리가 스택을 기반으로 동작하고, 대부분의 네트워크 프로토콜도 스택을 기반으로 구성되어 있습니다. 

 


 

배열로 구현하는 스택 

 

배열을 이용하면, 동적으로 스택의 길이를 조절할 수 없지만, 구현이 간단합니다. 

사용자가 정한 숫자만큼의 길이를 가진 배열을 만듭니다. 

그리고 최상위 노드의 위치를 알고있는 변수로 삽입과 제거 연산을 합니다. 

 

 

스택의 노드 

 

스택에 들어갈 노드입니다. 

데이터 하나를 담는 노드를 구조체로 표현합니다. 

노드의 위치는 배열의 인덱스로 알 수 있습니다. 

typedef struct Node {
	int data;
}Node;

 

다음은 스택 구조체입니다. 

구조체 ArrayStack에 필요한 필드는 세 가지 입니다. 

배열의 길이
배열
최상위 노드의 위치 

노드가 최대 몇 개 들어갈 수 있는지 배열의 길이를 알아야 합니다. 

그리고 노드를 저장할 '배열'이 필요하고, 최상위 노드의 위치로 삽입/제거 합니다. 

typedef struct ArrayStack {
	int capacity;		/* 배열 용량 */
	int top;	/* 최상위 노드 위치 */
	Node* arrayNodes;	/* 노드들을 보관하는 스택배열 */
}ArrayStack;

노드 배열은 포인터로 선언되어 있습니다. (포인터는 배열로 사용할 수 있습니다)

 

 

 

스택의 생성과 메모리해제 

 

CreateArrayStack() 함수는 배열의 최대길이를 이용하여 스택을 생성합니다.  

/* 스택 생성.  메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
	printf("[ 스택 생성 CreateArrayStack ]\n");

	/* 스택을 자유 저장소에 생성 */
	(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	/* 용량 만큼의 노드들을 자유 저장소에 생성 */
	(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);

	// 필드 초기화 
	(*stack)->capacity = capacity;
	(*stack)->top = 0;
}

 

 

FreeArrayStack() 함수는 노드와 스택을 자유 저장소에서 해제합니다.

void FreeArrayStack(ArrayStack** stack) {
	printf("[ 메모리 해제 FreeArrayStack ]\n");

	free((*stack)->arrayNodes);
	free((*stack));
}

 

 

 

삽입 연산 (PUSH)

 

스택 구조체가 알고있는 top 위치의 노드에 데이터를 넣습니다.

배열 인덱스가 top이 됩니다. 

데이터를 넣고, top위치를 갱신해줍니다. 

void Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;
}

 

 

스택이 꽉 찼을 때를 확인하는 Push 함수 

 

스택이 꽉 찼을 때 push를 안하고 종료하는 코드를 추가해봤습니다. 

 

capacity와 top이 같은지 확인합니다. 

Push의 리턴을 bool로 바꾸고, 삽입이 불가하면 false를 리턴하도록 했습니다. 

 

bool Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	if (stack->capacity == stack->top) {
		printf("[ 용량초과! ] 삽입이 불가합니다. \n");
		return false;
	}

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;

	return true;
}

 

 

삽입/제거 연산을 확인해본 main 함수 코드입니다.

 

 

int main() {

	ArrayStack* stack = NULL;

	CreateArrayStack(&stack, 10);

	// 12번 Push
	for (int i = 10; i <= 120; i+=10) {
		if (!Push(stack, i)) {
			break;
		}
	}

	// 5번 Pop
	for (int i = 0; i < 5; i++) {
		printf("%3d를 제거합니다.\n", Pop(stack));
	}
	
	return 0;
}

 

배열 최대 길이가 10인데, Push 연산을 12번 했을 경우 콘솔 화면 입니다. 

10번 넣고, 11번 넣으려고 할때 용량이 초과되서 for 문을 break 합니다.

이어서 제거 연산을 5번 수행합니다. 

 

 

 

스택용량이 Full 인지 확인하는 함수로 분리하면 더 좋을 것 같습니다. 

 

 

 

제거 연산 (POP)

 

삽입과는 달리, top 값을 1 감소하면 됩니다. 

그리고 top 위치에 있던 data를 호출자에게 반환합니다. 

int Pop(ArrayStack* stack) {
	printf("[ 제거연산 Pop ]\n");

	int location = --(stack->top);

	return stack->arrayNodes[location].data;
}

POP 연산 시, 배열의 인덱스를 주의해야 합니다. 

왜냐하면 top이 1이라면, 노드가 위치하는 실제 인덱스는 0이기 때문입니다. 

 

 

 

스택이 비었는지 확인  : Pop 전에 확인 

 

/* 스택이 비었는지 확인 : 제거 전에 확인  */
int isEmpty(ArrayStack* stack) {
	// true 1 반환. false 0 반환 
	return (0 == stack->top);
}

 


 

전체 코드 

 

배열길이는 10을 주고 10부터 100까지 10개의 숫자를 PUSH 합니다. 

12번의 POP을 시도하지만 10번까지만 하고 종료되는 코드입니다. 

 

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


typedef struct Node {
	int data;
}Node;

typedef struct ArrayStack {
	int capacity;		/* 배열 용량 */
	int top;	/* 최상위 노드 위치 */
	Node* arrayNodes;	/* 노드들을 보관하는 스택배열 */
}ArrayStack;


/* 스택 생성.  메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
	printf("[ 스택 생성 CreateArrayStack ]\n");

	/* 스택을 자유 저장소에 생성 */
	(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	/* 용량 만큼의 노드들을 자유 저장소에 생성 */
	(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);

	// 필드 초기화 
	(*stack)->capacity = capacity;
	(*stack)->top = 0;
}

/* 메모리 해제 */
void FreeArrayStack(ArrayStack** stack) {
	printf("[ 메모리 해제 FreeArrayStack ]\n");

	free((*stack)->arrayNodes);
	free((*stack));
}

/* 삽입 Push 연산 */
void Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;
}

/* 스택이 비었는지 확인 : 제거 전에 확인  */
int isEmpty(ArrayStack* stack) {
	// true 1 반환. false 0 반환 
	return (0 == stack->top);
}

/* 제거 Pop 연산 */
int Pop(ArrayStack* stack) {
	printf("[ 제거연산 Pop ]\n");

	int location = --(stack->top);

	return stack->arrayNodes[location].data;
}



int main() {

	ArrayStack* stack = NULL;

	CreateArrayStack(&stack, 10);

	// 10개 Push
	for (int i = 10; i <= 100; i+=10) {
		Push(stack, i);

	}

	// 12번을 pop 해본다 
	for (int i = 0; i < 12; i++) {

		if (isEmpty(stack)) {
			printf("스택이 비었습니다. \n");
			break;
		}
		else {
			printf("%3d를 제거합니다.\n", Pop(stack));
		}
	}
	
	return 0;
}

 

콘솔 결과 입니다. 

 

 


다음 포스팅에서는 링크드 리스트로 구현하는 스택을 다루겠습니다.

 

728x90

+ Recent posts