진진진 개발일지

Git 이란? 하나의 폴더 내에서 코드의 변경점을 기록하기 위해 사용 -> 형상 관리 도구 형상 관리 도구: 소프트웨어의 변경사항을 체계적으로 추적하고 통제하는 것 Github란? 백업과 공유(협업)가 가능한 온라인 코드 저장소 내 코드를 온라이 저장소에 백업 가능 협업 시 내 코드를 공유 가능 함께 작업 가능 Git 명령어 리스트 필수 리눅스 명령어 pwd: 현재 작업하는 폴더를 보여줌 ls: 현재 위치의 모든 파일 및 폴더 리스트를 보여줌 ls -a: 숨겨진 폴더도 보여줌 mkdir : 현재 경로에 폴더를 생성 cd : 폴더 위치를 이동 - ..은 상위 폴더(디렉토리) git init: 프로젝트를 git으로 관리하기 위해 처음에 한 번만 입력하는 명령어 git add : 저장할 파일 지정 -> 모든 ..

#include #include #include // quiz_len은 배열 quiz의 길이입니다. // 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요. char** solution(const char* quiz[], size_t quiz_len) { // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요. char** answer = (char**)malloc(sizeof(char*)*quiz_len); for(int i=0;i

처음 풀이 #include #include #include // 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요. char* solution(const char* polynomial) { // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요. char* answer = (char*)malloc(sizeof(char)*50); int index=0; int var = 0; int cnst = 0; int flag = 0; int temp = 0; while(polynomial[index]){ if(polynomial[index]>='0'&&polynomial[index] 1){ int a = 1; int val ..

- 정렬된 배열에 새로운 값을 추가하려면? 1. 삽입할 위치를 이진검색법으로 조사 2. 삽입할 위치 이후의 모든 요소를 뒤로 하나씩 이동 3. 새로운 값 대입 => 복잡도: O(n) 해시법: 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것 해시 함수(hash function): 키 값을 가지고 해시 값을 만드는 과정 해시 값(hash value): 배열의 키 값을 배열의 요소 개수로 나눈 나머지 등 해시 함수를 거친 값 해시 테이블(hash table): 해시 값을 정리한 표 버킷(bucket): 해시 테이블의 각 요소 충돌(collision): 저장할 버킷이 중복되는 현상 해시 함수는 가능하면 해시 값이 중복되지 않도록 고르게 분포된 값을 만들어야 함 충돌에 대한 대처: 체인법: 같은 해시 ..

트리: 데이터 사이의 계층 관계를 나타내는 자료구조 노드(node), 가지(edge) 루트(root): 가장 윗부분에 위치하는 노드 리프(leaf): 가장 아랫부분에 위치하는 노드 (=끝 노드, 바깥 노드) 안쪽 노드(internal node): 리프를 제외한 노드 자식(child), 부모(parent), 형제(sibling) 조상(ancestor): 어떤 노드에서 가지로 연결된 위쪽 노드 모두 자손(descendant): 어떤 노드에서 가지로 연결된 아래쪽 노드 모두 레벨(level): 루트로부터 얼마나 떨어져 있는지에 대한 값. 루트는 0 차수(degree): 노드가 갖는 자식의 수 높이(height): 루트부터 가장 멀리 떨어진 리프까지의 거리 널 트리(null tree): 노드, 가지가 없는 트리..

원형 리스트(Circular list) 선형 리스트의 꼬리 노드가 머리 노드를 가리키는 자료구조 원형 리스트 상태를 판단하는 방법 빈 원형 리스트 판단: list->head == NULL 노드가 1개인지 판단: list->head->next == list->head Node* p가 머리 노드인지 판단: p == list->head Node* p가 꼬리 노드인지 판단: p->next == list->head 이중 연결 리스트(Doubly linked list) 선형 리스트에서 각 노드가 다음 노드와 앞쪽 노드에 대한 포인터를 가지고 있는 자료 구조 typedef struct __node{ Member data; struct __node* prev; struct __node* next; } Dnode; Dn..

선형 리스트: 데이터를 순서대로 나열한 자료 구조 리스트의 데이터는 노드(node) 또는 요소(element)라고 함 각각의 노드는 다음 노드를 가리키는 포인터를 가지고 있으며, 처음과 끝에 있는 노드는 각각 머리 노드(head node), 꼬리 노드(tail node) 한 노드의 바로 앞에 있는 노드는 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드는 다음 노드(successor node) 배열로 선형 리스트 만들기의 문제 쌓이는 데이터의 크기를 미리 알아야 함 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 함 포인터로 연결 리스트 만들기 노드를 구현한 구조체 Node typedef struct __node { Member data; struct __node *next; } Nod..

지역 변수(local variable) 중괄호 내부, 함수의 매개변수에서 사용되는 변수 함수 안에서만 접근 가능하며, 벗어나면 사라짐 초기화하지 않으면 쓰레기값이 저장됨 Stack 영역에 메모리 할당됨 전역 변수(global variable) 중괄호 외부에서 선언되는 변수 어느 지역에서든 참조해서 사용 가능 프로그램이 시작될 때 생성 및 초기화되고 끝날 때 사라짐 반드시 상수(변수x)로 초기화해야 하며 초기화하지 않으면 0임 Data 영역에 메모리 할당 정적 변수(static variable) static이 붙여서 선언된 변수 전역 변수와 동일하지만 차이점은 초기화가 딱 한 번만 진행됨 함수의 매개 변수로 사용할 수 없음 Data 영역에 메모리 할당 정적 지역변수(static local variable)..

Boyer-Moore법 -> KMP법보다 효율이 더 좋음 ! 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정함 건너뛰기 표 패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같이 결정: 1. 패턴에 들어 있지 않은 문자를 만난 경우: n 2. 패턴에 들어 있는 문자를 만난 경우 2-1. 해당 문자가 패턴 안에 중복되지 않으면서 마지막에 있는 경우: n 2-2. 그 외의 패턴의 마지막 문자의 인덱스가 k일 때: n - k - 1 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산해야 하므로 건너뛰기 표의 요소 개수는 UCHAR_MAX + 1 (UCHAR_MAX: 표현할 수 있는 문자의 개수로 에 객체 형식 매크로로 정의되어 있..

KMP법 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 표로 만들어 저장 (건너뛰기 표, skip table) -> 패턴 내에서 중복되는 문자의 나열을 먼저 찾아야 함. 패턴과 패턴을 한 칸씩 비교 ! 연속해서 겹치는 횟수를 기록 예를 들어 패턴이 "ABCABD"일 때, 4번째에서 처음 겹치고(1) 5번째에서 연속으로 겹친다(2) 따라서 건너뛰기 표는 "- 0 0 1 2 0"가 된다. skip[idx]: idx번째 문자가 일치하지 않을 때 다시 되돌아가야 할 위치 ! KMP법으로 문자열 검색 #include int kmp_match(const char txt[], const c..