With The Lights Out

문제  시행 착오없음  해결 방법순회하며 1을 찾고, 1을 찾은 위치에서 DFS 를 이용해 상하, 좌우에 1이 없을 때까지 탐색했다. 아래는 문제풀이 전에 직접  VS 에 작성한 방법이다.DP 를 풀듯 차근차근 생각하는 것이 도움이 많이 되는 것 같다.생각해 본 해결방법  1. 상하, 좌우 이렇게 두 경우만 집이 붙어있는 경우이다.2. DFS / BFS 중 어느거라도 사용한다.3. 몇 개가 붙어있는지 세고 오름차순으로 출력한다.  #define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;vector v;int N;int map[26][26];bool visited[26][26] = { false };int cnt = 0;v..

문제   시행 착오인접 정점을 어떻게 해야 번갈아 가며 색으로 칠할 수 있는 지 고민했다.   해결 방법삼항연산자로 간편하게 인접 정점에 부모 노드와 다른 색을 칠할 수 있었다.. 예시 :void DFS(int node, int c) { color[node] = c; visited[node] = true; for (auto v : g[node]) { if (color[v] == 0) { // 방문 안 한 경우 DFS(v, c == RED ? BLUE : RED); } }}     DFS 사용해서 해결#include #include #include #include #define RED 1#define BLUE 2using namespace ..

구조체 하나의 데이터 타입이 아니라, 다양한 데이터타입을 묶어서 새로운 데이터타입을 필요로 할 때 사용된다. struct Player{    string name;    float moveSpeed;    double attackVaule;    int hp;    bool isDead;    name, moveSpeed, attackValue, hp, isDead}; C++ 에서 구조체와 클래스의 차이점은  구조체는 접근 지정자가 public: 클래스는 private: 이다. 위 사항 말고는 큰 차이점이 없다. 함수 코드를 특정 기능 단위로 묶어 놓은 것. 함수의 유용성1) 코드 자체가 매우 간략해질 수 있다.2) 함수명, 매개변수명=기능을 나타내기 때문에 코드 가독성 / 유지 보수가 편해진다.3) 코..

문제 시행 착오 연결 요소  연결 요소란 간단히 말해서 간선으로 이어진 정점들의 한 뭉탱이를 말한다.1-3-5   2-4 이렇게 연결 된 정점들이 있다면 연결 요소는 두 개인 것.   해결 방법 dfs 혹은 bfs 를 시행했을 때 한 번의 시행으로 전부 순회가 안 된다면 연결 요소가 두개 이상 있는 것이다. 두해당 알고리즘 시행 횟수만큼이 연결 요소의 개수가 된다. #include #include #include #include using namespace std;int N, M, V;vector g[1001];bool visited[1001] = { false };queue q;int cnt = 0;void dfs(int node){ visited[node] = true; for (a..

메모리주소를 값으로 가져야 하는 이유? 변수의 접근이나 제어가 불가능한 영역에서 해당 변수에 접근해서 값을 제어하고 싶을 때동적할당(new)을 통해서 런타임(실행시간) 때 메모리에 할당되는 변수를 제어하기 위해서 동적할당(new 키워드, delete 키워드)1) 개념 : 힙메모리 자료를 저장할 공간을 할당받는 것 힙메모리와 스택메모리스택 : 특정 코드 구문 내에서 {...} 임시로 할당되는 메모리영역힙 : 프로그래머가 자유롭게 할당하고 해제할 수 있는 메모리 영역 데이터의 크기가 일정하지 않은 형태의 자료형서로 다른 코드 구문 { } { } 사이의 변수 값을 제어하고 싶을 때 참조 : 포인터가 가리키고 있는ㄷ(담고 있다) 메모리 주소의 값에 접근하는 것   1. 다음 보기 중에서 알맞지 않게 짝지어진 것..

문제  시행 착오  해결 방법 벡터를 이용해 그래프를 구현하고, DFS 는 재귀호출을 통해, BFS 는 큐를 이용해 구현했다.정점 순서대로 순회 하려면 입력 받은 뒤 sort를 해주어야 한다.   #include #include #include #include using namespace std;int N, M, V;vector g[1001];bool visited[10001] = { false };queue q;vector v_bfs;vector v_dfs;void dfs(int node) { visited[node] = true; v_dfs.push_back(node); for (int nextnode : g[node]) { if (!visited[nextnode]..

#include #include using namespace std;int main(){ srand(time(NULL)); int escape_x = rand() % (9 - 0 + 1) + 0; int escape_y = rand() % (9 - 0 + 1) + 0; bool escaped = false; char m[10][10]; for (int i = 0; i > input; switch (input) { case 'w': m[curY][curX] = '#'; curY -= 1; m[curY][curX] = 'O'; break; case 'a': m[curY][curX] = '#'; curX -= 1; m[curY][curX] = 'O'; break; ..

문제   시행 착오  그래프가 기억이 안 나서 복습했다.백트래킹, 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..