파이썬 썸네일형 리스트형 [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] 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] algospot WORDCHAIN 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 � algospot.com 문제풀이 이 문제의 핵심은 그래프를 어떤 식으로 만드느냐에 있다. 1. 정점이 각각의 단어들이 되고, 끝말잇기가 가능한 단어들끼리 잇는 방법이 있고, 2. 정점을 각 단어의 시작 알파벳과 끝 알파벳으로 두고 간선을 시작 알파벳에서 끝 알파벳 방향으로 잇는 방법이 있다. 1번 방법을 이용해서 풀려면 모든 정점을 한 번씩만 지나는 경로를 .. 더보기 [python] baekjoon 1202 보석 도둑 문제 -> 문제 링크 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 문제풀이 가방의 개수와 보석의 개수 모두 30만으로 O(logN) 이하의 시간 복잡도로 문제를 해결해야 한다. 가방에 들어가는 보석을 선택하는 문제이든 보석을 담을 수 있는 가방을 선택하는 문제이든 시간이 O(logN)으로 찾을 수 있어야 문제를 해결할 수 있다. 기준을 가방으로 잡고, 현재 가방에 들어갈 수 있는 보석 중 가장 비싼 보석을 넣는 방식으로 문제를 해.. 더보기 [python] baekjoon 3111 검열 문제 -> 문제 링크 : https://www.acmicpc.net/problem/3111 3111번: 검열 문제 김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다. 상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다. T에 A가 없으면 알고� www.acmicpc.net 문제풀이 문자열이 최대 30만자이기 때문에 문자열 T에 있는 문자들을 한번씩만 탐색하면서 문제를 해결해야 한다고 생각했다. 문자열 T를 앞에서부터 접근하는 리스트 front와 맨끝에서부터 접근하는 리스트 back을 만들고 한칸씩 이동하면서 새로운 문자가 들어올 때 마다 리스트에 문자열 A가 만들어지는지 검사하면서 나아간다. 만약 리스트 front나 back에 문자열 A가 만들어지면.. 더보기 [python] baekjoon 2879 풀이 문제 문제 링크 -> https://www.acmicpc.net/problem/2879 2879번: 코딩은 예쁘게 문제 백준이는 한 작은 회사에 취직했다. 이 회사에서 백준이는 소스 코드의 뒤죽박죽인 인덴트를 고치고 있다. 인덴트는 각 줄을 탭 키를 이용해 들여 쓰는 것을 말한다. 다행히 백준이가 사용� www.acmicpc.net 문제풀이 문제를 보면 최대한 많은 줄에 탭을 추가하거나 삭제해야 최솟값으로 일을 끝낼 수 있다.각 줄에서 어떤 행동을 해야하는지 알아내기 위해서 첫째 줄을 둘째 줄에 있는 값으로 빼주면 각 줄에서 해야할 행동을 구할 수 있다.양수가 있으면 탭을 추가해야하는 부분이고 음수가 있으면 제거해야하는 부분이다. 반복문을 통해 첫 줄부터 끝까지 탐색해간다. 만약 현재 줄이 이전 줄과 같.. 더보기 [python] algospot Lunchbox 문제풀이 문제 -> 문제 링크 : https://www.algospot.com/judge/problem/read/LUNCHBOX algospot.com :: LUNCHBOX Microwaving Lunch Boxes 문제 정보 문제 After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp. He contacted the famous packed lunch company "Doosot" to prepare N lun www.algospot.com 문제풀이 이 문제에서 전자레인지로 도시락을 데우는 데 걸리는 시간은 정해져있다... 더보기 이전 1 2 다음