회고1. 그냥 같은 row끼리 Concat하면 되는데 Join을 해버렸다. 정신이 어떻게 된것 같다.그래서 미친듯이 많은 재귀를 돌리고 메모리가 터졌다..2. 비트셋을 이용해 본것은 처음 3. vector> 내 원소들간 중복제거를 연구해봐야 겠다.4. 프로그래머스에 전역 변수 선언을 하는것도 한번 참고해 보자.5. 이상한 반례 : 다음 테이블의 후보키는 전부 가능한거 아닌가? 근데 막상 풀었을때, 후보키는 1개 밖에 사용 못했다.학번이름전공학년"100""ryan""music""2" #include using namespace std;vector CandiKey;int ColNum = -1;int RowNum = -1;int solution(vector> relation) { int answer = ..

1). double 같은지 비교https://www.acmicpc.net/blog/view/37double 끼리 같은지 비교할때, abs(a - b) 이렇게 해야 한다.그런데 여기서 좀 충격인게 위 글을 보고 1e-9 (0.000000001) 의 오차를 가지게 했는데실제 실행시킬때 테케 통과가 안되는 문제가 있었다. 그래서 EPS를 1e-15 까지 더 줄이니 통과 했다.2). 풀이#include #define x first#define y secondusing namespace std;const double DOUBLE_OFFSET = 1e-15;bool comp(const pair& lhs, const pair& rhs) { if(abs(lhs.x - rhs.x) rhs.x;}vector sol..

정말 오래간만에 알고리즘 문제를 풀어봤다.PS 실력은 옜날과 비교할때는 저점이 되었지만 C++ 언어 자체는 김포프님 언매니지드 강의 듣고 나서 이해는 더 잘된듯. #include #include #include #include #include using namespace std;// hashSet == unorderd_map 사용 // UID 와 string 매핑 // 레퍼런스 변경void Change(unordered_map &ud, const string& uid, const string& repN) { // TODO user에 있는 string을 찾아서 교체, 레퍼런스 교체 ud[uid] = repN;}// UUID & Enter/Leave// UUID & 01010// UID..

FSM : 유한상태기계1. 목차DFANFANFA -> DFA 변환 알고리즘FSM 변환 알고리즘유니티 코드2. DFA1). 정의결정적 유한 오토마타 (Determinstic Finite Automata) 5개로 구성된 튜플이다.2. 특징next state가 단 하나로 결정됨ε (empty input)에 대한 전이가 없음2). 수식M=(Q,∑,∂,q0,F){M = (Q, ∑, ∂, q0, F)}M=(Q,∑,∂,q0,F)Q : set of state노드, 상태를 의미인풋으로 들어가는 상태는 원소 하나일수도, 원소의 집합일 수 있다.∑ : set of symbols called input간선(화살표), 전이함수의 인풋 매개변수로 사용∂ : 전이 함수∂(상태, 인풋) -> 상태q0 : inital state초기 ..

해시 테이블 개요 접근 삭제 시간 복잡도 : O(1) 개빠르다 Collision : 동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것 해시 함수 인덱스 값을 설정해주는 함수 보통 나머지연산은 큰 소수로 이뤄지면 좋다. 단 등가교환이 있다 과유불급 좋은 해시 함수는 최대한 Collsion이 적어야한다. Collsion이 많아지면 O(1)에서 O(n)으로 가까워진다. 그런데 너무 심각하게 Collsion이 있다면 메모리를 너무 차지하게 된다. Collsion의 해결 개방 주소법 linear 하게 버킷을 탐색한다 Double hashing probing 하나의 해쉬 함수에서 충돌이 발생하면 2 차 해쉬 함수를 이용해 새로운 주소를 할당한다. 분리 연결법 동일버킷 : 연결 리스트를..

