본문 바로가기
728x90
반응형

DFS7

[Baekjoon] 15686 치킨 배달(자바스크립트/NodeJs) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 👨‍💻 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리.. 2023. 1. 24.
[Baekjoon] 18428 감시 피하기(자바스크립트/NodeJs) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 👨‍💻 문제 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다. 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다. 또한.. 2023. 1. 18.
[Baekjoon] 14888 연산자 끼워넣기(자바스크립트/NodeJs) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 👨‍💻 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4.. 2023. 1. 17.
[Baekjoon] 14052 연구소(자바스크립트/NodeJs) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 👨‍💻 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 .. 2023. 1. 17.
[이코테] DFS/BFS_음료수 얼려 먹기(자바스크립트) 이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고 이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 product.kyobobook.co.kr 👨‍💻 문제 정답 코드 답안 1 답안 2 문제 풀이 이 문제는 dfs를 활용해서 풀 수 있다. 우선 이중 for 문을 활용해 2차원 배열의 모든 요소를 시작 지점 (0, 0)에서부터 탐색해나간다. 이때 현재 탐색하는 노드의 값이 0이라면 dfs 함수로 진입해서 상하좌우의 모든 요소를 탐색한다. 상하좌우의 노드.. 2023. 1. 16.
DFS/BFS (깊이 우선 탐색/너비 우선 탐색) 이 문제를 다 풀고 나서 다른 사람들이 짜놓은 코드를 보는데 'DFS'라는 개념이 등장했다. 이전부터 어렴풋이는 알고 있었지만 막상 코드를 읽으니 어떻게 돌아가는지 머릿속에 잘 그려지지 않았다. 어차피 공부해야 하는 내용이니 이참에 확실히 짚고 넘어가야겠다 싶어 정리해보았다. 先요약 DFS BFS 동작 원리 스택 큐 구현 방법 재귀 함수 큐 활용 🤔 DFS(Depth First Search, 깊이 우선 탐색) 🗣 그래프에서 깊은 부분부터 탐색하는 알고리즘. 스택 자료구조 활용. 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 pop 위의 과정 반복.. 2023. 1. 16.
트리(Tree) References 아래 링크의 강의 중 Section 25. Building a Tree의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy Node class Node { constructor(data) { this.data = data; this.children = []; } // node의 입력값 data를 배열로 children에 push add(data) { const node = new Node(data); this.children.push(node); } // filter() method로써 특정값을 제외한 배열을 반환 remove(data) { this.children = th.. 2022. 4. 5.
728x90
반응형