Hongveloper
[백준]광고
백준저지 [광고]https://www.acmicpc.net/problem/1305 • kmp 알고리즘에 대한 정확한 이해가 되어야 풀 수 있는 문제이다. • kmp 알고리즘은 이전 포스팅에 자세히 설명을 해놨으니 참고 바란다! • 현재 보이는 문자열 길이에서 “접두사와 접미사가 같은 최대 길이를 빼면” 정답이다. #include #include using namespace std; int * getPi(string p) { int * pi = new int[(int)p.size()]; pi[0] = 0; int j = 0; for (int i = 1; i < (int)p.size(); i++) { while (p[i] != p[j]) { if (j == 0) { pi[i] = j; break; } j =..
트리2
[이진 트리]• 트리 중에서 가장 많이 쓰이는 트리이다.• 정의- (1) 공집합이거나- (2) 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다.• 정의에서 ‘이진 트리’의 개념이 재귀적으로 들어간다는 점에 유의하자! 이진트리의 서브 트리도 이진트리의 성질을 만족하여야 한다는 것! • 위 그림은 이진트리인지를 알아보자.• 먼저 SUB3을 보자. SUB3은 하나의 노드 D로만 이루어져 있다. 만약 노드 D를 SUB3의 루트라고 생각하면 D의 왼쪽, 오른쪽 서브트리는 공집합이다. 하지만 정의 (1)에 의해서 공집합도 이진트리이므로 정의 (2)에 의하여 SUB3은 루트와 공집합 서브트리 2개를 갖는 이진트리이다.• SUB1은..
트리1
[트리의 개념]• 리스트, 스택, 큐 등이 선형 자료구조라고 한다면 트리는 비선형(계층적) 자료구조이다.• 계층적 자료구조는 ‘회사 조직’, ‘의사 결정 트리’ 등의 형태를 표현한다.• 리스트, 스택, 큐 등이 데이터 삽입, 삭제, 조회 등에 초점을 맞춘 자료구조라고 한다면, 트리는 어떠한 형태를 표현하는데 초점을 맞춘 자료구조다.• 그렇다고 트리에서 삽입, 삭제, 조회가 중요하지 않다는 것이 아니다. 단순히 무언가를 표현하는 것에 최적화된 자료구조라는 뜻이다. [트리의 용어] • 노드: 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J, K를 노드(node)라 한다.• 루트: 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.• 서브 트리: 전체 노트 집합 ..
[C++]포인터와 배열3
• 포인터와 배열에 대한 마지막 글이 될 것 같다.• 이번 포스트에서는 필자가 포인터와 배열의 공부하면서 가장 헷갈리고 애매했던 것에 대해 이야기하려고 한다.[char a[]와 char *a 차이]• 결론부터 말씀드리자면, char a[]와 char *a는 전혀 다르다.• 차이점은 - 배열: 같은 타입의 연속적인 요소들이 미리 할당된 공간, 크기와 위치가 고정되어 있다. - 포인터: 할당된 메모리 공간을 가리킬 수 있으며, 변경할 수도 있다. 또한 배열을 가리킬 수 있으며, 동적으로 할당한 배열처럼 흉내내어 쓸 수 있다. • 아마 헷갈리는 이유는 함수의 Formal Parameter에 관한 것이라 생각한다.(cf. void func(char * a); 라는 함수를 호출할 때 char a[]; func(a..
[C++]포인터와 배열2
[포인터 배열] • 배열을 가리키는 포인터를 뜻한다. 그럼 초기화 방법을 보도록 하자. #include using namespace std; int main(void) { int arr[3]; int *p; p = arr; // 배열의 이름은 배열의 시작주소를 나타내는 상수 값 cout ※ int a[2][3][4] - int형 배열 메모리(int [3][4])가 2개 있는 3차원 배열을 뜻함 - 각 요소가 int[3][4]형 이므로 int [3][4]를 가리키는 포인터(int (*p)[3][4])를 선언한다. [예시 2] #include using namespace std; int main(void) { int a[2][3] = { 1, 2, 3, 4, 5, 6 }; int(*p)[3] = a; for..
[C++]포인터와 배열1
• 필자는 크게 포인터와 배열의 관계에서 크게 “포인터 배열”과 “배열 포인터”가 있다고 생각한다.• 참고로 필자는 “포인터 배열”과 “배열 포인터”에 대해 용어가 혼동이 왔었는데 아래와 같이 화살표를 그려서 혼동을 해결했다. 필요한 사람만 참고했으면 좋겠다. - 포인터 배열 : 포인터→배열 – 포인터는 배열을 가리킴! - 배열 포인터 : 배열→포인터 – 배열은 포인터다! [포인터와 배열 사이의 기본적인 관계 이해] • 우선 배열의 이름이 갖는 의미부터 명확하게 집고 넘어가야 한다.• n차원 배열의 이름은 배열의 선두번지 주소를 대표한다.• 배열의 이름은 상수인 것이다!• 아래 예시는 기본적인 것이니 답을 보지 말고 출력을 예상해보자. #include using namespace std; int main..
[C++]포인터
[포인터 개념] • 변수의 주소나 배열의 이름을 포인터의 값으로 가진다. • 주 메모리상의 여러 형태의 주소를 값으로 취한다. • 포인터가 1byte char형을 가리키던 8byte double형을 가리키던 가리켜야 할 주소는 모두 4byte(32bit)이다. [주소 개념 이해] • 변수 앞에 &를 붙일 경우 변수의 주소를 말한다. • ‘&’를 주소 연산자라고 한다. • 주소는 컴파일러에 의해 결정된다. [포인터 초기화 방법] //방법 1 int a = 26; int *pa; pa = &a; //방법 2 int b = 26; int *pb = &b; [예시1] int a = 7; int *p = &a a 표현출력 값설명p 표현a7a 변수의 값*p==*(0x789)&a0x789a 변수의 주소p*&a7a 변..
KMP 알고리즘
KMP알고리즘 백준저지 [찾기] https://www.acmicpc.net/problem/1786 본 문제를 해결하기 위해서는 KMP알고리즘에 대해 학습이 되어야한다. (참고로 전 이 알고리즘을 이해하는데 2주가 걸렸다는... T^T...) 먼저 이 알고리즘은 '찾기' 흔히 [CTRL] + [F]를 눌러 문자열 검색을 하는 기능에 필수적으로 들어가는 알고리즘이다. KMP는 Knuth, Morris, Prett의 사람 이름 앞자를 따서 만든 이름이다. 흔히 찾기 알고리즘을 구현하라고 하면 아래와 같은 방식으로 구현을 할 수 있을것이다. "ABCDEF"란 Text에서 "CD"란 Pattern을 찾는다고 한다면, 012345TextABCDEF 01 PatternCDText[0]과 Text[1]이 Pattern..
[C++]new & delete
malloc & free를 대신하는 new & delete 먼저 C언어의 malloc & free를 이용한 동적할당을 아래 코드로 살펴보자. #include #include #include #pragma warning(disable: 4996) using namespace std; char * MakeStrAdr(int len) { char * str = (char *)malloc(sizeof(char) * len); return str; } int main(void) { char * str = MakeStrAdr(20); strcpy(str, "I am so happy~"); cout