📍문제 링크 https://www.acmicpc.net/problem/18233 18233번: 러버덕을 사랑하는 모임 첫 번째 줄에 정수 N, P, E가 공백으로 구분되어 주어진다. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000) 그 다음 줄부터 N개의 줄에 걸쳐 회원 1부터 순서대로 xi와 yi가 공백으로 구분되어 주어진다. (1 ≤ xi www.acmicpc.net 📍알고리즘 분류 - 브루트포스 📍문제 풀이 (백트래킹) DFS를 활용해 nCp 조합을 구하고, 각 경우의 수가 범위를 만족하면서 전체 합이 E인 것을 구하면 된다 1. 조합을 구해야 하므로 백트래킹 코드를 만든다. 스택에는 실제 데이터가 아닌 인덱스만 담는 것이 간편하다 (중복을 제거하기 쉽고, 속도도 빠름) 2. p 가짓수..

📍문제 링크 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 위상 정렬 📍문제 풀이 N명의 학생을 줄세우려 한다. M개의 선, 후 정보가 주어질 때 모든 학생을 줄세우는 아무 방법을 출력한다 - 답이 여러개일 수 있음 1 { const [N, M] = input[0]; const graph = {}; // 진입 차수(간선에서 도착 횟수)를 기록할 배열 const in..

📍문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 브루트포스 알고리즘 - 그래프 탐색 - 너비 우선 탐색 📍문제 풀이 - N(세로) * M(가로) 좌표 평면에 바이러스, 벽, 빈칸이 존재한다. 벽을 딱 3개만 세울 수 있을 때, 확보 가능한 안전영역의 최대넓이를 구하라 - 바이러스는 벽이 없는 상하좌우로 퍼질 수 있다 - 빨간 2 = 바이러스 좌표 - 파란 1 = 벽 - 초록 0 = 벽을 세우는 좌표 ..

📍문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 시뮬레이션 - 깊이 우선 탐색 📍문제 풀이 1과 0으로 이루어진 n * m 보드가 주어진다. - 두 면이 0과 접한 1은 1턴 이후에 0으로 변하는데, 모든 1이 0으로 변하는데 몇 턴이 걸리는지 구하라 📍1트 : 완전탐색 -> 내부 공간 고려 못해 실패 1. 전체 보드 total 구하기 - ..

📍문제 링크 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 브루트포스 - 그래프 탐색 - 깊이 우선 탐색 📍문제 풀이 숫자가 담긴 5 x 5 이차원 배열이 주어진다. 2차원 배열에서 6개의 원소를 연결하여 만들 수 있는 수열의 가짓수를 출력한다 - 왔던 길을 되돌아갈 수 있다 ☑️재귀 DFS를 사용 - 매개변수로 수열을 사용하여 길이가 6이 되기 전까지는 이차원 배..

📍문제 링크 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 📍알고리즘 분류 - 자료구조 - 그래프 이론 - 그래프 탐색 - 깊이 우선 탐색 📍문제 풀이 인접 리스트를 만들 수 있는 정보와, 경로가 주어질 때, 주어진 경로가 DFS를 만족하는 경로인지 확인하라 📍의사 코드 경로의 현재 값을 A, 다음 값을 B라고 할 때, 1️⃣주어진 경로를 순회하며, A 와 B를 비교하는 반복문을 만든다 2️⃣분기 - A의 ..

📍문제 링크 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 트리 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 - 간선에 가중치를 갖는 트리가 주어질 때, 테스트 케이스에서 주어지는 시작점부터 끝점까지의 거리를 구하라 - DFS를 활용한다- 거리를 계산하는 로직은 아래와 같다1️⃣정점의 갯수 + 1 만큼의 길이를 갖는 빈 배열 distance를 만든다 (계산의 편의상)2️⃣현재 정점의 이웃 정점들을 순회하며 distance[이웃 정..

📍문제 링크 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 높이 m, 너비 n 의 사각형이 주어질 때, 1번째 row의 0이 마지막 row의 0까지 연결되어 있는지를 확인 DFS를 통해 연결된 경로가 있으면 바로 YES를 출력하면 된다 📍코드 (JavaScript) const [in1, ...map] = re..