Solution1. 송전탑과 연결된 간선은 이중 리스트를 활용해 트리로 나타낸다.송전탑 번호 = 인덱스 번호간선 = 그 인덱스에 들어있는 번호들2. BFS를 활용하여 끊긴 노드를 제외하고 자신과 연결되어 있는 노드의 개수를 센다.3. bfs를 돌리기 전 해당 노드를 미리 방문처리 하는 방식으로 간선을 끊는 걸 구현한다. Codefrom collections import dequedef solution(n, wires): answer = n # wires를 2차원 배열로 표현, 1번 송전탑부터 시작이기 때문에 n+1 tree = [[] for _ in range(n+1)] # 송전탑 간의 간선을 트리로 구현 for v1, v2 in wires: tree[v1].app..
Problem Solve
Solutiontarget의 단어를 만들고 count 된 숫자를 return 해야 하기 때문에 BFS를 사용한다.글자 검사하는 건 반복문으로 하나씩 돌려본다. Codefrom collections import dequedef solution(begin, target, words): # target하는 단어가 배열에 없으면 0을 return한다. if target not in words: return 0 answer = bfs(begin, target, words) return answerdef bfs(begin, target, words): queue = deque() queue.append([begin, 0]) # 시작 단어와 카운트를 처음으로 추가해준다. ..
더보기문제 설명ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.첫 번째 방법은 11개의..
7월 13일에 진행되는 '삼성전자 DX부문 하계 대학생 S/W 알고리즘 역량 강화 특강'에 참여하기 위해 앞으로 일주일 간은 SEA에서 알고리즘 문제를 풀어보려 한다.문제 설명25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.판매는 얼마든지 할 수 있다. 예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.입력..
문제 설명네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한 사항컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.각 컴퓨터는 0부터 n-1인 정수로 표현합니다.i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][..
문제 설명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 이상 1000 이하인 자연수입니..
더보기문제 설명XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전..
더보기문제 설명Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.제한사항갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다...
문제 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 입출력 예 해결 방법 소수를 판별하는 함수를 미리 만들어놓는다. permutation 함수를 이용해서 순열을 만든다. 루프를 돌며 소수인지 판별한다. 코드 from itertools import permutations def isPrime(number): if number < 2: return False else: for i in range(2, number): if number % i == 0: retur..
