skive 🌿

2025.03.31 ~ 2025.04.28 ✨ 스터디를 찾게 된 계기코딩테스트를 준비하다 보니 꾸준함을 유지하기 위해 강제성이 부여되면 좋겠다는 생각이 들었다. 다른 취준생들과 함께 할 스터디를 찾아보던 중에 항해99의 1일 1알고리즘 챌린지에 대해 알게 되었다. 이전에도 항해99를 알고 있긴 했지만, 한 번도 이용해보지 않았는데 참가비 3만 원이라는 부담 없는 가격에 매일 문제를 풀도록 강제되는 시스템이 좋아서 고민 없이 신청했다. ✨ 99클럽 참여 후기 지금까지 돈을 내고 참여해본 스터디형 커뮤니티는 체인지업과 이번 99클럽이다. 물론 두 커뮤니티의 목적은 매우 다르지만(체인지업: 자소서/면접, 99클럽: 알고리즘) 체인지업 만큼이나 체계적이고 LMS가 직관적이다는 생각이 들었다.특히 좋았던..

[문제]백준 17265 - 나의 인생에는 수학과 함께 n x n 크기의 격자판에 숫자와 연산자(+, -, *)가 섞여 있다.(0,0)에서 시작하여 오른쪽이나 아래쪽으로만 이동할 수 있다.이동 경로를 따라 수식을 계산했을 때 최댓값과 최솟값을 구하는 문제. [문제 풀이] DFS(깊이 우선 탐색) 를 이용해 모든 가능한 경로를 탐색한다.숫자 칸에 도착하면 현재까지의 값과 직전 연산자를 이용해 새로운 값을 계산한다.연산자 칸에 도착하면 현재 연산자를 갱신한다.(n-1, n-1) 도착 지점에 도착하면 지금까지 계산된 결과로 최댓값과 최솟값을 갱신한다.연산자에 따라 계산하는 함수 cal()을 명확히 분리해서 가독성을 높였다. 첫 시작인 (0,0) 좌표는 항상 숫자라서 DFS를 호출할 때 숫자값만 cur로 ..

[문제]백준 28069 - 김밥천국의 계단 시작점은 0번 계단, 목표는 n번 계단에 정확히 k번 이하의 이동으로 도달하는 것 이동 방식은 두 가지:현재 계단 +1현재 계단 + (현재 계단 / 2)목표: 정확히 k번 이하의 이동으로 n번 계단에 도달할 수 있으면 "minigimbob", 아니면 "water" 출력 int nx1 = cur + 1;int nx2 = cur + (cur / 2); [문제 풀이] 이 문제는 가중치가 모두 1인 그래프의 최단거리 문제와 같으므로 BFS가 적합하다고 생각했다. 방문 배열 visited에 0번 계단에서 x번 계단까지 도달하는 최소 이동 횟수를 저장하고, BFS 탐색 도중 n번 계단에 도달했을 때 visited[n] - 1 BFS에서는 다음 상태를 아래와 같이..

[문제]백준 27971 - 강아지는 많을수록 좋다 [문제 풀이]이 문제는 특정 상태(강아지 수)에서 시작하여 A 또는 B를 더하는 식으로 상태를 확장해 나가는 최단 거리 탐색 문제로 볼 수 있다. 따라서 BFS(너비 우선 탐색)을 활용하여 직관적으로 구현해봤다. 1. q.push({0, 0}): 강아지 수 0마리부터 시작, 행동 횟수도 02. visited[]: 중복 방문 방지3. arr[]: 입력으로 주어진 금지 구간을 마킹. arr[i] == 1이면 해당 수의 강아지를 만들면 안 됨4. next > 100000: 문제 제한 범위를 초과하면 무시. BFS 특성상 가장 먼저 도착한 경로가 곧 최소 행동 횟수가 된다. [소스 코드]#include using namespace std;int n, m, ..

[문제]백준 18126 - 너구리 구구 노드 수 n (최대 5,000개)n-1개의 간선 (트리 구조)각 간선에는 거리 가중치가 있음임의의 두 정점 사이의 최대 거리(트리의 지름)를 출력 [문제 풀이] 1. DFS 탐색으로 1번 노드에서 출발하여 각 노드를 탐색2. cnt를 누적 거리로 전달하면서 res = max(res, cnt)로 최대값 갱신3. 양방향 간선이므로 from → to, to → from 모두 저장* 주의할 점: 자료형 오버플로우 (결과값을 long long으로 해야 한다) - 풀이 과정에서 새로 배운 것 : 구조 분해 선언(structured binding)for (auto [next, d] : a[from]) { ...} 위 문법은 사실상 아래와 같은 동작을 수행한다. fo..

