WantAirpod

세그먼트(Segment)

• 코드 세그먼트 : 컴파일된 프로그램이 저장되는 영역, 일반적으로 read-only 속성이다.
• 데이터 세그먼트 : 전역 변수 및 정적 변수가 저장되는 영역
• 힙 세그먼트 : 동적으로 할당된 변수가 할당되는 영역
• 스택 세그먼트 : 함수 매개 변수, 지역 변수 및 기타 함수 관련 정보가 저장되는 영역.

힙 세그먼트(Heap segment)

힙 세그먼트는 동적 메모리 할당에 사용되는 메모리를 적재한다. C++에서 new 연산자를 사용해서 메모리를 할당하면 이 메모리는 응용 프로그램의 힙 세그먼트에 할당된다.

int main()
{ 
	int* ptr = new int;//ptr은 힙에서 4바이트로 할당됨.
	int* array = new int[10];//array는 힙에서 40바이트로 할당됨.

	//차례로 선언했지만 순차적 메모리 주소를 갖는 것은 아님
	int* ptr1 = new int;
	int* ptr2 = new int;
}

힙의 장단점

• 힙에 메모리를 할당하는 것은 비교적 느리다.
• 할당된 메모리는 명시적으로 할당 해제하거나 (delete) 응용 프로그램이 종료될 때까지 유지된다.(메모리 릭 주의
• 동적으로 할당된 메모리는 포인터를 통해 접근한다: 포인터를 역참조하는 것은 변수에 직접 접근하는 것보다 느리다.
• 힙은 큰 메모리 풀이므로 큰 배열, 구조체 또는 클래스를 할당할 수 있다.

스택 세그먼트

• 스택 세그먼트(=콜스택)는 메인() 함수부터 현재 실행 지점까지의 모든 활성 함수를 추적하고 모든 함수 매개 변수와 지역 변수의 할당을 처리한다.
• 스택은 후입선출(LIFO) 자료구조이다. 즉, 함수 호출이 끝나고, 이전 함수로 돌아갈 때 이 함수의 바로 이전함수로 돌아가야한다. 그래서 컴퓨터는 내부적으로 스택 세그먼트를 스택 자료구조로 구현한다.(재귀)
  • 콜 스택(call stack) 이란 컴퓨터 프로그램에서 현재 실행 중인 서브루틴(함수)에 관한 정보를 저장하는 스택 자료구조이다.
  • 응용 프로그램이 시작되면 메민() 함수가 운영체제에 의해 호출 스택에 푸시됨.
  • 프로그램 실행
  • 함수호출이 발생하면 함수가 콜 스택에 푸시됨.
  • 현재 함수가 끝나면 해당함수는 콜 스택에서 해제 됨.
  • 따라서 콜 스택에 푸시된 함수를 살펴보면 현재 실행 지점에서 이동하기 위해 호출된 모든 함수를 볼 수 있다.

#include <iostream>
using namespace std;
void func()
{
	cout << "func" << endl;
	 
 }
void func2()
{ 
	cout << "func" << endl;
}
void func3()
{
	cout << "func" << endl;
}

int main()
{ 
	int* ptr = new int;//ptr은 힙에서 4바이트로 할당됨.
	int* array = new int[10];//array는 힙에서 40바이트로 할당됨.

	//차례로 선언했지만 순차적 메모리 주소를 갖는 것은 아님
	int* ptr1 = new int;
	int* ptr2 = new int;

	//콜 스택 ex
	func();
	func2();
	func3();

}

• 콜 스택 자체는 고정된 크기의 메모리 영역이다.
• 스택 프레임(stack frame) : 콜 스택에 넣고 빼는 데이터, 하나의 함수 호출과 관련된 모든 데이터를 추적
• 스택 포인터(stack pointer) : cpu의 작은 조각인 레지스터는 현재 호출 스택의 최상위 위치를 가리킨다.

콜 스택 발생 순서

1. 프로그램에 함수 호출이 발생
2. 스택 프레임이 생성되고 콜 스택에 푸시된다. 스택 프레임은 다음과 같이 구성된다.
   1. 함수가 종료되면 복귀할 주소
   2. 함수의 모든 매개변수
   3. 지역 변수
   4. 함수가 반환할 때 복원해야 하는 수정된 레지스터의 복사본
3.  CPU가 함수의 시작점을 점프한다.
4. 함수 내부의 명령어를 실행한다.

함수가 종료 되면 다음단계가 수행된다.

1. 레지스터가 콜 스택에서 복원된다.
2. 스택 프레임이 콜 스텍에서 튀어나온다. 이렇게 하면 모든 지역 변수와 매개 변수에 대한 메모리가 해제된다.
3. 반환 값이 처리된다.
4. CPU는 반환 주소에서 실행을 재개한다.

일반적으로 콜 스택이 어떻게 동작하는지에 대한 모든 세부사항은 중요하지 않다. 그러나 함수가 호출될 때와 종료될 때 함수가 콜 스택에서 효과적으로 작동하다는 것을 이해하면 재귀를 이해할 때와 디버깅할 때 유용하다.

스택 오버플로 (stack overflow)

• 스택 세그먼트는 크기가 제한되어 있으므로 제한된 양의 데이터만 저장할 수 있다. 
• window 운영체제에서 기본 스택 세그먼트의 크기는 1MB다. 
• 응용 프로그램이 스택 세그먼트에 너무 많은 정보를 담으려고 하면 스택 오버플로(stack overflow)가 발생한다.
• 스택 오버플로는 보통 스택 세그먼트에 1)너무 많은 변수 2)중첩된 함수 호출 이다.

