Python 썸네일형 리스트형 [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] baekjoon 11266 : 단절점 문제 -> 문제 링크 : https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 문제풀이 단절점이란 해당 정점이 사라졌을 때 그래프가 여러 개의 그래프로 나눠지는 정점이다. dfs를 활용하면 단절점을 쉽게 찾을 수 있다. 단절점 찾기 알고리즘의 핵심은 dfs를 통해 먼저 방문한 순서대로 정점에 순서를 매길 때 현재 정점 이후에 발견되는 정점들이 방문할 수 있는 정점의 최소 순서가 현재 정점의 순서보다 크거나 같으면 단절점이.. 더보기 [python] algospot DICTIONARY5 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/DICTIONARY algospot.com :: DICTIONARY 고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 algospot.com 문제풀이 문자열이 여러 개 입력될 때 직전에 입력된 문자열과 현재 입력된 문자열을 비교함으로써 문자 간의 순서를 확정 지을 수 있다. gg와 kia가 순서대로 들어온다면 g는 k보다 순서상 항상 앞에 있는 문자이다. 이는 방향 그래프 g -> k로 나타낼 수 있고 모든 문자열에 대해서 그래프로 매핑시킨 뒤 위상정렬을 하면 문자들의 순서를.. 더보기 [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 Wildcard 문제풀이 문제 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다. 예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다. 와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오. 문제풀이 이 문제에서 핵심은 *이다. 와일드카드 *가 나왔을 때 이 문자가 파일 이름에서 몇개.. 더보기 이전 1 2 다음