항해99 TIL

BFS

•

숫자/연산자 구분 처리

•

Character → Integer 변환

•

최댓값, 최솟값 경로 탐색

문제 파악 및 풀이

•

(0, 0)부터 시작하여 (n-1, n-1)까지 이동하며 만나는 숫자와 연산자들로 최댓값과 최솟값을 계산하는 문제이다.

•

이동 경로는 오른쪽 또는 아래 방향으로만 가능하다.

•

각 위치에는 숫자 또는 연산자가 번갈아가며 배치되어 있고, 연산자 다음에 반드시 숫자가 오기 때문에 직전에 어떤 연산자인지를 기억하며 연산을 수행해야 한다.

•

BFS를 통해 가능한 모든 경로를 탐색하며 최댓값과 최솟값을 동시에 갱신했다.

[99클럽 코테 스터디 20일차 TIL] 백준 17265번 - 나의 인생에는 수학과 함께

백준 28069번 - 미니김밥

오늘의 키워드

•

DP

•

점화식 구성

•

조건 만족 여부 판단

문제 파악 및 풀이

•

목표는 수 n에 도달하기까지 두 가지 연산 ( +1 또는 +i/2 )를 이용해 최소 횟수를 구하고, 해당 횟수가 제한된 횟수 k 이하인지 판별하는 것이다.

•

즉, 최소 횟수 문제로서 BFS처럼 보일 수 있지만, 이동 방법이 명확히 주어져 있어 DP로 선형 탐색이 가능하다고 판단했다.

•

핵심은 각 수에 도달하기 위한 최소 연산 횟수를 누적하면서, dp[i] 값을 갱신하는 것이다.

최종 풀이 코드

[99클럽 코테 스터디 19일차 TIL] 백준 28069번 - 미니김밥

백준 27971번 - 고양이는 많을수록 좋다

오늘의 키워드

•

DP

•

BFS (비효율적 접근)

•

최단 거리

•

점프 제약 조건 + 차단 구간

문제 파악 및 풀이

•

처음에는 최단 거리 문제처럼 보여 BFS로 접근했지만, 탐색 공간이 커서 시간 초과가 발생했다.

•

이후 DP로 점화식을 구성해 선형적으로 탐색하는 방식으로 변경하여 해결했다.

•

핵심은 특정 구간이 막혀 있고, 이동이 가능한 단위가 a 또는 b라는 점을 활용해 dp[i]를 i에 도달하기 위한 최소 횟수로 정의하는 것이다.

BFS 접근 (시간 초과 발생)

[99클럽 코테 스터디 18일차 TIL] 백준 27971번 - 고양이는 많을수록 좋다

백준 18126번 - 너구리 구구

오늘의 키워드

•

트리의 지름

•

BFS

•

거리 누적

•

long 자료형 처리

문제 파악 및 풀이

•

트리 형태의 연결 구조에서, 가장 먼 방 사이의 거리를 구하는 문제다.

•

시작점이 고정(0번 방)이고, 모든 경로가 양방향으로 주어지며 사이클이 없기 때문에 BFS로 거리 누적이 가능하다고 판단했다.

•

BFS를 통해 각 방까지의 누적 거리(memo 배열)를 계산한 뒤, 그 중 최대 값을 출력하면 된다.

•

하지만 가중치 C의 범위를 1,000,000,000까지 주는 것을 처음에 간과해서 int로 처리했다가 오버플로우 위험이 생겼고, 이로 인해 디버깅 시간이 길어졌다.

최종 풀이 코드

[99클럽 코테 스터디 17일차 TIL] 백준 18126번 - 너구리 구구

프로그래머스 - 신규 아이디 추천

오늘의 키워드

•

문자열 처리

•

단계별 구현

•

정규 표현식

문제 파악 및 풀이

•

문제는 총 7단계로 이루어진 문자열 처리 문제다.

•

단순 구현으로 접근했지만, 조건을 놓친 부분이 많아 여러 테스트케이스에서 실패했고, 하나하나 조건을 추가해가며 수정하느라 시간이 오래 걸렸다.

•

특히 마침표 연속 처리, 시작/끝 마침표 제거, 문자열 길이 조건 등에서 헷갈리는 부분이 많았다.

나의 풀이 코드

[99클럽 코테 스터디 16일차 TIL] 프로그래머스 - 신규 아이디 추천

