핵심 요약 팰린드롬(Palindrome)은 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 의미하며, DP를 이용해 O(N^2)에 해결할 수 있습니다. 백준 10942번 문제는 로직의 정확성뿐만 아니라 대량의 입출력(I/O) 처리 능력을 평가하는 까다로운 문제입니다. 질문의 개수(M)가 100만 개일 때, Scanner와 System.out.println을 사용하면 I/O 오버헤드로 인해 필연적으로 시간 초과가 발생합니다. StringBuilder를 사용하여 정답을 메모리 버퍼에 담아두었다가 한 번에 출력하는 패턴은 코딩 … 더 읽기
핵심 요약 LCS(Longest Common Subsequence)는 두 문자열에서 순서를 유지하며 공통으로 나타나는 가장 긴 부분 수열을 찾는 알고리즘입니다. 연속될 필요가 없다는 점에서 Substring과 다릅니다. 핵심 논리는 문자열 끝에서부터 ‘같으면 포함하고, 다르면 버리는’ 분할 정복 방식입니다. 점화식 Math.max(위쪽, 왼쪽)은 단순히 표를 채우는 규칙이 아니라, 두 가지 논리적 경우의 수(Case)를 2차원 공간에 표현한 결과입니다. 단순 재귀로 풀면 O(2N)이 … 더 읽기
“같은 동전을 여러 번 써도 된다면?” Unbounded Knapsack(무한 배낭 문제)의 대표 예제인 백준 2293번을 통해, 반복문 순서의 비밀을 완벽하게 파헤칩니다. Outer Loop가 금액일 때(순열)와 동전일 때(조합)의 코드를 직접 비교하며, 왜 순서를 바꾸는 것만으로 중복이 사라지는지 명쾌하게 설명합니다. 코딩 전 점화식 설계의 중요성을 다시 한번 확인해 보세요.
“이걸 먼저 해야 저걸 할 수 있다?” 순서가 꼬인 코딩 테스트 문제, 위상정렬(Topological Sort)로 단번에 해결하세요! 난해한 개념을 게임 스킬 트리에 빗대어 쉽게 풀고, 필수 기출문제 백준 1005번(ACM Craft)의 완벽한 공략법을 다룹니다. 특히 복잡한 코드를 직관적으로 바꿔주는 ‘역방향 DFS’ 시크릿 팁까지 담았으니, 이 글 하나로 위상정렬을 확실하게 정복해 보세요.
복잡한 문제는 작게 쪼개고, 정답은 기억해둔다!” 코딩 테스트의 난관 DP(다이나믹 프로그래밍)를 완벽하게 정복하는 가이드 1부입니다. DP의 핵심 원리인 메모이제이션(Memoization)을 시험 공부에 빗대어 쉽게 설명하고, 재귀를 쓰는 Top-Down과 반복문을 쓰는 Bottom-Up 구현 방식을 코드와 함께 비교합니다. 이 글을 통해 DP의 기초 개념과 구현의 뼈대를 확실하게 잡아보세요.