문자열과 char 포인터

오늘은 심심한데 문자열에 대해서 이야기 해볼까 해요~ 문자열과 포인터는 C언어에서 너무나 귀찮은 놈들인데,,, 그래도 꼭 쓰이니까요. char 자료형은 문자를 변수로 갖는 건 모두 아는 사실이죠?

근데~ 우리는 문자열을 쉽게 할당하고 싶단 말이에요. 우리는 배열이라는 아주 편리한 변수 선언 법을 알고 있답니다.

배열로 문자열을 표현하는 방법을 알아보겠습니다.

char hello[6] = { 'h','e','l','l','o','\0' };

이 표현은 char이 자료형을 배열로 문자열을 표현한 방법이랍니다. '\0' 라는 문자는 NULL문자라는 뜻입니다. 문자열의 끝을 알려줍니다.

그래서 hello가 다섯글자임에도 불구하고 배열 크기를 6으로 잡은 겁니다.

또 이런 선언법도 가능합니다.

char hello[6] = "hello";

그렇다면 우리가 문자열의 길이를 알고 싶다면 널문자가 나타나기 전까지만 세어주면 문자열의 길이를 알 수 있겠네요.

#include <stdio.h>

int main() {
        char *ptr = "ABCDEF";
        int len = -1;
       
        while (*(ptr+(++len)));
        printf("문자열 길이: %d\n", len);
}

그 결과는 이렇겠네요.

 

len=-1인 이유는 null문자 이전까지만 세어주기 위함입니다. while의 조건절은 null이면 멈추어 버립니다. 여기까지는 쉽네요. 포인터로는 어떻게 표현할까요?

사실 문자열("~~~~")은 그 문자열이 시작되는 주소를 가리키게 됩니다. 주소를 가리킨다!?  그러면 포인터가 생각나지 않나요?

왜냐면 주소를 포인터로 가리키면 문자열을 찾을 수 있으니까요.

그러면 이렇게 선언할 수 있을까요?

char *ptr = "hello";

포인터 ptr은 "hello"라는 문자열을 가리키는 포인터입니다. 

그림에서 보는 것과 같이 ptr은 문자열 "hello"의 주소를 가리키고 있고, 그렇기 때문에 참조가 가능한 상태가 됩니다. 그렇다면 어떤 포인터 역시 hello를 가리킨다면 그 주소는 같을까요?

코드와 결과로 확인해보도록 합시다.

 

#include <stdio.h>  int main() {   	char *ptr1 = "hello"; 	char *ptr2 = "hello"; 	printf("%s, %s\n", ptr1, ptr2); 	printf("%p, %p\n", ptr1, ptr2); } #include <stdio.h> 

int main() {   
        char *ptr1 = "hello"; 
        char *ptr2 = "hello"; 

        printf("%s, %s\n", ptr1, ptr2);
        printf("%p, %p\n", ptr1, ptr2);
}

 

같다는 것을 알 수 있습니다. 우리는 이런 그림을 그려볼 수 있겠네요.

ptr1과 ptr2는 서로 같은 문자열을 가리킵니다.  배열과 포인터에 대해서 선언방법은 그렇게 차이가 없어보이죠?

그렇다면 문자열 배열과 포인터는 서로 같은 성질을 갖고 있을까요?

만약 아래와 같은 코드를 입력한다 arr에 ptr가 가리키는 문자열을 넣으라는 거겠죠??

char arr[10] = "world";

char *ptr = "hello";

arr = ptr;

 "hello"라는 문자열의 길이는 배열크기보다 작기 때문에 들어갈 것입니다. 이렇게 생각하셨다면 다시 생각해봅시다. 오류나니까요.

문자열 "hello" 그 주소 자체를 반환합니다. 그러니까 "hello"의 시작주소가 되는 것이죠. 그것이 ptr이 갖고 있는 값입니다.

arr자체는 arr[0]의 주소, 즉 배열의 시작 위치를 말합니다. 이러한 시작 주소를 마음대로 ptr이 가리키고 있는 주소로 바꿀 수 없습니다.

