본문 바로가기

알고리즘

[python] algospot FIRETRUCK 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 �� algospot.com 문제풀이 이 문제는 소방서에서 불난 지점까지의 최단 거리들의 합을 구하는 문제이다. 소방서의 개수가 최대 1000개이기 때문에 모든 소방서에서 최단경로 알고리즘을 돌린 뒤 최단 거리를 찾으면 시간 초과가 발생한다. 다익스트라 알고리즘을 한 번만 돌려 풀 수 있는 방법을 생각해야 한다. 이 문제의 핵심은 모든 소방서들은 최단 거리가 .. 더보기
[python] baekjoon 2549 : 루빅의 사각형 문제 -> 문제 링크 : https://www.acmicpc.net/problem/2549 2549번: 루빅의 사각형 첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 www.acmicpc.net 문제풀이 입력값은 2차원 배열이지만 1차원 배열로 만들어 16자리의 수열을 정렬시키는 문제로 풀면 된다. 이때 숫자를 배열보다는 문자열로 만드는 게 딕셔너리를 사용할 때 시간이 적게 든다. 하지만 10을 넘는 숫자가 있어 2차원 배열에서의 자리를 유추하기가 힘들다. 모든 숫자가 한 글자가 되도록 16진수의 수로 바꿔 표현하면 1차원 배열의 자리를 보고 2차원 배열을 .. 더보기
[python] algospot SORTGAME 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com 문제풀이 문제에서 입력값으로 들어오는 최대 수열의 길이가 8이다. 이떄 만들어질 수 있는 모든 경우의 수는 8! = 4만이다. 가능한 경우의 수가 작기 떄문에 BFS를 통해 문제를 해결할 수 있다. (시간복잡도는?) 모든 가능한 수열을 정점으로 하고 뒤집는 연산을 통해 만들어질 수 있는 수열들은 간선으로 이어 그래프를 만들.. 더보기
[python] baekjoon 11400 : 단절선 문제 -> 문제 링크 : https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 문제풀이 단절선은 제거했을 때 그래프가 여러 개로 나눠지는 간선을 의미한다. 단절선 문제를 해결하기 위해서는 트리의 부모, 자식의 개념을 이용하면 쉽다. dfs를 이용해 방문 순서대로 정점에 순서를 매긴다고 하자. 이때 자식의 정점 순서는 부모의 정점 순서 + 1이 된다. 이때 현재 간선이 없다고 가정하고, 자식 정점에서부터 접근 가능한 모든 .. 더보기
[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 WORDCHAIN 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 � algospot.com 문제풀이 이 문제의 핵심은 그래프를 어떤 식으로 만드느냐에 있다. 1. 정점이 각각의 단어들이 되고, 끝말잇기가 가능한 단어들끼리 잇는 방법이 있고, 2. 정점을 각 단어의 시작 알파벳과 끝 알파벳으로 두고 간선을 시작 알파벳에서 끝 알파벳 방향으로 잇는 방법이 있다. 1번 방법을 이용해서 풀려면 모든 정점을 한 번씩만 지나는 경로를 .. 더보기
[python] algospot DICTIONARY5 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/DICTIONARY algospot.com :: DICTIONARY 고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 algospot.com 문제풀이 문자열이 여러 개 입력될 때 직전에 입력된 문자열과 현재 입력된 문자열을 비교함으로써 문자 간의 순서를 확정 지을 수 있다. gg와 kia가 순서대로 들어온다면 g는 k보다 순서상 항상 앞에 있는 문자이다. 이는 방향 그래프 g -> k로 나타낼 수 있고 모든 문자열에 대해서 그래프로 매핑시킨 뒤 위상정렬을 하면 문자들의 순서를.. 더보기
[python] baekjoon 1202 보석 도둑 문제 -> 문제 링크 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 문제풀이 가방의 개수와 보석의 개수 모두 30만으로 O(logN) 이하의 시간 복잡도로 문제를 해결해야 한다. 가방에 들어가는 보석을 선택하는 문제이든 보석을 담을 수 있는 가방을 선택하는 문제이든 시간이 O(logN)으로 찾을 수 있어야 문제를 해결할 수 있다. 기준을 가방으로 잡고, 현재 가방에 들어갈 수 있는 보석 중 가장 비싼 보석을 넣는 방식으로 문제를 해.. 더보기

티스토리툴바