문제 설명 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요. 제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다. 입출력 예 word result "AAAAE" 6 "AAAE" 10 "I" 1563 "EIO" 1189 입출력 예 설명 입출력 예 #1 사전에서 첫 번째 단어는 "A"이고, 그다음은 ..

생각해보기 처음에는 아스키 코드를 통해 a ~ z까지 다 바꾸면서 비교하는 방식으로 했었다. 그러나 문제 조건을 활용하면 연산 횟수를 줄일 수 있다. 조건 1 - words라는 배열 안에 있는 단어로만 변환 가능하다는 점 조건 2 - 한 번의 변환 과정에서 하나의 알파벳만 바꿀 수 있다는 점 다른 알파벳의 수를 count해서 count가 1이면 변환 가능한 단어임을 알 수 있다. 조건 1에 의해 words 배열 안에 있는 단어들에 한정하여 비교를 진행하면 된다. DFS를 통해 탐색할 때, visited를 초기화하여 다른 경우의 수에 대해서도 탐색을 가능하게 한다. 또한 count를 갱신하면서 최소 횟수를 찾는다. 풀이) function solution(begin, target, words) { let a..

생각해보기 인접 리스트로만 풀다보니 인접 행렬에 대해 미숙했다. 인접 리스트와 인접 행렬에 대한 구현과 탐색을 다시 숙지하자. 네트워크의 개수 = 부분 그래프의 개수 임의의 정점 x에 대해 BFS 또는 DFS로 탐색하였을 때, 방문하지 않은 노드들은 임의의 정점 x와 같은 그래프에 속해 있지 않다. 따라서 방문하지 않은 노드들에 대해 BFS 또는 DFS 탐색을 다시 수행한다. 조건문 안에서 BFS 또는 DFS 함수가 호출된 횟수가 곧 네트워크의 개수이다. 풀이) function solution(n, computers) { let answer = 0; let visited = Array.from({ length: n }, () => false); // BFS function bfs(x) { let queu..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 생각해보기 인접 행렬과 인접 리스트의 구현과 탐색 방법 인접 행렬의 경우, 인수로 넘겨진 노드를 기준으로 해서 각각의 다른 노드들이 연결되어 있는지 확인하며 탐색 인접 리스트의 경우, 인수로 넘겨진 노드에 해당하는 인덱스에 연결된 노드의 정보들이 있음 DFS와 BFS의 노드 탐색 순서 DFS 재귀 호출이나 스택으로 구현 함수 호출이 되면서 방문 체크 BFS 큐..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 생각해보기 센서 N개를 K개의 분류로 나눠야 한다. 이를 위해서 K-1개의 기준선이 필요하다. 기준선은 센서 사이의 간격이 큰 것부터 선정한다. 이렇게 되면 선정된 기준선의 간격은 무시할 수 있게 되고 수신 가능 영역의 합이 최소가 된다. 센서 사이의 간격을 나타내는 배열을 diff라고 했을 때, 기준선으로 선정된 간격은 무시할 수 있으므로 지울 수 있다. 따라서 diff..

문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 생각해보기 입력값으로 주어진 2차원 배열을 순회하면서 방문 하지 않은 노드에 대해 BFS로 탐색 이때, 적군과 아군을 나누는 조건에 따라 인수를 다르게 전달한다. 풀이) const fs = require("fs"); const filepath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let input ..

문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 100..