이 의미는 더 쉽게 풀어서 이야기하면

int a = 0;

int b = 30;

&a = b;

랑 유사한 짓거리를 하는 것이라는 거죠. 마치 a의 주소를 b의 값으로 변경하라는 것과 유사하게 되어버립니다.

하지만 그 반대는 가능합니다. 이렇게요.

char arr[10] = "world" ;

char *ptr = "hello";

ptr = arr;

ptr은 주소를 갖을 수 있는 포인터, arr은 arr[0]의 주소! 말이 되죠 이건??

그러니 ptr은 arr과 동일한 곳을 가리키게 되는 겁니다.

만약

arr = ptr;

이걸 죽어도 써야겠다. 난 arr에다가 ptr의 문자열을 진짜 안쓰면 디질거 같다.  하시는 분들은 ptr의 문자열을 복사해서 쓰는 방법밖에 없습니다.

strcpy(arr, ptr)

이렇게 하시면 arr에 ptr이 가리키는 문자열을 그대로 복사해서 arr에 쑤셔 넣습니다. 주의 할 사항은 arr의 크기는 ptr이 가리키고 있는 문자열의 길이 이상으로 커야한다는 겁니다.

그렇지 않으면 런타임 오류납니다. 컴파일에서 문자열의 길이를 검사하지 않습니다!

이 오류가 바로 그 유명한 버퍼오버플로우(buffer overflow)가 됩니다. 취약점인거죠. 버퍼오버플로우를 통해 해커는 함수의 return 주소를 변경하여 자신의 실행코드를 실행합니다. 별짓을 다할 수가 있게 됩니다그래서 그 대안으로 strncpy, strncat 이런것이 나오게 된겁니다.

그리고 또!

포인터와 배열에는 다른 차이점이 있습니다.

문자열을 초기화 할때 배열은 배열 원소를 변경할 수 있지만, 포인터는 배열의 원소를 바꿀 수 없습니다. 즉, 포인터로 초기화 한다면 상수적인 성격을 띈다라는 것입니다.

가령, 아래 코드가 있다면 ptr[0] 변경시 오류가 발생합니다.

char hello[10] = "hello";

char *ptr = "hello";

ptr[0] = 'H';  //오류

hello[0] = 'H';

하지만

char hello[10] = "hello";

char *ptr = hello; 

ptr[0] = 'H'; 

hello[0] = 'H';

이건 오류가 나지 않습니다. 왜냐면 hello는 배열이거든요. 배열은 그 원소의 값이 변경가능합니다. ptr은 배열의 시작주소를 참조하고 있는 포인터이기 때문입니다.

 

그래서 이러한 strcat를 써먹을때도

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

int main() {
        char *hello = "hello, ";  
        strcat(hello, "world");
        printf("%s\n", hello);
}

가 아닌

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

int main() { 
        char hello[20] = "hello, ";  
        strcat(hello, "world");
        printf("%s\n", hello);
}

 

이런 형태나

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

int main() {  
        char hello[20] = "hello, ";
        char *ptr = hello;  
        strcat(ptr, "world");  
        printf("%s\n", ptr);
}

이런식으로 쓰여야 한다는 겁니다. 이렇게 간단하게 문자열과 포인터에 대해서 알아보았습니다. 부족한 점은 나중에 또 보충 설명해보도록 할게요 ㅎㅎ

 

 

반응형
블로그 이미지

REAKWON

와나진짜

,

1463번 1로 만들기


문제 해석


문제는 너무 간단 합니다. 세가지 규칙이 있는데요.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.


이렇게 만들어서 1로 만들어라 이겁니다. 12를 최소로 위 규칙을 사용하면 어떤 과정을 거칠 수 있을까요?

12 - 4(1번 규칙 적용) - 2(2번 규칙 적용) - 1(2번 또는 3번 규칙 적용)

이렇게 3번으로 1을 만들 수 있다는 건데요. 


36은 어떻게 구할 수 있을까요?

36 - 12(1번 규칙 적용)

