알고리즘119 [프로그래머스] 게임 맵 최단거리 c++ 풀이 bfs를 이용해 최단거리를 구하는 문제였다. bfs는 근접 노드를 다 방문하고 depth를 +1 해서 방문하기 때문에 근접 a와 인근한 b,c,d .. 노드들은 depth가 같고 즉 거리가 같다. 그렇기 때문에 b,c,d를 방문한 순서와 상관없이 b,c,d까지의 거리가 같다. ( ex) c,d,b순서대로 방문해도) 한 단계에서 갈 수 있는 모든 노드들을 방문하기 때문에 한 번 방문한 노드의 거리는 노드까지의 최단 경로가 된다. 효율성까지 맞기 위해서는이미 거리를 갱신한 노드는 또 거리를 갱신시켜주면 안된다. b에서 탐색을 해서 d의 최단거리를 3으로 갱신시켜주었다. c에서 탐색을 할때도 d의 최단거리는 3이 된다. 하지만 이미 갱신을 시켜주었기 때문에 불필요한 작업이 된다. 이는 34번째 줄의 cn.. 2024. 2. 7. [프로그래머스] 네트워크 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. 이전 1 2 3 4 5 ··· 30 다음
