와드의 블로그

어느덧 코드트리 청약 챌린지의 마지막인 7주차에 다다랐습니다. 처음 시작할 때만 해도 '매일 빠짐없이 알고리즘 문제를 풀 수 있을까?' 하는 걱정이 앞섰지만, 꽤 힘들었던 시간들을 이겨내고 끝내 완주해낸 제 자신에게 먼저 고생했다는 칭찬을 해주고 싶습니다.오늘은 7주간의 여정을 돌아보며, 그동안의 변화와 앞으로의 다짐을 솔직하게 정리해 보려 합니다.시작할 때와 가장 달라진 점, 그리고 가장 뿌듯했던 순간1주차 첫 갭체크(Gap Check) 진단 당시, 저는 백트래킹과 그래프 탐색 영역에서 뚜렷한 약점을 보였고 동적 계획법(DP)은 아예 접근조차 어려워하던 상태였습니다.하지만 7주가 지난 지금, 가장 크게 달라진 점은 문제를 마주하는 '태도'와 '시야'입니다. 예전에는 복잡한 문제를 보면 막막함부터 느꼈다..

1. 다익스트라 알고리즘은 무엇일까?다익스트라 알고리즘은 그래프 내의 한 정점(시작점)에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.현실 세계에서 내비게이션이 목적지까지의 최소 시간 경로나 최소 비용 경로를 찾을 때 사용하는 알고리즘의 뼈대가 되기도 합니다. 단, 이 알고리즘은 간선의 가중치가 음수가 아닐 때만 정상적으로 동작한다는 중요한 제약 조건이 있습니다. 음수 간선이 존재할 경우에는 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.2. 동작 과정다익스트라 알고리즘은 '매 순간 가장 비용이 적은 노드를 선택한다'는 그리디(Greedy) 알고리즘과, '이전에 계산해둔 최단 거리 값을 활용한다'는 동적 계획법(DP)의 아이디어가 결합되어 있습니다.기본적인 동작 과정은 다음과..

코드트리 청약 챌린지를 시작하고 매일 꾸준히 학습을 진행한 지 어느덧 한 달이 지났습니다. 시간의 흐름에 맞춰 내 실력이 얼마나 향상되었는지, 또 현재 시점에서의 취약점은 무엇인지 파악하기 위해 2차 갭체크를 진행했습니다.오늘은 첫 갭체크와 이번 갭체크를 비교해보고, 지난 한 달간의 노력과 앞으로의 학습 목표를 정리해보고자 합니다.1. 첫 갭체크와 2차 갭체크 비교 및 한 달간의 노력1회차 갭체크 당시, 저는 백트래킹과 그래프 탐색 영역에서 약점이 있다는 진단을 받았습니다. 이를 극복하기 위해 한 달 동안 코드트리의 '알고리즘 입문' 단계 중 백트래킹 파트를 차근차근 학습하며 기본기를 다지는 데 집중했습니다.이번 2차 갭체크를 진행할 때는 이전과 다르게 설정에 변화를 주었습니다. 1회차에서는 내가 학습 ..

코드트리에서 문제를 푼 지 거의 한 달이 다 되어갑니다. 매일 꾸준히 학습 트레일을 따라가다 보니 알고리즘 문제에 익숙해지고 서서히 자신감이 붙는 기분입니다.알고리즘 문제를 풀다 보면 풀다가 막혀 풀이를 참고하거나 힌트를 보고 푸는 경우가 반드시 존재합니다. 또는 이전에는 분명 풀었던 문제인데 다시 풀어보니까 안 풀리는 당황스러운 경우도 있습니다. 따라서 난이도가 있거나 푸는 데 오래 걸린 문제는 반복적으로 풀어 숙달해야 할 필요가 있습니다.투박하지만 확실한 나만의 북마크 활용법코드트리에서는 '북마크' 기능을 제공하여 다시 풀고 싶은 문제를 모아서 볼 수 있습니다.보통 북마크 폴더를 알고리즘 주제별로나 난이도별로 세분화해서 분류하는 분들도 계시겠지만, 저는 복잡한 기준 없이 그냥 하나의 북마크에 다 넣는..

2회차에 걸쳐 갭체크 진단과 취약점(백트래킹) 보완을 마친 뒤, 이제는 코드트리의 학습 트레일을 따라 매일 꾸준히 학습하는 습관을 들이고 있습니다.코딩 테스트는 단기간에 몰아서 하는 것보다 매일 조금씩이라도 꾸준히 감을 잃지 않는 것이 중요한데, 오늘은 제가 어떻게 학습 동기를 유지하고 루틴을 만들고 있는지에 대해 이야기해 보려 합니다.깃허브(GitHub) 연동으로 잔디 심기저는 기존에 백준이나 프로그래머스에서 문제를 풀 때 '백준허브'라는 크롬 익스텐션을 사용하여 깃허브에 코드를 자동 백업해 왔습니다. 내 학습 기록이 차곡차곡 쌓이는 것을 보는 것은 꽤나 큰 동기부여가 되거든요.그런데 코드트리에서는 확장 프로그램 없이 플랫폼 자체에서 깃허브 저장소(Repository) 연동 기능을 완벽하게 지원합니다...

