본문 바로가기

dfs22

[백준] 1520번: 내리막 길 (python) 1520번: 내리막 길 문제 ) 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로.. 2022. 3. 28.
[백준] 16562번: 친구비 (python) 16562번: 친구비 문제 ) 19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다! 학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다. 준석이는 이제 모든 친구에게 돈을 주지 않아도 된다! 위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라. 입력 .. 2022. 3. 27.
[SW Expert Academy] 2105. 디저트 카페 2105. 디저트 카페 문제) 친구들과 디저트 카페 투어를 할 계획이다. [Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다. 원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고 카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다. 디저트 카페 투어는 어느 한 카페에서 출발하여 [Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다. 디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다. 또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다. 즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다. [Fig. 4]와 같이 하나.. 2022. 3. 22.
[python] Stack과 DFS 자료 구조인 Stack과 DFS(깊이 우선 탐색)에 대해 알아보도록 하자. 1. Stack (스택) 스택(stack)은 제한적으로 접근할 수 있는 나열 구조로, 접근 방법은 항상 목록의 끝에서만 일어난다. 따라서 후입선출 (Last In First Out—LIFO)의 특성을 가지는 자료구조라고 불리운다. 이와 반대인 선입선출의 구조를 가진 queue도 존재하지만, 이번 글에서는 스택만 다루도록 한다. 스택에서는 다음과 같은 중요한 연산이 존재한다. S.size() 현재 스택에 들어있는 데이터 원소 개수를 반환한다. S.pop() 스택의 가장 윗 데이터를 반환하고, 삭제한다. S.push() 스택의 가장 윗 데이터를 추가한다. S.empty() 스택이 비었다면 1, 그렇지 않다면 0을 반환한다. S.ful.. 2022. 2. 27.

티스토리툴바