알고리즘/프로그래머스71 [프로그래머스] 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. [프로그래머스] 구명보트 c++ 풀이 보트는 최대 두명씩 탈 수 있기 때문에 무거운 순과 가벼운 순으로 짝을 맞추어 주면된다. a>=b>=c>=d라고 할때 {a,d} {b,c}로 짝은 맞추어준다. a+d =idx2) break; if(people[idx2]+people[idx1] 2024. 1. 29. 이전 1 2 3 4 5 6 ··· 18 다음