algospot 썸네일형 리스트형 [python] algospot FIRETRUCK 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 �� algospot.com 문제풀이 이 문제는 소방서에서 불난 지점까지의 최단 거리들의 합을 구하는 문제이다. 소방서의 개수가 최대 1000개이기 때문에 모든 소방서에서 최단경로 알고리즘을 돌린 뒤 최단 거리를 찾으면 시간 초과가 발생한다. 다익스트라 알고리즘을 한 번만 돌려 풀 수 있는 방법을 생각해야 한다. 이 문제의 핵심은 모든 소방서들은 최단 거리가 .. 더보기 [python] algospot SORTGAME 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com 문제풀이 문제에서 입력값으로 들어오는 최대 수열의 길이가 8이다. 이떄 만들어질 수 있는 모든 경우의 수는 8! = 4만이다. 가능한 경우의 수가 작기 떄문에 BFS를 통해 문제를 해결할 수 있다. (시간복잡도는?) 모든 가능한 수열을 정점으로 하고 뒤집는 연산을 통해 만들어질 수 있는 수열들은 간선으로 이어 그래프를 만들.. 더보기 [python] algospot WORDCHAIN 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 � algospot.com 문제풀이 이 문제의 핵심은 그래프를 어떤 식으로 만드느냐에 있다. 1. 정점이 각각의 단어들이 되고, 끝말잇기가 가능한 단어들끼리 잇는 방법이 있고, 2. 정점을 각 단어의 시작 알파벳과 끝 알파벳으로 두고 간선을 시작 알파벳에서 끝 알파벳 방향으로 잇는 방법이 있다. 1번 방법을 이용해서 풀려면 모든 정점을 한 번씩만 지나는 경로를 .. 더보기 [python] algospot RUNNINGMEDIAN 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN algospot.com :: RUNNINGMEDIAN 변화하는 중간값 문제 정보 문제 한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때 algospot.com 문제풀이 수열의 길이가 최대 20만이기 때문에 매번 새로운 숫자가 들어왔을 때 중간값을 구하는 방법으로는 시간 안에 해결할 수 없다. O(nlogn)이나 O(logn)에 해결할 수 있는 방법이 필요하다. 수열에 있는 숫자들은 모두 한 번씩은 사용해야 하기 때문에 n이 나올 수밖에 없다고 생각했고, 숫.. 더보기 [python] algospot TRAVERSAL 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/TRAVERSAL algospot.com :: TRAVERSAL 트리 순회 순서 변경 문제 정보 문제 트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 �� algospot.com 문제풀이 전위 순회식과 중위 순회식을 이용해 후위 순회식을 만드는 코드를 작성해야한다. 순회식에는 각각 특성이 있는데, 전위 순회식은 루트와 왼쪽 서브트리, 오른쪽 서브트리 중 루트를 먼저 방문하고, 중위 순회식은 왼쪽 서브트리를 먼저 방문하고 루트를 방문하게 된다. 순회식은 재귀적으로 돌며 매 순간 루트, 왼쪽 서브트리, 오른쪽 서브.. 더보기 [python] algospot ITES 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/ITES algospot.com :: ITES 외계 신호 분석 문제 정보 문제 수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,10000 algospot.com 문제풀이 문제 입력을 보면 최대 5000만개이다. 10000 이하의 정수 5000만개를 모두 저장하려면 64KB라는 메모리 제한에 걸리게 된다. 이 문제는 전체 입력값을 모두 보며 처리하는 것이 아닌 순간순간 필요한 입력값의 일부만 보며 처리하는 알고리즘을 짜야한다. 부분 수열은 전체 수열에서 연속되어 있어야 한다. [1,4,2,1,4,3.. 더보기 [python] algospot POLY 문제풀이 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고 하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. n개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작성하세요. -> 문제 링크 : https://algospot.com/judge/problem/read/POLY algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 문제풀이 문제에서 .. 더보기 [python] algospot SNAIL 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요. -> 문제 링크 : https://algospot.com/judge/problem/read/SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 � algos.. 더보기 이전 1 2 3 다음