특정한 i번째 노드를 루트로 하는 서브 트리에 대해 i번째 루트 노드를 포함했을 때와 포함하지 않았을 때 중 조건에 맞는 답을 정의한다.DP[i]: i를 루트 노드로 하는 서브 트리에 있는 노드에 적힌 수들의 합특정 노드를 출발점으로 하여 새로운 DFS가 진행한다고 하더라도, 이전에 한 번이라도 방문된 노드는 다시 가지 않도록 하면 트리를 탐색하는 것과 같아진다.int dfs(int cur) { // 이미 방문한 곳은 가지 않도록 한다. if (visit[cur]) return dp[cur]; visit[cur]= true; // cur와 인접한 노드를 방문한다. for (auto next: node[cur]) { // 이미 방문한 곳 X if (visit[next]) continu..

## 더 맵게- 번호: 42626- 난이도: Lv.2- 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626- 풀이 여부: O- 다시 풀 필요: O - 핵심 아이디어: 힙(우선순위 큐)- 내가 막힌 지점: JS로 우선순위 큐를 만드는 지점에서 막혔다.- 시간복잡도: O(N log N)- 공간복잡도: O(N)- 회고: JS로 힙을 만드는 걸 다른 문제 풀어보며 더 연습해봐야겠다. 문제 정보문제 번호: 42626문제명: 더 맵게난이도: Lv.2링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626접근 과정처음 떠올린 풀이가장 작은 것 두 개를 빼낸 뒤 계산한다는 부분을 보고,..

처음 갭체크를 받았을 때 가장 부족하다고 느낀 유형은 완전 탐색이었다. 문제를 보면 어디서부터 경우의 수를 나누어야 할지 막막했고, 반복문으로 풀어야 할지 DFS로 풀어야 할지 판단하는 것부터 어려웠다. 그래서 지난 한 달 동안 코드트리에서 완전 탐색 관련 문제를 꾸준히 풀며, 문제 조건을 하나씩 분리해서 생각하는 연습을 했다. 단순히 정답을 맞히는 것보다 “왜 이 경우를 모두 확인해야 하는지”, “불필요한 탐색은 없는지”를 고민하며 풀이 과정을 정리하려고 했다. 이번 갭체크 결과에서는 이전과 다르게 완전 탐색 문제는 어느 정도 풀 수 있게 되었다는 점에서 스스로 성장을 느꼈다. 물론 새롭게 백트래킹이 부족한 유형으로 나왔기 때문에 아직 완전히 약점을 극복했다고 말하기는 어렵다. 백트래킹도 결국 완전 탐..

알고리즘 공부를 하다 보면 한 번 풀었다고 해서 완전히 내 것이 되는 문제는 생각보다 많지 않았다.특히 처음에는 이해한 것 같았지만, 며칠 뒤 다시 보면 풀이 흐름이 바로 떠오르지 않는 문제들이 있었다.저에게는 그중 하나가 이진트리의 탐색 문제였다. 저는 코드트리에서 문제를 풀면서 단순히 어려웠던 문제만 북마크하지 않았다.북마크 폴더를 만들 때는 다음과 같은 기준으로 분류했다.첫 번째는 개념은 알지만 구현이 헷갈리는 문제였다.예를 들어 이진트리 탐색처럼 전위 순회, 중위 순회, 후위 순회의 개념은 이해했지만, 막상 코드로 작성할 때 순서가 헷갈리는 문제를 따로 모아두었다.두 번째는 다시 풀었을 때 실력 향상이 잘 보이는 문제였다.처음에는 해설을 참고하거나 오래 고민해서 풀었지만, 다시 풀었을 때 스스로 ..

코드트리를 꾸준히 활용하는 데 가장 도움이 된 기능은 학습 리마인더 알림톡이다. 코딩테스트 공부는 하루에 몰아서 많이 푸는 것보다, 매일 조금씩이라도 문제를 풀며 감을 유지하는 것이 중요하다고 생각한다. 하지만 혼자 공부하다 보면 바쁘다는 이유로 하루 이틀 미루게 되고, 한 번 흐름이 끊기면 다시 시작하는 데 시간이 걸리는 경우가 많았다. 이때 코드트리의 알림톡 연동 기능이 좋은 동기 부여가 되었다. 매일 카카오톡으로 학습 리마인드가 오기 때문에 자연스럽게 “오늘도 한 문제는 풀어야겠다”는 생각을 하게 된다. 단순히 앱에 접속했을 때만 확인할 수 있는 알림이 아니라, 평소 자주 사용하는 카카오톡으로 리마인드가 오다 보니 학습을 잊지 않게 해주는 효과가 컸다. 다른 학습 서비스의 경우 문제를 풀기 위한..

코딩테스트 공부를 하면서 내가 가장 약하다고 느낀 알고리즘 유형은 완전탐색이었다. 문제를 보면 “이건 모든 경우를 확인하면 되겠다”는 생각은 들었지만, 막상 구현하려고 하면 어디까지 반복문을 돌려야 하는지, 어떤 조건으로 가지치기를 해야 하는지, 시간 복잡도는 괜찮은지 확신이 서지 않았다. 그래서 문제를 풀 때마다 감으로 접근하는 경우가 많았고, 조금만 조건이 복잡해져도 풀이가 흔들렸다. 이번에 코드트리를 통해 공부하면서 가장 좋았던 점은 커리큘럼이 레슨 단위로 잘게 나뉘어 있다는 점이었다. 단순히 문제만 많이 던져주는 방식이 아니라, 먼저 개념을 익히고 기본 문제를 풀어본 뒤, 연습 문제로 풀이 감각을 쌓고, 마지막으로 테스트 문제를 통해 내가 제대로 이해했는지 확인할 수 있었다. 특히 완전탐색처럼 ..

친구의 추천으로 코드트리에 가입하게 되었고, 본격적으로 알고리즘 공부를 시작하기 전에 먼저 갭체크를 응시해 보았다. 처음에는 가볍게 현재 실력을 확인해 보는 정도라고 생각했는데, 막상 문제를 풀어보니 생각보다 부족한 부분이 바로 드러나서 꽤 인상 깊었다. 평소에 진짜 약하다고 생각했던 완전탐색이 바로 나왔기 때문이다...나름 어려운 문제도 많이 풀어봤으나 그래도 가장 기본기인 완전 탐색이 항상 부족하다고 느끼긴 했는데 그게 여기서 바로 드러났다...ㄷㄷ 갭체크를 통해 확인한 강점은 그래도 기본적인 구현이나 문제를 읽고 조건을 정리하는 부분은 어느 정도 따라갈 수 있다는 점이었다. 반면 약점은 역시 완전탐색처럼 경우의 수를 체계적으로 나누고, 빠짐없이 탐색하는 사고 방식이 부족하다는 점이었다. 평소에는 막..

오랜만에 문제를 풀었다. 가볍게 실버 1로... 1. 문제https://www.acmicpc.net/problem/5014 2. 풀이그래프 분류를 보고 문제를 풀긴 했으나 그래프라는 생각이 도저히 생각이 나지 않아 그리디로 풀어버렸다. 그래도 문제 분류는 BFS라고 써있으니 문제를 푼 다음 다른 사람들의 코드를 훑어보았다. BFS는 한 단계씩 탐색하는 느낌이라면, 나는 한꺼번에 오르내리는 느낌이었다. if (S + U 이 부분이 바로 한꺼번에 뛰어넘는 부분이다. 그래서인지 시간을 단축할 수 있었고, 실행시간 3등~이 되었다.3. 소스 코드const readline = require("readline");const rl = readline.createInterface({ input: process.s..