여가생활 개발일지

[C++] 프로그래머스 다단계 칫솔 판매

프로그래머스 다단계 칫솔 판매 문제 바로가기 사용 알고리즘 구현 레슨런 아래의 두 코드는 부모 노드를 재귀로 탐색하는 함수이다. 함수의 흐름과 기능은 같다. 그러니 이것을 제외하고 두 코드의 차이는 무엇일까? 1번 함수 void find(int child, int money) { if(child == 0) return; int div = money * 0.1; if(div == 0) { selling[child] += money; return; } selling[child] += money - div; return find(root[child], div); } 2번 함수 void find(int child, int money) { if(child == 0) return; if(money * 0.1 == ..

[C++] 프로그래머스 혼자 놀기의 달인

프로그래머스 혼자 놀기의 달인 문제 바로가기 사용 알고리즘 구현 풀이 문제를 짧게 세 줄로 요약하자면 이렇다. 1. 숫자는 이동할 배열 원소의 순번이다. 2. 계속 숫자를 재귀처럼 이동하는데, 끝날 때까지의 이동한 횟수를 센다. 3. 한번 쭉 이동한 것을 그룹이라고 한다. 모든 그룹 중에서 가장 횟수가 큰 2개의 곱이 정답이다. 문제에서 주어진 테스트 케이스를 예시로 살펴보자. 배열의 원소 [8, 6, 3, 7, 2, 5, 1, 4] 여기서 8을 시작으로 그룹을 지어보면, 1. 배열의 8번째 인덱스는 4이다. 2. 배열의 4번째 인덱스는 7이다. 3. 배열의 7번째 인덱스는 1이다. 4. 배열의 1번째 인덱스는 8이다. (되돌아옴) 이렇게 꼬리 물기를 하면 된다. 첫번째 그룹은 [8, 4, 7, 1]이 ..

[C++] 프로그래머스 시소 짝꿍

프로그래머스 시소 짝꿍 문제 바로가기 사용 알고리즘 map 조합 풀이 1. 같은 몸무게끼리 묶기 중복되는 몸무게는 같은 거리에서 균형을 이룬다. 중복되는 몸무게끼리의 경우의 수는 (n-1)의 등차수열 합이다 = n(n-1)/2 2. 다른 몸무게끼리 2m, 3m, 4m 계산하기 비율이 같다는 건 몸무게가 같다는 뜻이다. 중복은 1번에서 이미 계산했으므로 계산하지 않는다. 조합에서는 순서를 고려하지 않는다. 즉, 순서가 달라도 같다. (AB == BA) 예시로 내가 100이고 상대방이 200이라고 가정하자. 내가 4m에 상대방을 2m로 계산하여 결과에 더하고, 반대로 상대방이 2m에 나를 4m로 계산해 버리면 계산이 중복된다. 결과적으로 1번에서 이미 중복을 계산했으므로 제외하고, 다른 몸무게는 오름차순 비..

[C++] 프로그래머스 마법의 엘리베이터

마법의 엘리베이터 문제 바로가기 사용 알고리즘 완전 탐색 풀이 경우의 수가 4가지 존재한다. 이전 층 영향 있음 (자리 올림) 현재 층에서 올라가기 현재 층에서 내려가기 이전 층 영향 없음 현재 층에서 올라가기 현재 층에서 내려가기 이전 층에 영향 없으면 눌러야 되는 버튼 수를 그대로 더하면 된다. 하지만 이전 층에 영향이 있으면 자리올림 때문에 버튼 수를 1을 더해준다. 풀이 코드 #include using namespace std; int ans = 1e9; string elevator; // 캐리 여부, 현재 위치, 버튼 누른 수 void dfs(bool carry, int depth, int cnt) { // 종료 조건 if(depth == -1) { // 캐리 if(carry) cnt++; if..