코딩 버릇 여든까지 간다

문제 1. 음료수 얼려 먹기 문제 해결 아이디어 이 문제는 연결 요소 찾기(connected component) 문제이다. DFS 혹은 BFS로 해결할 수 있으며 연결 요소 개수가 몇 개 인지 구하면 되는 문제이다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링할 수 있다. 다음과 같이 3 X 3 크기의 얼음 틀이 있다고 가정해보자. 이와 같이 그래프 형태로 모델링을 해보면 상하좌우로 연결되어 있는 위치들은 서로 인접한 노드 형태로 표현할 수 있다. 특정 기점에서 DFS 혹은 BFS를 수행해서 이동 가능한 모든 경로에 대해서 방문처리를 진행할 수 있다. (왼쪽 상단에 있는 0에서 시작된다면 인접한 0 노드 2개가 방문처리 된다) 1인 노드는 이..

그래프 탐색 알고리즘: DFS/BFS 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 특정 조건에 맞는 데이터가 존재하는지, 존재한다면 어떤 위치에 존재하는지 등을 찾고자 하는 목적으로 다양한 탐색 알고리즘을 사용한다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. 코딩 테스트에서 매우 자주 등장하는 유형이다 (⭐️⭐️⭐️⭐️⭐️ 반드시 숙지하도록) 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 예를 들어, 여러 개의 박스를 쌓을 때 (스택하고자 할 때) 아래쪽에서부터 차례대로 박스를 올려놓는다. 쌓아 올린 박스를 다시 내려놓고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 ..