📍문제 링크 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 📍알고리즘 분류 - 수학 - 다이나믹 프로그래밍 - 게임이론 📍문제 풀이 두 사람 A, B가 게임을 하는데 N개의 돌 중에 1, 3개를 택해서 가져갈 수 있다. 마지막에 가져가는 사람이 이긴다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람은 누구일까? 🤔완벽하게 게임을 했을 때? - 이길 수 있는 상황에서 게임을 이기는 것. 확실한 finish로 시행 횟수를 최소화 하는 것! - 예) N = 7, A, B가 플레이어 A B A 1 3 3(무조건 3을 냄, 1을 내지 않음) 일단 A가 이긴다는 것은 진..

📍문제 링크 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/1057 1057번: 토너먼트김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를www.acmicpc.net 📍알고리즘 분류- 수학- 브루트포스 📍문제 풀이- 총 팀 수 N과 팀번호 A, B가 주어질 때, A, B 팀이 몇 라운드에서 만나는지 구하라 (A, B 팀은 무조건 이긴다고 가정) - 토너먼트의 규칙은 반드시 2팀씩 묶어 1팀만 올라간다는 것이다따라서 팀 1 2 3 4 가 있다면1라운드에서 묶음 1 1 2 2 로 나타낼 수 있다2라운드에서 묶음 1 1 1 1 로 나타낼 수 있고 토너먼트가 종..

📍문제 링크 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..

📍문제 링크 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 브루트포스 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 구현으로도 해결할 수 있는 문제이지만 DFS를 사용해서 풀자 - 크기가 작아서 구현으로 해결 가능 DFS를 사용하는 이유 - 빠르게 목표 지점에 도달하는 경로 하나만 찾으면 프로그램을 종료할 수 있어서 📍의사 코드 /* 1. 행렬 형태로 주어진 데이터를 2차원 배열로..