With The Lights Out

문제   시행 착오  그래프가 기억이 안 나서 복습했다.백트래킹, dfs 는 잘 하지만 그래프와 합쳐지니 연상이 잘 안 되었다. 항상 천천히 알고리즘을 생각해내는 연습이 필요해 보인다. (무작정 아는 방식으로 구현 X 머릿속에서 구체화) 해결 방법 그래프를 선언하고, 각 그래프마다 관계 또한 최대 2000개까지 들어올 수 있다.사실상 2차원 배열 형태를 벡터를 이용해 표현한 것과 비슷한데,  시작 노드를 정한다.시작 노드에 저장되어있는 관계로 접근한다.노드의 관계를 깊이우선탐색 하면서 cnt 가 4가 되는 노드순서를 찾는다.끝   #include #include #include using namespace std;int N, M;vector g[2000];bool visited[2000] = { fals..

문제    시행 착오 비트마스크 알고리즘을 사용해 문제 풀이가 아직 익숙치 않아 풀이가 오래 걸렸다.무에서 유를 창조할 수는 없기에 gpt에게 아이디어만 제공받아 풀이를 시작했다.  해결 방법 문제에서의 힌트는 수는 무조건 행렬에서 각각 성분의 크기가 커지는 방향으로 진행된다는 점이다.따라서 수는 오른쪽, 혹은 아래쪽 으로만 진행하게 된다. 경우의 수가 2개라는 것은 결국 이진으로 표현이 가능함을 알 수 있었다. 배열 3개를 사용했다.입력받은 수를 저장할 arr비트마스크를 통한 경우의수를 저장할 binaryarr방문 여부를 나타내는 visited 방문되어있지 않은 이진배열 위치에서 해당 위치의 값이 아닌 값 (연속되지 않을 때까지, 방문 되지 않은 곳으로) 까지 순회하면서 수를 만들고 더해준 다음 최댓값..

변수는 데이터를 저장하는 공간변수에게는 아래 네 가지 속성이 있다.이름값데이터 타입(메모리 크기)메모리 주소(포인터) 변수의 이름규칙C++ 에서 사용하는 키워드들은 이름으로 사용할 수 없다.알파벳, 숫자, _로만 구성할 수 있다.숫자로 시작할 수 없다.대/소문자를 구분한다.이름 사이에 띄어쓰기를 넣을 수 없다.(컴파일러는 띄어쓰기를 기준으로 인식하므로) 데이터 타입 : 변수가 가지는 데이터의 형태, '자료형'할당받는 메모리의 크기가 결정된다.타입의 종류 : 정수형, 실수형, 문자형, 문자열, 불 대수 값 연산자 : 데이터를 가공하는 모든 명령에 필요한 것들어떤 종류의 연산자들이 있는가?우선순위 : 어던 순서로 연산이 되는가?결합순서 : 좌측부터 연산하는 연산자, 우측부터 연산하는 연산자 boolalpha..

문제   시행 착오 비트마스크 사용법을 몰라 인터넷에 검색해 이해했다. 비트 연산을 통해 백트래킹 사용을 하거나 큰 크기의 배열을 선언할 필요 없이 간편하게 해결할 수 있었다. 비트마스크는 아래 글을 읽고 이해했다. https://velog.io/@alkwen0996/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC 컴퓨터는 내부적으로 모든 자료를 이진수(비트)로 처리한다. 이런 컴퓨터의 연산방식을 이용한, 정수의 이진수 표현을 활용하여 문제를 해결하는 기법을 말한다. 비트(Bit)란? 비" data-og-host="velog.io" data-og-source-url="https://velog.io/@alk..

프로그래밍 언어란? 기계어와 사람이 쓰는 언어 중간에 있는 언어로 기계어를 사람이 인식할 수 있게, 사람의 언어를 기계가 인식할 수 있게 바꿔주는 것이다. 컴파일러가 해당 작업을 수행하며 이로 인해 사람이 프로그래밍 언어로 코딩을 할 수 있게 된다.  main 함수는 하나만 존재한다. 이때 Main, main, maiN 등 이런 함수 이름들은 다 다른 것으로 컴파일러가 인식한다. include 문을 작성할 때 는 내장되어 있는 라이브러리를 포함할 때, "" 는 내가 직접 만든 라이브러리 파일을 포함할 대 사용한다.그리고 include 문은 cpp 파일의 적어도 main 위인 상단에 위치해야 한다. #include 에서 iostream 은 표준 입출력 스트림을 의미한다.(input ouput stream)