[문제]프로그래머스 - 신규 아이디 추천 새로운 유저 아이디를 생성할 때, 정해진 7단계 규칙을 순차적으로 수행하여 적절한 아이디를 추천하는 문제다. 주어진 규칙은 문자열 전처리, 필터링, 변형, 길이 조정 등을 포함한다. [문제 풀이]단순하지만 문자열 필터링 과정을 단계별로 정확하게 구현해야 하는 문제였다. 문자열을 다루는 함수들을 주로 활용했으며 특히 erase와 같은 반복 중 삭제 연산은 iterator 무효화에 주의하며 풀었다. 직관적으로 인덱스를 수동 조정하는 방식을 이용해 풀었지만, STL의 remove_if나 unique, regex_replace 등을 활용한다면 코드를 더 다듬을 수 있을 것 같다. 사용한 주요 함수isupper(char)해당 문자가 대문자인지 확인tolower(c..

[문제]백준 17271 - 리그 오브 레전설(Small) 스킬을 시전해 정확히 N초를 채우는 모든 경우의 수를 구하는 문제다. 사용할 수 있는 스킬은 두 가지:A 스킬: 1초 소모B 스킬: M초 소모각 스킬은 무제한 사용 가능하고, 결과는 1,000,000,007로 나눈 나머지를 출력해야 한다. [문제 풀이]사용한 알고리즘: 동적 계획법 (DP)처음에는 모든 가능한 스킬 조합을 DFS로 완전탐색하는 방식이 떠올랐지만 N이 최대 10,000이기 때문에, 단순 DFS는 중복 호출이 많아지기 때문에 시간 초과가 발생할 것 같아서 DP를 이용했다. 단순 DFS는 시간 초과지만, 메모이제이션을 적용한 DFS는 사실상 Top-Down DP로 문제를 해결할 수 있다. dp[ i ]: 총 i초를 정확히 채우는 ..

[문제]백준 17484 - 진우의 달 여행 로봇은 맨 위 줄의 어느 칸에서든 시작 가능매 턴마다 ↙, ↓, ↘ 방향 중 하나로 이동단, 같은 방향을 연속해서 사용할 수 없음n행에 도달할 때까지의 최소 연료 소비량을 구해야 함 [문제 풀이]DFS로 모든 경로를 탐색하고 있었지만, "같은 방향을 연속해서 이동할 수 없다"는 제약 조건을 고려하지 못함.이로 인해 조건을 위반한 경로도 포함되어 정답보다 더 작은 잘못된 값이 결과로 출력될 수 있음.같은 방향을 연속해서 쓰지 않도록 prev_dir이라는 인자를 추가해 이전 방향과 비교 DFS는 중복 경로가 많아 효율이 떨어짐.그래서 dp[y][x][dir] = y행 x열에 dir 방향으로 도착했을 때 최소 연료로 정의하면 중복 경로 제거 + 빠른 연산 가능...

[문제]프로그래머스 - JadenCase 문자열 만들기 주어진 문자열 s를 JadenCase로 변환하는 문제다.각 단어의 첫 글자는 대문자나머지 알파벳은 소문자 단, 공백이 연속해서 들어올 수도 있고, 숫자로 시작하는 단어도 있다. [문제 풀이]1. 문자열을 공백을 기준으로 나눈다. (C++ STL에서는 문자열 분할을 지원하지 않기 때문에 따로 split 구현)2. 각 단어의 첫 글자를 대문자, 나머지는 소문자로 바꿔준다. (islower, isupper, tolower, toupper 사용)3. 공백을 붙여서 결과를 출력한다. 주요 알고리즘 및 함수 개념 정리✅ string.find(del)string 클래스의 함수로, del(구분자) 문자열이 처음 등장하는 위치를 반환한다.npos는 찾을 수 ..

[문제]백준 2156 - 포도주 시식 포도주 잔 n개가 일렬로 놓여 있고, 각 잔마다 포도주의 양이 주어진다.포도주는 연속으로 3잔을 마실 수 없다.마실 수 있는 포도주의 최대 양을 구하라. [문제 풀이]접근 방법: Dynamic Programmingdp[i]를 i번째 잔까지 고려했을 때 마실 수 있는 최대 포도주 양이라고 정의한다. i번째 포도주의 양은 a[i]이다.선택지는 아래 세 가지 중 하나이다:현재 잔을 마시지 않음 → dp[i - 1]현재 잔만 마심 (이전 잔은 마시지 않음) → dp[i - 2] + a[i]이전 잔과 현재 잔 둘 다 마심 (i-3번째는 마시지 않아야 함) → dp[i - 3] + a[i - 1] + a[i] 점화식: dp[0] = a[0];dp[1] = a[0] + ..