ex)1) 너무 큰 배열 2)무한 루프

void foo()
{
	foo(); //2) 무한 루프 
} 
int main()
{
	int stack[100000000]; //1) 너무 많은 크기의 배열
    foo(); 
}

• 스택에 메모리를 할당하는 것은 비교적 빠르다.
• 스택에 할당된 메모리는 스택 범위에 있을 때만 접근 할 수 있다.
• 스택에 할당된 모든 메모리는 컴파일 타임에 알려진다. 메모리는 변수를 통해 직접 접근 가능.
• 스택은 비교적 크기가 작으므로 스택 공간을 많이 차지하는 지역 변수를 만드는 것은 좋지 않다.
  
  출처: https://boycoding.tistory.com/235 [소년코딩]

동적할당 시 메모리 delete를 안해주면 메모리가 누수된다.

누수된 부분을 찾는 방법

• int형 400byte 동적할당한다. 

int main()
{
	int* buff = new int[100];

}

• 전처리 및 함수를 입력한다.

//메모리 누수관련 전처리
#include <iostream>
#define _CRTDBF_MAP_ALLOC 
#include <cstdlib>
#include <crtdbg.h>

int main()
{
	int* buff = new int[100];
	_CrtDumpMemoryLeaks();  //메모리 누수 함수 체크 

}

(출력이미지)

출력은 되었지만, 어느 부분에서 메모리 누수 되었는지 알수없다.

• 해결방법

#include <iostream>
//메모리누수 체크 코드
//#include "pch.h"
//#include <Window.h>
#define _CRTDBF_MAP_ALLOC
#include <cstdlib>
#include <crtdbg.h>

//어느 부분인지 체크하는 전처리 및 정의
#ifdef _DEBUG
#define new new (_NORMAL_BLOCK, __FILE__, __LINE__)
#endif

int main()
{
	int* buff = new int[100];
	_CrtDumpMemoryLeaks();

}

ifdef 부분을 추가하면 다음과 같이 어느부분에서 메모리누수가 발생했는지 알수있다.

또한, 더블클릭하면 그 지점으로 이동한다.

https://luckygg.tistory.com/226

• char[]의 경우는 local data를 가지는 포인터이다. 따라서 수정가능.
• char* 경우는 global static data 할당한 후 그의 포인터를 가지는 것이기 때문에 수정 불가능.!

char str[] = "hello world";  //local data 수정 O
str[3] = '3'; 
cout << str << endl; 

char *str2 = "hello world"; //global static data 수정 X
str2[3] = '3'; //error 

일반 변수

• 직접 값을 보유.