12는 위에서 구했습니다. 감이 오시죠? DP냄새가 나지 않습니까?





제약 조건
n은 1000000이하네요. O(n^2) 이상으로는 풀 수 없습니다.

풀이
 
세가지 조건과 메모이제이션을 이용해서 이 문제를 풀 수 있습니다. 


#include <cstdio>
#include <string.h>

#define min(x,y) x<=y ? x:y
#define INF 987654321
using namespace std;

int dp[1000001];

int solve(int n) {

	if (n == 1) return 0;
	if (dp[n] != -1) return dp[n];

	int ret = INF;
	if (n % 2 == 0) ret = 1 + solve(n / 2);
	if (n % 3 == 0) ret = min(ret, 1 + solve(n / 3));
        //ret = min(ret, 1+solve(n-1));
	if (n % 6 != 0) 
		ret = min(ret, 1 + solve(n - 1));

	return dp[n] = ret;
}

int main() {

	int n;
	scanf("%d", &n);

	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(n));
}




n을 규칙대로 3으로 나누어 떨어지면 3으로 나누고, 2로 나누어 떨어지면 2로 나누고, 또는 1을 뺀 규칙을 적용해서 1로 만들어보는 것입니다. 3으로 나누어 떨어지지 않거나, 2로 나누어 떨어지지 않을 땐 1을 빼는 규칙을 적용해줍니다.

왜요?

n을 1로 만들어주는데 있어서 2와 3으로 나누는 것이 유리하다는 것이죠. 어떤 수로 나누는 것이 n을 줄이는 일에 효과적이라는 겁니다. 그래서 1을 최소로 빼주고 될 수 있으면 2와 3으로 나누는 편이 더 좋습니다.  그러니 2와 3의 최소 공배수 6을 이용해서 6으로 나누어 떨어지지 않으면 1을 빼는 것을 시도하는 것입니다.


위 코드의 주석을 해제하고 if문 부분을 주석처리하여 제출해보세요. 결과는 맞지만 효율성에서 차이가 나는게 보일겁니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

BOJ [1260] DFS와 BFS



문제해석


그래프를 DFS와 BFS 순으로 탐색한 결과를 반환하면 되겠습니다.


제약조건


간선 M은 10000개 이하, 정점 N은 1000 이하입니다.

그냥 묻지도 따지지도 않고 DFS, BFS 오지게 코딩하시면 됩니다.


문제풀이



DFS와 BFS에 대한 설명은 아래의 링크를 통해서 확인해주세요.


DFS https://reakwon.tistory.com/4?category=300866

BFS https://reakwon.tistory.com/7?category=300867





코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> dfs_order = vector<int>();
vector<int> bfs_order = vector<int>();
vector<bool> visited;
int map[1001][1001];

int V,E;

void dfs(int here) {
	
	visited[here] = true;
	dfs_order.push_back(here);

	for (int to = 1; to<=V; to++) 
		if (!visited[to] && map[here][to] == 1) 
			dfs(to);
}

void bfs(int start) {

	queue<int> q;
	q.push(start);
	bfs_order.push_back(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int next = 1; next<=V; next++) 
			if (!visited[next] && map[here][next] == 1) {
				q.push(next);
				bfs_order.push_back(next);
				visited[next] = true;
			}
	}
}

void print_order(vector<int> &order) {
	for (int i = 0; i < order.size(); i++)
		printf("%d ", order[i]);
	printf("\n");
}


int main() {
	
	scanf("%d %d", &V, &E);

	int start;
	scanf("%d", &start);
	for (int i = 0; i<E; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = map[b][a] = 1;
	}

	visited = vector<bool>(V + 1);
	dfs(start);
	visited = vector<bool>(V + 1);
	bfs(start);

	print_order(dfs_order);
	print_order(bfs_order);

}

dfs_order와 bfs_order는 각각 dfs 순으로 방문된 순서를 저장하는 벡터, bfs 순으로 방문된 순서를 저장하는 벡터입니다.



반응형
블로그 이미지

REAKWON

와나진짜

,