20대 개발자의 여행

-문제-https://www.acmicpc.net/problem/13565 -문제 접근-위 문제에서의 조건으로 상하좌우로 인접한 격자들에 흰색은 통과 가능하고 검은색은 차단되어 접근이 불가능하다.격자의 위쪽을 바깥쪽으로 정의를 하였기에 맨위에 1열에서 시작을 하여서 맨 끝 열에 도달 할 수 있는지 아닌지를 판단하는 문제임을 알 수 있다. 여기서 우선 상하좌우로 인접한 격자들을 확인하기 위해서const int dx[4] = {-1, 1, 0, 0};const int dy[4] = {0, 0, -1, 1};를 써야 겠다는 생각을 할 수 있다. vector> adj(M, vector(N)); vector> vis(M, vector(N));벡터를 2차원으로 생성해야 함을 알 수 있다. queue> q;q.pu..

-문제-https://www.acmicpc.net/problem/5567 -문제 접근-위 문제는 친구의 친구일 경우까지만 친구로 카운트를 한다고 되어있다. 그 말은 즉 시작점으로 부터 depth가 2까지만 친구로써 카운트 하겠다는 뜻이다. 그렇다면 이 depth를 2까지 어떻게 구별하고 카운트를 할것인가? 를 우리는 생각해야된다. 위 문제에서 main은 딱히 다른 bfs의 문제들과 별 차이점이 없이 구성하면 될 거 같다. 그렇다면 bfs를 건들여야 하는데 일반적인 bfs는 queue를 하나로 둔다.하지만 이 문제에서는 queue를 pair로 둬서 노드, dapth 이렇게 두 개를 처리해야 함을 알 수 있다.그렇게 하면 dapth가 2 이상 일 때는 넘기고 그 전까지의 count를 해주면 문제가 요구하..

-문제-https://www.acmicpc.net/problem/18352 -코드-#include #include #include #include using namespace std;void bfs(const vector>& adj, int s, vector& dist){ queue q; q.push(s); dist[s] = 0; while(!q.empty()){ int cur = q.front(); q.pop(); for(auto nxt: adj[cur]){ if(dist[nxt] != -1) continue; dist[nxt] = dist[cur..

-문제- -문제 접근-무방향 그래프에서 첫 줄에 정점의 개수 N 과 간선의 개수 M을 받고 두번째 줄 부터 간선의 개수 만큼 간선의 양 끝점 u,v를 받으며 연결 요소의 개수를 구하는 문제이다. 연결 요소의 개수라는 말이 무슨 말인가 싶을 수 있는데 한마디로 서로 연결이 되어있지 않은 개별의 그래프의 개수를 의미한다고 이해하면 좋을 것 같다. -문제 풀이- 변수노드와 간선의 관계를 저장하기위해 vector를 사용하여 adj를 선언하고 방문여부를 확인 하여야 하므로 vis를 선언한다.(크기는 문제의 조건에 맞게) main입력값 N과 M을 받아주어야 하며 그 다음 줄 부터 간선의 끝점 u, v를 받아서 연결을 해줘야 되므로 vector adj에 push_back을 하여 간선 처리를 해준다.int cnt ..

-문제- -문제 접근-위 문제는 트리의 루트를 1로 정하고 각 노드의 부모를 구하는 프로그램을 작성하는 문제이다.입력값으로는 노드의 개수 N과 N-1개의 간선인 연결된 두 정점을 입력한다. main()우선 메인함수에서는 입력값을 받을 애들부터 작성을 해준다.N 값과 그 다음 줄을 받기 위해 간선의 수가 N-1번 나올 것이기에 int형 e를 선언하여 int e = n-1로 잡고 while(e--)을 하여서 간선의 두 정점을 다 받을 수 있도록 하고 정점의 변수 u, v를 선언하고 받은 후 전체 노드를 받을 vector에 push_back을 사용하여 양방향으로 간선을 받아준다. 2이상의 노드의 부모를 출력하도록 for문을 만들어 주면 끝이다. 전역변수전역변수로 뭐가 필요할지 생각해보면 전체의 노드를 받을 ..