포인터

• 다른 값의 주소(또는  NULL)를 보유.

레퍼런스

• 참조자(Reference)는 변수에 "별명"을 붙인다고 한다.
• 그 별명을 통해서 변수의 메모리 공간에 접근이 가능하다.
• 참조자(Reference)는 이름 앞에 "&"붙여서 선언한다.
• 참조자(Reference)는 변수에 대해서만 선언이 가능, 선언과 동시에 누군가를 참조 해야만 한다.
• 참조자(Reference)는 참조의 대상을 바꾸는 것이 불가능.
• 참조자(Reference)는 NULL로 초기화 하는 것이 불가능.

세 가지 종류의 참조형 지원

1. non-const 값 참조형
2. const 값 참조형
3. r-value 참조형 

1)사용법

• 참조자(Reference)가 가지고 있는 값을 변경하면 원래 있던 변수의 값이 변경됨.
• 코드 중에 '&'는 주소(address)를 의미하지 않고 참조(reference)를 의미함.
• 따라서 num1과 num2는 동의어라고 취급된다. (num1 -= 10 해주면 num2도 -10 됨)

int num1 = 10;
int &num2 = num1; 
num2 += 10; //num1,2 모두 20으로 변환

2)참조자와 함수

• 레퍼런스를 함수의 매개변수로 사용 가능(Call by Reference)
• C에서는 Call-by-pointer, C++에서는 Call-by-Reference

두 가지 차이점 

1.NULL 사용 여부

• 포인터는 NULL 사용을 허용O
• 레퍼런스는 NULL 사용 허용X

struct Point 
{
	int x;
	int y;
};

struct Point *aaa = NULL;
	aaa->x = 120;
	aaa->y = 240;

• 하지만, 레퍼런스는 문제 발생하지 않음 why ? 페러런스 자체는 NULL을 할당할 수 없도록 아예 처음부터 제한함.
• 포인터와 목적은 같지만 잘못된 참조로 인해 발생하는 오류를 방지하기 위해 고안.

2.참조 대상 할당 및 접근

• 포인터는 참조대상에 대해 &연산을 통해 주소값을 할당함.
• 하지만, 레퍼런스는 참조 대상을 그대로 할당함.
• 레퍼런스는 선언과 동시에 초기화 하지 않으면 컴파일 오류가 발생함. (NULL을 할당 불가)

int a = 10;  
int *ppp = &a;  //포인터변수에는 주소값이 할당됨.  
int &r = a;   //레퍼런스에는 참조대상을 그대로 할당함.

결론

레퍼런스는 포인터를 잘못 사용해서 생기는 수많은 재앙과도 같은 문제들을 최소화하기위해 등장

Use references when you can, and pointers when you can have to
사용할 수 있다면 참조자를, 어쩔 수 없다면 포인터를 써라

lower_bound란

이진탐색(Binary Search)기반의 탐색 방법. (배열 또는 리스트가 정렬 되어야 있어야함.)

 : 찾고자 하는 값 이상의 값이 처음 나타나는 "위치" 

	int arr[10] = {1,2,4,5,6,6,7,7,7,9 };
	//lower_bound : 정수 값 찾음
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 10, 6) - arr  << endl; //4
	cout << "lower_bound(7) : " << lower_bound(arr, arr + 10, 7) - arr  << endl; //6
	cout << "lower_bound(8) : " << lower_bound(arr, arr + 10, 8) - arr  << endl; //9
	cout << "lower_bound(9) : " << lower_bound(arr, arr + 10, 9) - arr  << endl; //9

단, 만약 못찾으면 찾고자 하는 값 배열의 마지막 위치를 반환한다.

upper_bound

lower_bound와 마찬가지로 이진탐색기반의 탐색법 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어야한다.

 : 찾고자 하는 값 초과하는 값이 처음 나타나는 "위치"

	cout << "upper_bound(6) : " << upper_bound(arr, arr + 10, 6) - arr  << endl; //6
	cout << "upper_bound(7) : " << upper_bound(arr, arr + 10, 7) - arr  << endl; //9
	cout << "upper_bound(8) : " << upper_bound(arr, arr + 10, 8) - arr  << endl; //9
	cout << "upper_bound(9) : " << upper_bound(arr, arr + 10, 9) - arr  << endl; //10

