알고리즘/프로그래머스71 [프로그래머스] 네트워크 c++ 풀이 간단한 dfs문제였다 노드는 좌표가 아니라 번호로 주어졌고 연결 여부는 2차원 벡터로 주어졌다. 인접행렬말 인접리스트를 이용해 풀었다. 방문하지 않았던 노드라면 그 노드부터 dfs를 수행한다. 노드를 방문하면 chk에 방문여부를 저장해준다. dfs를 수행한 횟수가 네트위크 개수이므로 답으로 반환한다. #include #include #include using namespace std; vectornode[201]; vectorchk(201,0); void dfs(int idx){ chk[idx]=true; for(int i=0;i 2024. 2. 7. [프로그래머스] 도둑질 c++ 풀이 첫번째 집과 마지막 집에 옆에 있으므로 마지막 집을 털게되면 첫번째 집을 털지 못한다. 처음부터 첫번째 집을 터는 경우와 털지 않는 경우로 나누어서 구해야한다. dp[i] 는 i까지 터는 경우의 최댓값이다. 2번 전 집을 털고 i번째 집을 터는 경우와 털지 않고 i-1번째까지의 최댓값을 가져오는 경우가 있다. #include #include #include using namespace std; vectordp1; vectordp2; int solution(vector money) { int answer = 0; dp1.resize(money.size()); dp2.resize(money.size()); int money_size = money.size(); //첫번째 집을 터는 경우 dp1[0] =.. 2024. 2. 6. [프로그래머스] 사칙연산 c++ 풀이 매번 괄호 안을 연산해주면 시간이 많이 걸리기 때문에 괄호안의 결과를 저장해서 계산해주었다. dp를 이용해 풀었다. 연산이 더하기냐 뺴냐에 따라 최댓값을 만드는 방법이 달라진다. +일때 : (최댓값)+(최댓값) -일때 :(최솟값)-(최댓값) 그러므로 괄호안의 연산의 최솟값도 dp를 이용해 구해놓아야한다. #include #include #include #include using namespace std; vectordp_max(202,vector(202,-10000000)); vectordp_min(202,vector(202,10000000)); vector arr; int calculate(int start, int end,int isMax){ if(isMax & (dp_max[start][end.. 2024. 2. 5. [프로그래머스] 등굣길 c++ 풀이 (1,1)에서 (m,n)까지 가는 최단 경로의 개수를 구해야한다. 중간에 물웅덩이를 지날 수 없다. m이 x축이고 n이 y축이다. puddles도 (x축 좌표, y축 좌표)이다. 예시로 준 물웅덩이가 2,2라 헷갈릴 수 있다. 1. 물웅덩이의 값을-1로 설정한다. 2. i,j까지 오는 경우의 수는 (i-1,j)와 (i,j-1)에서 오는 경우의 수뿐이다 (오른쪽과 아래쪽으로 밖에 못 움직인다.) 3.두 방향에 각각 물웅덩이가 있는지 검사하고 없다면 경우의 수를 더한다. 4.물웅덩이는 지나갈 수 없으므로 더하지 않고 continue해준다. #include #include #include using namespace std; vectordp(101,vector(101,0)); int solution(in.. 2024. 2. 2. 이전 1 2 3 4 5 ··· 18 다음