백준 17271번 - 리그 오브 레전설

오늘의 키워드

•

동적 계획법(DP)

•

점화식

•

모듈러 연산

문제 파악 및 풀이

•

처음에는 현재 최선의 선택이 미래의 최선이 되지 않을 수 있다고 생각해 그리디가 아니라고 판단했다.

•

또, 정렬된 상태나 조건 기반의 구간 탐색이 아니라는 점에서 이분 탐색도 아니라고 생각했다.

•

하지만 문제를 보고도 이전 결과를 활용할 수 있다는 점을 인지하지 못해서 DP 접근을 떠올리지 못했다.

•

구현이나 백트래킹으로 접근하려 했지만, 힌트를 보고 나서야 DP 문제라는 것을 인지했다.

핵심 아이디어

•

dp[i] = dp[i - 1] + dp[i - m]

[99클럽 코테 스터디 15일차 TIL] 백준 17271번 - 리그 오브 레전설

백준 17484번 - 진우의 달 여행 (Small)

오늘의 키워드

•

BFS

•

우선순위 큐 (PriorityQueue)

•

조건에 따른 탐색 제한

문제 파악 및 풀이

•

해당 문제를 보고 처음에는 BFS를 활용해서 풀어야겠다고 생각했다.

•

이때 Deque와 PriorityQueue 중 어떤 자료구조를 사용할지 고민했다.

•

Deque를 사용할 경우 방문 체크가 필요해 보였고, PriorityQueue를 사용하면 방문 체크 없이도 항상 최소 경로를 우선 탐색할 수 있다는 점에서 공간 및 시간 측면에서 더 효율적이라 판단했다.

핵심 조건

•

연속으로 같은 방향(왼쪽, 아래, 오른쪽)으로 이동할 수 없다.

•

시작 지점은 첫 번째 행의 아무 열이나 가능하며, 마지막 행에 도달했을 때 최소 합을 구하는 문제이다.

[99클럽 코테 스터디 14일차 TIL] 백준 17484번 - 진우의 달 여행 (Small)

프로그래머스 - JadenCase 문자열 만들기

오늘의 키워드

•

문자열 처리

•

공백 유지

•

Character 클래스

문제 파악 및 풀이

•

처음에는 s.split(" ") 방식으로 접근했는데, 공백이 연속으로 들어올 경우 split 결과에서 해당 공백이 사라지는 문제가 발생했다.

•

즉, 공백을 기준으로 나누면 빈 문자열은 제거되기 때문에, 원래 문자열의 형태를 복원할 수 없었다.

•

이로 인해 오답이 발생했고, 문제를 다시 읽어보니 공백도 그대로 유지되어야 한다는 조건이 있었다.

•

StringTokenizer의 countTokens() 메서드를 처음 알게 되어 사용해보았지만, 이 역시 공백 유지에는 적절하지 않았다.

•

최종적으로는 문자열을 문자 단위로 순회하면서 직접 구현하였다.

시도한 풀이 (44/100점)

[99클럽 코테 스터디 13일차 TIL] 프로그래머스 - JadenCase 문자열 만들기

[99클럽 코테 스터디 12일차 TIL] 백준 2156번 - 포도주 시식

[99클럽 코테 스터디 11일차 TIL] 백준 16401번 - 과자 나눠주기

백준 1783번 - 병든 나이트

오늘의 키워드

•

수학적 규칙

•

조건 분기

•

최적화

문제 파악 및 풀이

•

문제를 처음 봤을 때 최대 숫자가 매우 커서 그리디 알고리즘을 생각했다.

•

하지만 문제를 자세히 분석해보니, N과 M의 크기에 따라 경우를 나눠 수학적으로 해결할 수 있는 문제였다.

•

이동 방법이 제한적이기 때문에, 세로 길이(N)와 가로 길이(M)에 따라 이동 횟수가 수학적으로 결정된다.

•

다만, 코드를 깔끔하게 작성하지 않아 조건별 경우를 찾는 데 시간이 걸렸다.

핵심 아이디어

•

세로(N)가 3 이상이고 가로(M)이 6 이상이면 다양한 이동이 가능하여 (M - 2)가 최대 방문 칸 수가 된다.

•