단, 만약 못찾으면 찾고자 하는 값 배열의 마지막 위치를 반환한다.

1) char* v;

v는 문자, 문자열이 저장된 메모리의 첫 주소를 저장할 수 있는 포인터변수

v 주소 메모리의 내용 변경 가능

v 문자열 변경 가능

ex)

char* v ="문자열 상수1"; //초기화 했어도 코드중에 언제나 변경 가능
v= "문자열 상수2"; 		//변경 가능
v= "문자열 상수3"; 		//변경 가능 

2)const char* v;

v는 문자열이 저장된 메모리의 첫 주소를 저장할 수 있는 포인터변수, 즉, v는 "상수문자열"의 포인터변수라는 의미

v 주소 메모리의 내용 변경 불가

v 문자열 변경 가능

한편, const의 대상이 v자체가 아니므로  v가 가리키는 주소는 변경가능함.

ex)

const char* v = "난 문자열 상수1이다"

위 처럼 초기화 했어도, 코드상에서 아래 처럼 다른 문자열의 메모리 주소를 대입가능하다는 말

v="난 문자열 상수2임" //가능함 v에 다른 문자열 주소는 대입가능
*v="난 문자열 상수2임"; //허용 안됨. v는 주소 메모리의 값을 변경 의도한 것인데, const char* v; 의 정의가 이런거 못하게 하는 것

3)char* const v;

v는 문자열이 저장된 메모리의 첫 주소를 저장할수 있는 포인터변수

초기화 할 때 한번 지정된 문자열& 메모리 주소는 변경 못함

ex)

char* const v = "난 문자열 상수1이다." ; 로 초기화 했는데 
v="난 문자열 상수2임"; 으로 변경 허용 안됨.

문제

문제설명

hit에서 cog를 가는 방법의 갯를 리턴

시행착오

처음에 DFS로 풀려고 시도했는데 words를 탐색할때 앞으로 갔다가 뒤로 갔다가 하니깐 visit 처리가 꼬이면서 결국 gg

풀면서도 bfs로 풀면 쉽겠다 생각이 들어서 40분동안 dfs로 풀다가 결국 bfs로 넘어가서 쉽게 품...

하지만, bfs에서 계속 2,3번이 안나옴 알고보니 꼭 words가 세글자가 아닌 10글자까지 가능한 것... 문제 잘 읽자..

문제풀이

1) begin값에서 변환가능한 모든 경우의 수를 queue에 넣음 

2) bfs를 돌리며 target이 나오는 순간 모든 함수 종료

3) 트리구조를 떠올리며 자식 노드로 이동 할때 +1을 해주기 위해 queue를 페어로 구현하였고 두번째 값에 노드 번째를 나타냄.

난이도

★★★☆☆

dfs 하면서 오기 생겨서 테스트케이스 많이 생성하게 됨... dfs로 다시 구현 예정..

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
bool visit[50] = { false, };
 
bool flag = false;
int bfs(string begin, vector<string> words, int num, string target)
{
	int answer = 100;
	queue<pair<string, int>> q;
	q.push({ begin,0 });
	int sizeQueue = 0; 
	int ansNum = 0;
	while(!q.empty())
	{ 
		if (flag == true)
			break; 
		string begin = q.front().first;
		int ansNum = q.front().second;
		q.pop();
		ansNum++;  
		for (int w = 0; w < words.size(); w++)
		{
			int cnt = 0;
			for (int i = 0; i < begin.length(); i++)
			{
				if (begin[i] == words[w][i])
				{
					cnt++;
				}
			} 
			if (cnt == begin.size()-1 && !visit[w])
			{
				if (words[w] == target)
				{
					flag = true; 
					answer = ansNum;
					break;
				}
				visit[w] = true;
				q.push({ words[w],ansNum });
			}
		} 
		sizeQueue = q.size(); 
	}

	return answer;


}