트리 트리의 구성 요소 ❗ 기본 트리의 구성 요소 노드 간선 노드와 노드를 연결하는선 서브 트리 트리를 구성하는 작은 트리 트리는 재귀적이다. ❗ 관점에 따른 노드 분류 👉 위치에 대한 관점 루트 노드 ■ 맨 꼭데기 노드 단말 노드 ■ 자식이 없는 노드 내부 노드 ■ 단말 노드 이외 노드 👉 상위, 하위 관점 부모 노드 ■ 자식을 가지고 있는노드 자식 노드 ■ 부모가 있는 노드 형제 노드 ■ 부모가 있고 Depth가 동일한 노드 트리의 분류 ❗ depth / level 트리의 깊이혹은 높이라 부른다 어떤 트리의 depth / level을 물어볼때 최대 depth를 말하면 된다. 가족관계 현재 노드 : i; 부모 : i/2; 왼쪽 : 2i; 오른쪽 : 2i + 1; 👉 이진 트리 노드 하나를 중심으로 2개..

이진 탐색 트리 구현 이진 탐색트리 구현은 다음 깃허브를 참고했습니다 https://gist.github.com/harish-r/a7df7ce576dda35c9660 Visual Studio 솔루션 구성 구현부 노드 - 헤더 : Node.h #pragma once class Node { friend class BinSearchTree; public: int data; Node* lch; Node* rch; }; 이진 탐색 트리 - 헤더 : BinSearchTree.h #pragma once #include "Node.h" class BinSearchTree { friend class Node; private: Node* mRoot; Node* mMakeEmpty(Node *_t); Node* mInser..

스택과 큐 스택 ❗ 스택의 특징 👉 자료구조 LIFO (후입선출) 👉 메모리에 올라간 구조 프로세스 메모리 구조 코데힙스 코드 영역 컴파일후 생성된 기계어 CPU가 기계 명령어를 가져올때 사용되는 영역 프로그램 종료후에도 남아있음 데이터 영역 전역변수 정적변수 컴파일후 할당됨 프로그램 종료후에 같이 삭제 힙 영역 동적할당된 메모리 영역 new delete, malloc free 컴파일중에 할당 프로그램 종료후에 같이 삭제 스택 영역 함수, 지역변수, 매개변수 스택 프레임이라고 함수의 호출 정보를 스택처럼 쌓도록 동작하는 구조 컴파일중에 할당 프로그램 종료후에 같이 삭제 👉 미로찾기 그래프탐색 DFS는 보통 재귀로 해결하기도 하지만 스택을 이용해서도 DFS를 진행할 수 있다. 코드는 다음과 같다 미로찾기 ..

미로찾기 스택큐 노트로 돌아가기 https://felipuss.tistory.com/entry/니앙팽이-자료구조-2-스택큐-노트?category=961476 1. stack을 이용한 DFS #include #include #include #include #include #include #define pr pair #define y first #define x second using namespace std; int arr[1010][1010] = {0, }; bool visit[1010][1010] = { false, }; pr MV[8] = { {0,-1},{1,-1},{1, 0},{1,1}, {0,1},{-1,1},{-1,0},{-1,-1} }; bool isEnter(pr _pos, int _N) ..

배열과 연결리스트 Quest ❗ 배열과 연결리스트의 차이 ___ 배열 연결리스트 형식 정적 동적 접근 random Access : O(1) Sequential Access : O(N) 삽입 맨앞 O(N) 맨뒤 O(1) 맨앞O(1) 맨뒤 O(N) 삭제 맨앞 O(N) 맨뒤 O(1) 맨앞O(1) 맨뒤 O(N) 연결리스트 1. 더미노드 ❗ 더미노드는 왜 쓰는건가? 연결리스트(더미노드 없음) 구현 - 2. 원형 연결리스트 ❗ 작동방식 👉 구성은? list->tail 원형리스트의 마지막임 list->tail->next (내지는 head) 원형리스트의 시작임 👉 복잡도는? ___ 연결리스트 형식 동적 접근 Sequential Access : 맨앞 : O(1) 맨뒤 : O(N) 삽입 맨뒤 O(1) 삭제 맨앞O(1) 원..