전체 글40 99클럽 코테 스터디 20일차 TIL - 나의 인생에는 수학과 함께 (백준 17265) 오늘의 학습 키워드DFSDP경로 탐색경로 최대/최소값공부한 내용 정리오늘 문제는 N x N 격자에서 숫자와 연산자가 번갈아가며 위치해 있고, (0, 0)에서 (N-1, N-1)로 이동하면서 계산된 수식의 최대값과 최소값을 구하는 문제였어요. 조건 :(x + y)가 짝수일 땐 숫자, 홀수일 땐 연산자한 번 이동할 때는 오른쪽 또는 아래쪽으로만 이동 가능계산 과정 중 현재 위치가 숫자라면, 직전에 기억한 연산자를 이용해 값을 누적최대값과 최소값은 각각 max_dp, min_dp 배열로 관리하며 경로별 결과를 저장로직 요약:DFS를 통해 모든 가능한 경로를 탐색하면서,짝수 칸에 도달하면 현재까지 계산한 결과를 max_dp, min_dp에 갱신연산자는 문자열로 기억해두었다가 다음 숫자에 적용소스코드import .. 2025. 4. 25. 99클럽 코테 스터디 19일차 TIL - 김밥천국의 계단 (백준 28069) 오늘의 학습 키워드BFS상태 제한시간 초과 / 메모리 초과 이슈 대응경로 최적화공부한 내용 정리문제는 0번 계단에서 시작해서 K번의 행동만으로 정확히 N번 계단에 도달할 수 있는지 판단하는 문제였어요.행동은 2가지입니다:+1 계단 오르기+floor(i/2) 만큼 순간이동처음엔 단순한 DFS나 배열 기반 BFS로 접근했지만,K가 최대 1,000,000이라는 점, 그리고 방문 수 체크를 무한하게 하면 메모리 초과가 발생한다는 점에서 고비를 맞았어요.그래서 전략을 다음과 같이 바꿨어요:상태는 현재 위치(cur)와 행동 횟수(cnt[cur])로 구성BFS 탐색에서 cnt[다음 위치]를 방문 여부 판단 기준으로 사용중복 방문 방지를 위해 cnt[] 배열을 사용하고, 거리 업데이트 방식으로 최적화소스코드/*입력: .. 2025. 4. 24. 99클럽 코테 스터디 18일차 TIL - 강아지는 많을수록 좋다(백준 27971번) 오늘의 학습 키워드BFS (너비 우선 탐색)탐색금지된 구간 처리제약 조건 처리최단 거리공부한 내용 정리 오늘 문제는 마법소녀 호무라가 강아지를 N마리 만들기 위해 두 가지 마법(A, B 생성 마법)을 사용하는데, 처음에는 강아지 수 0에서 시작해 +A 또는 +B를 반복하며이는 BFS로 상태를 탐색하면 되는 전형적인 최단 거리 문제였습니다.현재 강아지 수가 금지된 구간에 포함되면 해당 상태는 방문 불가강아지 수가 N을 초과하지 않도록 하며, 0부터 N까지 탐색BFS를 통해 +A, +B 연산을 상태 그래프처럼 탐색하며 최소 횟수를 찾음주요 조건 :정확히 N에 도달하는 가장 빠른 행동 횟수(최소 연산 수) 를 구하는 문제로, 특정 금지된 개수 구간(닫힌 구간)에 들어가면 지금까지 키운 강아지가 전부 사라진다... 2025. 4. 23. 99클럽 코테 스터디 17일차 TIL - 너구리 구구 백준 18126번 오늘의 학습 키워드DFS(깊이 우선 탐색)그래프 탐색인접 리스트누적 거리 계산공부한 내용 정리이번 문제는 주어진 그래프(양방향)에서 1번 정점을 시작으로 도달할 수 있는 가장 먼 거리를 구하는 문제였습니다.주요 아이디어는 다음과 같습니다.각 노드는 연결된 이웃 노드와 해당 간선의 거리를 가지고 있어야 하므로, Node 클래스를 직접 정의 하여 index와 distance를 저장하였습니다.그래프는 인접 리스트(List[]) 로 구현하였습니다.DFS를 이용해 현재까지 이동한 거리(totalDistance)를 누적하면서, 탐색이 진행될 때 마다 최대 거리(maxDistance)를 갱신했습니다.흐름 요약:1번 노드에서 시작방문한 노드는 visited 배열에 표시이웃 노드를 따라가면서 누적 거리를 계산DFS가 끝.. 2025. 4. 22. 99클럽 코테 스터디 16일차 TIL - 프로그래머스 신규 아이디 추천 오늘의 학습 키워드문자열 처리정규 표현식(Regex)조건 분기예외처리시뮬레이션구현공부한 내용 정리이번 문제는 7단계로 문자열을 변형하여 규칙에 맞는 아이디를 만드는 작업이었습니다.각 단계마다 정해진 조건에 따라 new_id를 조작해야 했기 때문에 꼼꼼한 구현이 필요했습니다.문제를 읽느라 시간이 좀 걸렸습니다. 한 단계씩 구현하며 실행하면서 풀었습니다.주요 처리 흐름은 다음과 같았습니다:모든 대문자를 소문자로 변환 (toLowerCase)허용된 문자(소문자, 숫자, -, _, .)만 남기기 (정규식 사용)연속된 마침표를 하나로 합치기 (정규식 사용)문자열 앞뒤에 위치한 마침표 제거 (substring)빈 문자열이면 "a" 추가길이가 16자 이상이면 15자까지만 남기고, 끝에 마침표 있으면 제거길이가 2자 .. 2025. 4. 21. 99클럽 코테 스터디 15일차 TIL - 리그 오브 레전설(Small) 백준 17271번 오늘의 학습 키워드DP점화식최적화공부한 내용 정리문제는 N초 동안 A(1초) 또는 B(M초) 스킬을 사용해 시간을 정확히 채우는 방법의 수를 구하는 것이었습니다.이때 모듈러 연산(1,000,000,007로 나눈 나머지)을 적용해 결과를 출력해야 했습니다.핵심 아이디어는 다음과 같습니다:dp[i] = i초를 만드는 방법의 수dp[i] = dp[i-1] + dp[i-M]dp[i-1]: 1초짜리 스킬(A)을 하나 추가한 경우dp[i-M]: M초짜리 스킬(B)을 하나 추가한 경우 (단, i ≥ M일 때만)초기 상태로 dp[0] = 1 (0초를 만드는 방법은 아무것도 사용하지 않는 방법 1개)작은 문제부터 차근차근 쌓아나가면서 최종적으로 dp[N] 값을 구했습니다.소스코드/*백준 17271입력: N M조건: A시.. 2025. 4. 18. 99클럽 코테 스터디 14일차 TIL - 진우의 달 여행 (Small) 오늘의 학습 키워드다익스트라 알고리즘 변형우선순위 큐(PriorityQueue)방향 제한 탐공부한 내용 정리이번 문제는 기본적으로 최단 경로를 찾는 문제와 유사했지만, 같은 방향으로 연속 이동할 수 없다는 조건이 추가되어 있었습니다.따라서 단순한 다익스트라 알고리즘이 아니라, 현재까지 누적 연료량 + 이전에 움직인 방향까지 상태로 관리해야 했습니다.주요 아이디어는 다음과 같았습니다.(x, y) 위치에 도착했을 때, 이전 이동 방향을 함께 저장합니다.다음에 이동할 때, 직전 이동 방향과 같으면 이동하지 않습니다.첫 번째 줄의 모든 칸에서 출발할 수 있으며, N-1번째 줄(마지막 줄)에 도달하면 바로 최소 연료를 출력합니다.소스코드/*진우의 달 여행입력: 행렬 N, M 다음 N 줄동안 각 행렬의 원소 .. 2025. 4. 17. 99클럽 코테 스터디 13일차 TIL - JadenCase 문자열 만들기 오늘의 학습 키워드문자열 처리StringTokenizerCharacter 클래스조건분기공부한 내용 정리오늘 풀었던 문제는 문자열에서 각 단어의 첫 문자는 대문자로, 나머지는 소문자로 변환하는 것이 목표였습니다.다만 단순히 split(" ")을 쓰면 연속된 공백이 사라지기 때문에,이를 해결하기 위해 StringTokenizer를 " " 공백을 포함한 토큰(true) 으로 활용했습니다.각 토큰에서:공백이면 그대로 append(" ")단어이면 첫 글자를 char로 추출하고 나머지는 소문자로 변환 후첫 글자가 문자면 Character.toUpperCase()로 대문자화숫자거나 특수문자면 그대로 유지로직을 거쳐 StringBuilder에 이어붙이는 방식으로 구현했습니다.소스코드/*입력: 공백으로 분리되어있는 문자.. 2025. 4. 16. 99클럽 코테 스터디 12일차 TIL - 포도주 시식(백준 2156번) 오늘의 학습 키워드동적 계획법, DP부분합최대값 갱신상태 저장공부한 내용 정리이번 문제는 연속으로 3잔의 포도주를 마실 수 없다는 조건 하에가장 많은 양의 포도주를 마시는 경우를 찾는 문제였습니다.핵심은 지금 잔을 마시느냐 마시지 않느냐를 기준으로3가지 경우를 비교하는 방식으로 dp[i]를 정의한 것입니다.dp[i] = max( dp[i - 1], // 현재 잔을 마시지 않는 경우 dp[i - 2] + glass[i], // 현재 잔만 마시는 경우 dp[i - 3] + glass[i - 1] + glass[i] // 현재 잔과 이전 잔을 마시는 경우);이렇게 함으로써, 세 잔 연속으로 마시는 .. 2025. 4. 15. 이전 1 2 3 4 5 다음