int solution(string begin, string target, vector<string> words)
{
	int answer = 100;
	int in = 100;
	 
	in = bfs(begin, words, 0, target);
	answer = min(in, answer);
	in = 0;
	 
	if (answer == 100)
		answer = 0;
	return answer;
}

int main()
{
	cout << solution("hit", "cog", { "hot", "dot", "dog", "lot", "log","cog" }) << endl;// hot -> dot -> dog -> log -> cog 
 	//cout << solution("hit", "hhh", { "hhh", "hht" }) << endl; //2
	//cout << solution("zzz", "zzz", { "zzz" }) << endl;
	//cout << solution("hit", "zzz", { "zzz" }) << endl;
	//cout << solution("hit", "zzz", { "zzz", "zyz", "xzz", "xyz", "hyt", "hyz", "xiz", "hiz" }) << endl;// 4 :  hyt -> xiz -> xzz -> zzz //4번



}

문제

입출력 예시

풀이방법

1) 마스킹된 제재사용자 아이디로 가능한 유저 아이디를 체크한다.

2) 체크한 아이디들의 경우의 수를 따져준다. 

  2)-1 각각의 유저 아이디는 순서가 바뀐것은 하나로 취급한다.

3) 각 유저아이디의 조합의 경우를 count 해준다.

1) 이중포문으로 가능한 경우의 유저 아이디의 index를 추출하여 벡터에 담는다.

2) 체크한 아이디의 경우의 수를 따져주기 위해서 set 자료 구조를 이용 하였다. 

ex) 0123 = 0132가 같은 경우의 수 이기 때문이다. 단 set에 넣을 때는 0123과 0132일 떄 visit배열에 체크를 하였고 0부터 차례 대로 visit여부에 따라서 string으로 형변환하여 0132는 0123꼴로 나타내줬다 그래야만 set에 들어갈때 중복제거가 가능하기 때문이다.

3) 상기 set에 조합을 넣은 이유는 결론적으로 set에 들어간 크기가 전체 조합의 경우의 수와 같다는 것을 의미하기 때문

난이도

★★★☆☆

dfs를 구현하고 set에 어떻게 넣을지 고민을 좀 오래했음.. visit배열을 순서대로 추출하여 적재하는 방식은 구글에 도움을 받음.. 항상 풀고 나면 덜 어려워 보임 (다시 풀어볼 만함)

코드

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;
bool visit[50] = { false, };

vector<int> v[10];
 
set<string> s;

void  dfs(int num, int N) 
{
	if (num == N) 
	{
		string tmepStr = "";
		for (int i = 0; i < 10; i++)
			if (visit[i] == 1)
			{
				tmepStr += to_string(i);
			}
		s.insert(tmepStr);
		return;
	}

	for (int j = 0; j < v[num].size(); j++) 
	{
		int cur = v[num][j];
		if (visit[cur] == 1) continue;
		visit[cur] = 1;
		dfs(num + 1, N);
		visit[cur] = 0;
	}
 
} 

int solution(vector<string> user_id, vector<string> banned_id)
{
	int answer = 0;
	for (int i = 0; i < banned_id.size(); i++)
	{
		for (int j = 0; j < user_id.size(); j++)
		{

			int cnt = 0;
			int starcnt = 0;
			if (banned_id[i].length() != user_id[j].length())
				continue;
			for (int w = 0; w < banned_id[i].length(); w++)
			{
			
				if (banned_id[i][w] == '*')
				{
					starcnt++;
					continue;
				}
				if (banned_id[i][w] != user_id[j][w])
				{
					break;
				}
				else if( banned_id[i][w] == user_id[j][w])
				{
					cnt++;
				}
			}
			if (user_id[j].length() - starcnt == cnt)
			{
				v[i].push_back(j);
				//visit[j] = true;
			}
		}
	}
	 dfs(0, banned_id.size());
	 answer = s.size();
	return answer;
}
int main()
{
	//solution({ "frodo","fradi","crodo","abc123","frodoc" }, { "fr*d*","abc1**" });
	solution({ "frodo","fradi","crodo","abc123","frodoc" }, { "fr*d*","*rodo","******","******"});
	return 0;
}