LiDARism

C++를 공부하는 중 잊을 때마다 다시 보러오기 위해 적는 시리즈이다. 다시 보러오는 일이 적었으면 좋겠다. #include #include int main(void){ std::string input; //using namespace std; 를 안하면 표준라이브러리 사용할 때 std::string 해줘야함. std::cin >> input; //문자열 입력. >>는 공백문자(스페이스, 엔터, 탭)을 기준으로 입력을 받는다. 한줄을 전체로 입력받고 싶으면 getline을 이용해야한다. std::cout input; //문자열 입력. >>는 공백문자(스페이스, 엔터, 탭)을 기준으로 입력을 받는다. 따라서 >> 다음에는 한칸 띄어주어야한다. cout

뭔가 이름이 멋있는 알고리즘이다. O(N + M)의 시간 복잡도 특정한 상황에서 KMP 알고리즘보다 매우 느리게 동작한다고 한다. 사실 그럴만도 한 것이 일단 hash함수를 써야하고, hash값이 같은 부분이 많으면 check하는 함수를 써야하니... 그래도 내 머리보단 빠르지 않을까? 설명은 이 분의 블로그가 좋겠다. blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240679247&redirect=Dlog&widgetTypeCall=true&directAccess=false #include #include char * parent = "acabacdabac"; char * pattern = "abacdab"; // 같은 문장인지 확인하는 함수 void che..

1. 같은 자료형은 붙여서 선언하는 것이 메모리에 효율적이다. int a; int b; int c; long d; long e; long f; 2. UNION 비트필드의 구성 방법 공용체는 멤버 중에서 가장 큰 자료형의 공간을 공유한다. 이런 특성을 이용해서 가장 큰 자료형을 정의하고 이를 분할하는 여러 멤버들로 구성해서 bitfield를 만들 수 있다. 참고 : dojang.io/mod/page/view.php?id=453 주로 로봇의 작동 모드를 제어할 때 아래와 같이 작성한다고 한다. typedef union package_t{ struct{ uint32_t actionone:1; uint32_t actiontwo:1; uint32_t actionthree:1; uint32_t reserved:26..

O(N + M)의 시간복잡도의 알고리즘이다. matching 전에 접두사와 접미사가 일치하는 최대길이를 기록하는 table을 만들어 이용한다. 알고리즘이 다소 복잡하게 느껴질 수 있으니 설명을 찾아보는 게 좋을 듯하다. 그런데 알고리즘에 대한 설명은 나보다 이 사람이 더 잘하지 않을까? bowbowbow.tistory.com/6 #include #include #include char * parent = "acabacdabac"; char * pattern = "abacdab"; int * makeTable(char * pattern){ int patternSize = strlen(pattern); int * table = (int *)malloc(sizeof(int) * patternSize); for..

컴퓨터가 2의 보수를 이용하는 것을 이용할 것이다...? 2의 보수, 1의 보수에 관한 좋은 설명이 있는 블로그 링크 ndb796.tistory.com/tag/2%EC%9D%98%EB%B3%B4%EC%88%98 오타쳐서 런타임 에러가 났었고 찾아서 해결했다.. 아래는 예시 코드다. #include #define NUMBER 7 int tree[NUMBER]; int sum(int i){ int res = 0; while (i > 0){ res += tree[i]; i -= (i & -i); // i = (i & -i); // 오타쳤음. 이 경우 계속 i = 1이라서 영원히 안끝난다... 오버플로우까지 } return res; } void update(int i, int dif){ //i index에 di..

구간 합을 구하는데 좋은 알고리즘 중 하나이다. O(N)의 시간복잡도. 이마저도 비효율적이라 생각하는 알고리즘에 미친자들... 결국 트리를 이용해서 시간복잡도를 O(logN)으로 축소시킨다. #include #define NUMBER 7 // data의 개수 int a[] = {7,1,9,5,6,4,1}; int tree[4*NUMBER]; // 4를 곱해서 모든 범위를 커버한다...라고 하는데 그냥 높이를 곱한 것. // start : 시작하는 인덱스, end : 끝나는 인덱스 // node : 사실 그냥 1이 들어간다...만은 원래는 특정 노드에 특정 값이 들어가게 하기 위해 따로 파라미터로 내놓는다. 즉, 재귀함수로 사용하기 위해 존재하는 파라미터. main에서의 용도는 root node를 지정해주..

동작 원리가 프림 알고리즘과 흡사. 아래 설명 코드에선 main 함수에서 차이가 난다. 프림 알고리즘과의 차이점은 간선의 '가중치'가 아닌 간선의 '이동거리'를 중심으로 판단한다는 점이다. 즉 기존 이동했던 노드를 거쳐간다는 가정하에 '이동거리'를 계산하고 이를 통해 Table을 갱신한다. 기존의 테이블을 매번 새로 갱신하는 특징이 있다. 우선순위 큐를 이용해서 구현한다. 프림 알고리즘과 같이 시간복잡도 O(ElogV) #include #include #include #define NODE_MAX 1001 #define EDGE_MAX 600001 // 양방향 간선이므로 300000개를 고려 // Node가 Edge를 참조, priorityQueue가 Edge의 cost를 중심으로 최소값이 pop되게 구..

신장 트리 : 모든 정점을 포함하는 그래프 최소신장트리 : 스패닝 트리 중 간선 가중치 합이 가장 작은 트리 과정에 대해 간략히 설명하는 글을 인용하면... 1) 그래프에서 정점 하나를 선택하여 트리 T에 포함시킵니다. 2) T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가중치가 가장 작은 간선을 찾습니다. 3) 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킵니다. 4) 모든 노드가 포함될 때까지 2)와 3) 과정을 반복합니다. 중요한 것은 간선을 중심으로 노드를 우선순위 큐에 담아 처리한다는 점이다. 그리고 이때 가중치를 Cost라고 표현한다. 프림 알고리즘은 시간복잡도가 O(ElogV)이다. #include #include #incldue #define NODE_M..

체이닝(chaning) 체이닝은 연결리스트를 통해 특정한 키를 가지는 항목들을 연결해서 저장한다. 같은 key에 대한 중복을 허용 체이닝을 이용한 해시맵 구현 코드 예시 #include #include #include #include #define TABLE_SIZE 10007 #define INPUT_SIZE 5000 typedef struct{ int id; char name[20]; } Student; //하나의 key에 여러 data가 들어갈 수 있게 해주는 구조체다. Student * 의 주소를 담는 구조체 typedef struct{ Student * data; struct Bucket * next; } Bucket; //해시테이블 초기화 void init(Student ** hashTable..

해시맵 특징 - 많은메모리 소모, 빠른 데이터 처리 특정값을 찾을 때에는 key로 접근한다. 그 key를 index라고 한다. key 중복을 collision이라고 한다. - hashing은 division method을 주로 이용. 나머지를 key로 이용한다는 것. 테이블의 크기(나누기 크기)는 prime number로 설정한다. 충돌 처리 1. 선형조사법,이차조사법 : 충돌 발생항목을 테이블의 다른 위치에 저장한다. 2. 체이닝 : 해시 테이블의 하나의 버킷에 여러개의 항목을 저장한다. 선형 조사법 예시 코드 // 선형조사법 #include #include #include #include #define TABLE_SIZE 10007 #define INPUT_SIZE 5000 typedef struct..