세로가 2인 경우에는 이동에 제약이 많아 (M - 1) / 2 + 1로 계산된다.

[99클럽 코테 스터디 10일차 TIL] 백준 1783번 - 병든 나이트

백준 2437번 - 저울

오늘의 키워드

•

그리디

•

부분합

문제 파악 및 풀이

•

처음에는 DP나 이분 탐색과 같은 다양한 접근법을 떠올렸지만, 권장 시간인 45분 이내에 풀지 못했다.

•

문제를 아무리 고민해도 해결 방법이 명확히 떠오르지 않아 풀이를 찾아보았고, 그리디 알고리즘으로 접근해야 하는 문제임을 알게 되었다.

•

주어진 추들을 오름차순 정렬한 뒤, 만들 수 있는 무게 범위를 하나씩 확장해나가며 가장 작은 만들 수 없는 무게를 찾는 방식이다.

핵심 아이디어

•

현재까지 만들 수 있는 모든 무게의 합을 sum이라고 할 때,

•

다음 추의 무게가 sum + 1보다 크면, sum + 1 무게는 만들 수 없다.

•

그렇지 않다면, 현재 추를 추가하여 만들 수 있는 무게 범위를 확장한다.

[99클럽 코테 스터디 9일차 TIL] 백준 2437번 - 저울

[99클럽 코테 스터디 8일차 TIL] 백준 9996번 - 한국이 그리울 땐 서버에 접속하지

[99클럽 코테 스터디 7일차 TIL] 백준 10799번 - 쇠막대기

[99클럽 코테 스터디 6일차 TIL] 백준 4963번 - 섬의 개수

백준 2559번 - 수열

오늘의 키워드

•

메모이제이션

•

누적합

•

시간 복잡도 개선

문제 파악 및 풀이

이 문제는 1년 전 파이썬을 사용해 풀었던 경험이 있어 반가운 문제였다. 처음에는 이중 for문을 이용한 간단한 방식으로 풀이했으나, 예전에 비해 시간이 매우 오래 걸렸다. 그래서 메모이제이션(누적합)을 이용한 효율적인 풀이를 추가하여 O(N)의 시간 복잡도로 단축할 수 있었다.

첫 번째 풀이 (이중 for문 - 비효율적)

두 번째 풀이 (메모이제이션 - 효율적)

추가 풀이 (1년 전 파이썬 풀이 - 가장 효율적)

1년 전 파이썬 풀이가 가장 직관적이고 효율적인 것 같아 추가했다.

[99클럽 코테 스터디 5일차 TIL] 백준 2559번 - 수열

[99클럽 코테 스터디 4일차 TIL] 백준 2468번 - 안전 영역

프로그래머스 - 바탕화면 정리

오늘의 키워드

•

구현

•

최대/최소 좌표값

문제 파악 및 풀이

•

문제를 보자마자 바로 최대, 최소 좌표값을 활용하면 풀 수 있겠다고 생각했다.

풀이 코드

오늘의 회고

어려웠던 점

•

오늘 문제는 간단하게 최대 최소값을 구하는 문제라 특별히 어려운 점은 없었다.

[99클럽 코테 스터디 3일차 TIL] 프로그래머스 - 바탕화면 정리

백준 14495번 - 피보나치 비스무리한 수열

오늘의 키워드

•

동적 프로그래밍(DP)

•

메모이제이션

문제 파악 및 풀이

•

해당 문제는 보자마자 메모이제이션을 사용해야겠다고 생각했다

풀이 코드

오늘의 회고

어려웠던 점

1.

자료형 범위를 고려하지 않아 초기에 틀린 점이 아쉬웠다.

[99클럽 코테 스터디 2일차 TIL] 백준 14495번 - 피보나치 비스무리한 수열

백준 1929번 - 소수 구하기

오늘의 키워드

•

소수 판별

•

에라토스테네스의 체

문제 파악 및 풀이

에라토스테네스의 체(Eratosthenes' sieve)

: 에라토스테네스의 체는 범위 내에서 소수를 빠르고 효율적으로 찾는 알고리즘

시간 복잡도는

O(Nlog⁡log⁡N)

로 효율적이다.

오늘의 회고

어려웠던 점

[99클럽 코테 스터디 1일차 TIL] 백준 1929번 - 소수 구하기

[99클럽 코테 스터디 0일차 TIL]