시간복잡도에 유의하여 풀이해야 한다. 인덱스 배열을 만들어 해결했다. #include using namespace std;int M;int S[22];int main() { cin.tie(NULL); ios::sync_with_stdio(false); cin >> M; string inputoper; int input; for (int i = 0; i > inputoper; if (inputoper == "add") { cin >> input; if (!S[input]) S[input] = 1; } else if (inputoper == "remove") { ..

백트래킹을 이용해 푸는 문제. 늘상 하던 백트래킹 말고 좋아보이는 방법을 하나 발견할 수 있었는데, 처음에는 N^2 시간복잡도로 풀이하려 했었다. 그 대신 Sum 배열을 선언한 후 합을 미리 구해 놓는 방식이다. 이를 통해 시간복잡도를 획기적으로 줄일 수 있다.원하는 범위(-10 ~ 10) 까지에서 원하는 Depth 까지 순열을 구한다. (1, 1), (2,2) (3,3)  ----  이렇게 i == j 일 때는 무조건 자기 자신을 검사하면 되므로 if ((sign[depth][depth] == '+' && i = 0) || (sign[depth][depth] == '0' && i != 0)) { continue;} 이렇게 복잡도를 줄일 수 있다. 그리고 recur() 함수로 재귀 호출을 하기..

재귀, 백트래킹 을 이용하여 풀이했다.next_permutation을 사용하면 더 빨리 풀 수 있을 것 같다. 시간 복잡도가 다르기 때문에. 범위는 항상 조심하자.  #include #include #include #include using namespace std;int k[12];long long MinNum = 9999999999;long long MaxNum = -1;vector PermuVec;int visited[10] = { false };int N;bool checkCondition(vector inputVec){ for (int i = 0; i PermuVec[i+1]) { return false; } if (k[i] ==..

벡터 (Vector)크기와 방향을 가진 양을 나타내는 수학적 개념스칼라(Scalar)크기만을 가지고 방향이 없는 양을 의미벡터와 반대되는 개념으로 단순히 크기만을 가지고 있다.벡터의 정규화해당 벡터의 크기를 1로 만들어주는 과정벡터의 크기가 1이 되면 방향은 유지한 채 크기를 표준화 할 수 있다방향 벡터, 단위 벡터라고도 불린다.게임 개발에서 벡터는 다양한 용도로 사용되는데, 주로 위치, 방향, 속도 등을 나타내기 위해 사용됩니다.힘의 크기 (Magnitude)힘의 방향 (Direction) 벡터의 내적A⊙B = |A||B| Cosθθ 는 A와 B 벡터의 사이각이다.두 단위 벡터가 평행하면 절대값은 1이다. (같은 방향이거나, 반대 방향)  두 벡터 사이각은 내적공식을 통해 구할 수 있다. 1. 시야 판..

쿼드 트리(Quad Tree)트리의 자식 노드가 4개인 트리를 의미한다.공간을 재귀적인 호출로 4개의 자식 노드로 분할하는 방법게임에서는 일반적으로 지형 정보를 저장하는 데 사용된다.컬링을 위한 지형 검색에 쿼드 트리를 사용한다. (컬링 : 렌더링에 필요하지 않은 오브젝트들을 추려 내는 것)-> 쿼드 트리를 이용하면 필요 없는 데이터를 큰 덩어리 단위로 버릴 수 있게 되므로 거대한 지형을 빠르게 검색할 수 있기 때문이다.   FSM(Finite State Machine)유한 상태 머신이라고도 한다.유한 상태 머신은 자신이 취할 수 있는 유한한 갯수의 상태들을 가진다.그리고 그 중에서 반드시 하나의 상태만 취한다. (상태 중복을 피할 수 있다.)현재 상태는 특정 조건이 되면 다른 상태로 변할 수 있다.유한..