-문제- -문제 접근- 이 문제는 2차원 보드에서 1로 표시된 영역을 찾고, 이들로 이루어진 연결된 영역의 개수와 그 중에서 가장 큰 영역의크기를 구하는 문제 입니다.  입력:n x m 크기의 격자가 주어지며, 각 칸은 0 또는 1의 값을 가집니다.문제 접근:탐색 과정에서 같은 칸을 여러 번 방문하지 않도록 하기 위해 방문 여부를 체크할 방문 배열 필요순회격자의 각 칸을 순회하면서, 만약 해당 칸이 1이고 아직 방문하지 않았다면, 새로운 영역의 시작점으로 간주새로운 영역이 발견될 때마다 영역의 개수(num)를 증가영역 탐색 (BFS):BFS(너비 우선 탐색)를 이용하여 해당 영역의 연결된 모든 1들을 방문시작점을 큐에 넣고, 큐가 빌 때까지 반복하며 4방향(상, 하, 좌, 우)으로 인접한 칸들을 검사범위..

-문제--문제 접근-위 문제의 요구사항을 크게 볼 때 조합 생성과 조건 검사 두 가지로 볼 수 있습니다.1. 조합 생성각 암호는 주어진 C개의 문자 중에서 L개를 선택한 조합을 말합니다.2. 조건 검사조건:모음: 최소 1개 이상자음: 최소 2개 이상오름차순 정렬모든 가능한 조합을 생성하고 문제의 조건을 검사하여 출력을 해야되는데 이러한 경우에 백트래킹을 사용하여 구현할 수 있습니다. 3. 백트래킹재귀 함수를 이용하여 인덱스 순서대로 문자를 선택하면서 조합을 구성하고 기저 조건: 선택한 문자의 개수가 L개 가 되었을 때 모음과 자음을 확인하며 조건 검사를 수행해야 합니다.조건 검사 수행 후 만족했다면 문제에서 찾고자 한 가능성 있는 암호를 출력 할 수 있습니다. -전체 코드-#include #include..

-문제-   -문제 접근- 1. 문제 조건위 문제는 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다.퀸이 놓여진 행과 열 그리고 대각선 방향에는 아무것도 놓여있으면 안되는 조건을 가지고 있습니다.2. 문제 접근문제를 처음 봤을 때는 NxN의 체스판이라 당연히 2차원 배열을 생각해보게 되지만 문제의 조건에 조금 더 생각해보면 "각 행에 하나의 퀸만 놓을 수 있다" 라는 조건이 있으므로 각 행에 대해 열 번호만 저장하면 체스판의 모든 좌표를 표현 할 수 있습니다.  예시) n = 3 일때 board[0] =1 하면 0번째 행, 1번째 열에 퀸이 있다를 의미하게 됩니다. 문제 조건 적용을 하면 같은 열에 퀸이 위치 할 수 없기 때문에 board[0] = 0 이면  b..

-문제- -문제 접근-1. 문제 이해 입력 조건:여러 테스트 케이스가 주어집니다.각 테스트 케이스의 첫 번째 숫자 k는 집합 S에 포함된 원소의 개수입니다. (6 k 그 다음 k개의 숫자가 주어지며, 이 숫자들은 오름차순으로 정렬되어 있습니다.입력의 마지막 줄에는 0이 주어지며, 이 경우 테스트 케이스가 종료됨을 의미합니다.출력 조건:각 테스트 케이스마다 집합 S에서 6개를 선택하는 모든 조합을 사전 순으로 출력합니다.각 조합은 한 줄에 출력되며, 조합 사이에는 빈 줄을 하나 출력해야 합니다. 위 문제는 주어진 집합 S에서 6개의 숫자를 골라 모든 조합을 구하는 문제입니다. 2. 접근 방법조합 생성순서에 상관없이 주어진 집합에서 특정 개수의 원소를 선택하는 경우의 수BacktrackingRecursive..

-문제- -문제 접근-1부터 N까지의 숫자 사이에 세 가지 기호(공백, '+', '-')를 삽입하여 생성된 수식의 결과가 0이 되는 모든 경우를 찾아야 하는 문제입니다. 1. 백트래킹백트래킹(재귀) 기법을 사용하여 1부터 N까지 숫자 사이의 (N-1)개 위치마다 가능한 3가지 기호(공백, '+', '-')를 모두 삽입하는 경우의 수를 생성합니다.재귀 호출을 통해 한 단계씩 숫자를 추가하면서 완성된 수식을 만들고, 최종 숫자(N)에 도달하면 해당 수식을 평가합니다.2. evaluate 함수생성된 수식은 공백, '+' 및 '-'를 포함합니다.공백 처리: 공백은 인접한 숫자를 연결하여 하나의 수로 만들어야 합니다. ("1 2"는 12)연산 처리: '+'와 '-'를 만날 때마다, 지금까지 이어진 숫자를 정수로 ..