여가생활 개발일지

[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++] 백준 2504번 괄호의 값 (정규 표현식)

백준 2504번 괄호의 값 문제 바로가기 ※ 주의사항 이 문제의 대표적인 풀이는 스택입니다. 하지만 필자는 정규표현식 연습을 위해서 다른 방법으로 풀었습니다. 스택 풀이는 다른 블로그에서 보셔야 해요! 이 방법은 이렇게도 풀 수 있구나 하고 넘어가시면 됩니다 사용 알고리즘 정규 표현식 풀이 문제의 5가지 문자를 구분할 정규표현식 만든다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다. (), []와 같이 사이에 아무것도 없이 붙어 있는 괄호를 바로 숫자로 치환해 준다. regex_repl..

[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..

[C++] 백준 13549번 숨바꼭질3 (DP, 다익스트라)

백준 13549번 숨바꼭질3 문제 바로가기 알고리즘 분류 DP 다익스트라 풀이 점화식은 위치가 짝수일 때와 홀수일 때로 나뉜다. 짝수일 때 1칸 이전 값 (가중치 1) 절반 위치 (가중치 0) 홀수일 때 1칸 이전 값 (가중치 1) 1칸 앞(짝수)의 절반 위치(가중치 1) 하지만 홀수의 점화식에 의문이 들 수가 있다. 왜 1칸 앞의 절반만 고려할까? 문제에서는 앞이나 뒤로 1칸씩 이동할 수 있다고 했는데? 2로 나눈 값이 올림 또는 내림이 될 수 있는 거 아니야? 왜 "1칸 뒤(짝수)의 절반 위치"는 고려하지 않을까? 결론부터 말하자면 점화식에 1칸 뒤 절반 위치를 넣어도 결과는 동일하다. 하지만 의미 없는 연산이다. 이유는 "1칸 이전 값"과 중복되기 때문이다. 예를 들어 현재 위치가 9라고 가정해 보..

[C++] 백준 2615번 오목 (구현)

백준 2615번 오목 문제 바로가기 알고리즘 분류 구현 풀이 방향 설정하기 8방향 모두 검사할 필요 없이, 우(→), 하(↓), 상우(↗), 하우(↘) 4방향만 검사하면 된다. 중복되는 방향 제거 가로 방향을 예시로 왼쪽으로 훑기(←), 오른쪽으로(→) 훑기 당연히 2가지다. 첫 번째 돌부터 오른쪽으로 훑기 = 마지막 돌부터 왼쪽으로 훑기 방향의 우선순위 문제에서는 우선순위가 왼쪽 다음 위쪽이라고 정해졌다. 상우(↗) 대신에 하좌(↙)를 검사한다면 위쪽을 먼저 우선순위로 두게 된다(화살표 말고 시작점을 보자) 오목 검사를 시작 좌표 고르기 검은 바둑돌 또는 흰 바둑돌 이어야 한다. 인접한 같은 색깔의 돌이 우(→), 하(↓), 상우(↗), 하우(↘) 4방향 중에 있어야 한다. 인접한 같은 색깔의 돌이 좌..