알고리즘119 [프로그래머스] 등굣길 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. [프로그래머스] N으로 표현 c++ 풀이 dp를 이용해 풀었다. 임의의 숫자 i에 대해서 N으로만 표현하는 최소 횟수를 구해야하는 문제이다. 사칙연산을 할 수 있기때문에 i에 대해 +,-,*,/를 해주어서 최소횟수를 갱신시켜주었다. dp 배열의 초기화는 N이 1일때는 최소 N번으로 표현할 수 있고 (1+1+1...) N이 1보다 클 때는 N*2번으로 표현할 수 있다. (2/2 + 2/2 + .. ) 또한 N으로만 이루어져있는 숫자들은 따로 초기화를 해주었다. N=5, dp[5]=1 ,dp[55]=2 , dp[555] =3 #include #include #include #include #include using namespace std; vector dp; int solution(int N, int number) { int answer =.. 2024. 2. 1. [프로그래머스] 단속 카메라 c++ 처음에는 진입지점을 기준으로 오름차순으로 정렬해서 카메라가 진출지점이 있다고 가정하고 다음 경로의 진입지점과 비교했다. 그리고 다음 카메라는 다음 경로의 진출지점에 설치했다. 이렇게 하면 한 경로에 여러 경로가 포함될 경우 (ex) [0,10] ,[-1,3].[5,7]) 카메라가 3다음에 10으로 가게 된다. ->경로를 진출시점을 기준으로 오름차순으로 정렬해줘야한다. 풀이 1. 경로를 진출시점으로 오름차순 정렬한다. 진출시점이 같다면 진입시점이 더 빠른 순으로 정렬한다. 2. 맨 앞의 경로부터 탐색한다. 카메라는 진출시점에 설치한다. 3. 다음 경로의 진입시점이 카메라의 위치보다 크다면 새로운 카메라를 설치한다. 4. 이미 진출 시점으로 오름차순 정렬을 해주었기 때문에 진입시점과 카메라의 위치만 비교해주.. 2024. 1. 31. [프로그래머스] 섬 연결하기 c++ 풀이 크루스칼 알고리즘을 이용해 풀었다. 비용이 적게드는 순서대로 연결을 한다. 연결을 할때 circle이 생기는지 확인하고 생기지 않는다면 연결한다. 루트노드를 갱신시켜줄때 일반적으로 작은 노드를 루트노드로갱신시켜준다고한다. (거꾸로 해도 되고 매번 다르게 해도 정답이나온다. ) #include #include #include #include using namespace std; int parent[101]; int getParent(int node){ if(parent[node]==node) return node; return parent[node] = getParent(parent[node]); } bool cmp(vector a, vectorb){ return a[2] 2024. 1. 29. 이전 1 2 3 4 5 6 ··· 30 다음