본문 바로가기

전체 글199

[프로그래머스] 섬 연결하기 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.
[프로그래머스] 큰 수 만들기 c++ 풀이 앞자리에 큰 수가 들어가야한다. 1. 앞자리에 큰 수가 들어갈 수 있는 후보를 바로 옆가 비교하여 정한다. 2. 임의의 수 a,b,c,d가 있을때 수 abcd83이 있다면 a와 b중 큰거를 택하고 작은것을 삭제한다. 3. b 삭제 후 acd83 에서 a와 c를 비교해서 작은 것을 삭제한다. 4. c가 더 크다면 c와 d를 비교해서 더 작은 것을 삭제한다. 4. 2,3,4를 k가 0이 될 때까지 반복한다. #include #include #include using namespace std; string solution(string number, int k) { string answer = ""; for(int i=0;i 2024. 1. 29.
[프로그래머스] 조이스틱 c++ 풀이 정답이지만 비효율적인 코드이다. 매 순간마다 양 옆에 'A'가 아닌 글자 중에 더 가까운 곳을 선택한다. 이렇게 되면 왔다갔다하면서 한번만 가도 될 길에 여러번 갈 수 있다. 또한 출발시점에서 더 먼곳을 먼저 가는갈때 최소이동횟수를 만드는 케이스도 있다. 그리디 알고리즘 문제이지만 매번 어디를 갈지 하는 선택을 그리디로 하면 안된다. 모든 'A'가 아닌 위치를 각각 먼저가는 것을 검사하면 정답이나온다. #include #include #include #include using namespace std; int name_size=0; string name; int search(int start_cursor,int f_ans){ vectorchk; chk.resize(name_size); int ans.. 2024. 1. 26.

티스토리툴바