알고리즘 문제 풀이나 기술 면접에서 자주 등장하는 대표적인 정렬 알고리즘 8가지(거품, 선택, 삽입, 퀵, 병합, 힙, 기수, 계수 정렬)의 개념과 특징, 시간복잡도, 그리고 Java 코드를 정리해보았습니다.1. 거품 정렬 (Bubble Sort)서로 인접한 두 원소를 비교하여 정렬 기준에 맞지 않으면 자리를 교환하는 알고리즘입니다.과정 (오름차순 기준)첫 번째 원소부터 인접한 원소와 비교하여 조건에 맞지 않으면 위치를 바꿉니다.1회전이 종료되면 가장 큰 원소가 배열의 맨 끝에 위치하게 됩니다.정렬되지 않은 나머지 원소들을 대상으로 위 과정을 반복합니다.특징구현이 간단하고 코드가 직관적입니다.주어진 배열 안에서 교환하는 제자리 정렬(In-place Sort)입니다.중복된 값의 순서가 바뀌지 않는 안정 정..

1회차에서 진행했던 갭체크 결과를 기반으로 이번 주에는 나의 약점 중 하나였던 백트래킹 트랙을 집중적으로 학습했습니다.코드트리 플랫폼은 주제별로 단계적인 개념 설명과 문제들이 체계적으로 준비되어 있어, 기초부터 응용까지 차근차근 학습하기에 매우 좋았습니다. 이번 포스팅에서는 백트래킹 트랙을 진행하며 가장 인상 깊었고 까다로웠던 문제를 하나 소개하고 풀이를 정리해보려 합니다.문제: 2명의 도둑링크: 2명의 도둑알고리즘 분류: 완전 탐색(Brute Force), 비트마스킹(Bitmasking), 조합론(Combinatorics)문제 설명2명의 도둑이 N * N 크기의 방에서 물건을 훔치려 합니다. 두 도둑은 각각 하나의 행을 정해 그 행 내에 연속한 M개의 열에 있는 물건들을 훔칠 수 있습니다.[조건]두 도..

문제두 마리의 백조가 호수에 살고 있습니다. 호수는 행 R, 열 C 크기의 직사각형 모양이며, 물('.')과 빙판('X'), 그리고 백조('L')로 이루어져 있습니다. 매일 빙판은 물과 닿아있는 부분이 녹아서 물로 변합니다. 백조는 오직 물을 따라서 상하좌우로만 이동할 수 있습니다. 며칠이 지나야 두 백조가 서로 만날 수 있는지 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 R과 C가 주어집니다. (1 ≤ R, C ≤ 1,500) 둘째 줄부터 R개의 줄에 호수의 상태가 주어집니다.출력: 첫째 줄에 며칠이 지나야 두 백조가 만날 수 있는지 출력합니다.풀이: 2개의 큐(Queue)를 활용한 이어 달리기 BFS 최적화이 문제의 맵 최대 크기는 1,500 × 1,500입니다. 만약 매일 얼음을 녹이고,..

백준 서비스 종료 후 새로운 코딩 테스트 학습 사이트를 찾던 중, 인스타그램에서 우연히 코드트리 청약 챌린지를 발견하고 참여를 결정했습니다.1회차 미션은 본격적인 학습에 앞서 코딩 테스트 실력을 진단해 볼 수 있는 갭체크(Gap Check)였습니다.갭체크 진행 후기코드트리의 갭체크가 다른 플랫폼들과 차별화되는 점은 무작위로 문제를 던져주는 것이 아니라, 내가 학습하고자 하는 관련 주제나 개념을 선택하면 해당 개념을 위주로 문제가 출제된다는 점이었습니다.저는 최근 집중적으로 다루고 있는 '완전탐색', '백트래킹', 'DP(동적 계획법)'을 주제로 선택하여 진단을 진행했습니다.출제 문제 수: 총 5문제결과: 4문제 정답, 1문제 미해결 (4/5)체감 난이도 및 타임어택: 문제 자체의 난이도가 극악인 것은 아..

문제비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하는 문제입니다. 숫자 $x$의 범위는 1부터 20까지로 매우 작습니다.add x: S에 $x$를 추가합니다. (이미 있는 경우 무시)remove x: S에서 $x$를 제거합니다. (없는 경우 무시)check x: S에 $x$가 있으면 1을, 없으면 0을 출력합니다.toggle x: S에 $x$가 있으면 제거하고, 없으면 추가합니다.all: S를 {1, 2, ..., 20}으로 바꿉니다.empty: S를 공집합으로 바꿉니다.입력: 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)출력: check 연산이 주어질 때마다 결과를 출력합니다.풀이: 비트마스킹을 활용한 메모리 최적화이 문제의 핵심은 4MB라는 극도로 적은 메..