algospot

소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 www.algospot.com 다익스트라 문제 설명 더보기 각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다. Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다! -> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자 우선순위 큐에서 항상 가장 적은 시간이 소요되..

Sorting Game (SORTGAME)

algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com BFS, 최단거리 처음보는 유형의 문제. 신기한 문제 지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데 이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다. 1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다. ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상..

단어 제한 끝말잇기 (WORDCHAIN)

algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 www.algospot.com DFS, 오일러 서킷, 오일러 트레일 1. 문제 해결 아이디어 끝말잇기에 사용되는 단어들이 주어진다. 주어진 단어 모두를 사용해서 끝말잇기를 만들면 된다. -> 오일러 회로임을 알 수 있다. 단어를 모두 사용해서 다시 시작점으로 돌아올 수도 있고, 시작점이 아닌 지점에서 끝날 수도 있다. 다시 시작점으로 돌아오는 경우는 오일러 서킷이라고 할 수 있다. 모든 간선을 한 번씩 통과하지만 시작점이 아닌 다른 정점에서 끝나는 경로를 오일러 트레일 이라..