문제 https://www.acmicpc.net/problem/1700 문제기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,키보드헤어드라이기핸드폰 충전기디지털 카메라 충전기키보드헤어드라이기키보드, 헤어드라이기,..
Koala - 18기
문제 https://www.acmicpc.net/problem/1926 Algorithm1. dfs 알고리즘을 이용해 한 그림 즉 1이 이어져있는 것을 찾는다.2. 찾는 과정에서 정수 e를 전역변수로 두고 그림의 크기를 기록해 가장 큰 그림의 크기를 구한다.3. dfs 알고리즘을 통해 그림을 하나 찾을 때 마다 정수 cnt를 활용해 그림의 개수를 구한다. Codeimport sysinput = sys.stdin.readlinesys.setrecursionlimit(10 ** 8)def dfs(x, y): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] global e for i in range(4): nx = x + dx[i] ny =..
문제 & 링크https://www.acmicpc.net/problem/1294 풀이1. 각 문자열을 원하는 대로 쪼갤 수 있기에, 각 문자열(string)의 맨 앞 문자(char) 끼리 비교하여 사전순으로 가장 앞서는 문자 하나를 가져온다.2. 사전순으로 가장 앞서는 문자가 여러 문자열에 있을 경우 그 다음인 두 번째 문자도 고려해야 한다. - 문자열을 쪼개되, 조각의 순서는 유지해야 하는 조건 - 문제의 출력 조건을 만족하기 위해서 뒤의 문자도 고려하여 해당 문자열의 맨 앞 문자 추출 ex) CB, CA이렇게 두 문자열이 있을 경우 맨 앞 문자는 C로 사전순으로 같다. 그러면 두 번째 문자인 A와 B를 비교하여 두 번째 문자열에서 맨 앞 문자를 추출해야 한다. (이 경우 최종 결과 CACB, 만약..
문제 & 링크https://www.acmicpc.net/problem/13911 풀이1. 음의 가중치가 없는 그래프에서 최단 거리를 구해야 하기에 다익스트라 알고리즘을 사용한다.2. x세권인지 아닌지 판단하는 값이 주어지기에, 다익스트라 알고리즘에서 우선순위 큐에 넣을 때 이 값을 고려한다.3. 모든 집에서 다익스트라를 수행 할 경우 x세권이 아님에도 탐색 대상이 되는 경우가 있기에 비효율적이다.4. 맥도날드 or 스타벅스에서 다익스트라를 수행하여 x세권인 집만 탐색을 한다.5. 모든 맥도날드 or 스타벅스에서 다익스트라를 한 번씩 수행하면, 최악의 경우 9,999개의 노드에 대한 다익스트라 수행으로 시간 초과가 나게 된다. 6. 가상 노드라는 개념을 추가하여 모든 맥도날드의 시작점을 하나로 묶고, 모든..
문제 & 링크https://www.acmicpc.net/problem/1422 풀이1. K개의 수를 적어도 한 번씩 사용해야 하기에, 모든 수를 이어 붙여서 가장 큰 수를 구하는 문제와 유사하다.2. N > K일 경우 숫자를 중복으로 사용하여 추가할 수 있는데, 자릿수와 값을 생각하면 무조건 K개의 수 중 큰 수를 N - K 만큼 붙여야 한다.3. 숫자를 string으로 바꾸어 사전 순으로 가장 앞서는 수를 구한다. 숫자를 그냥 넣게 될 경우, 아래와 같은 예시가 존재할 수 있다. ex) K = { 31, 34 } -> 사전 순으로 정렬: 34, 31 -> 결과: 3431 (기댓값: 3431) ex) K = { 3, 34 } -> 사전 순으로 정렬: 34, 3 -> 결과: 343 (기댓값: 343) ..
문제 https://www.acmicpc.net/problem/5972문제농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]..
문제 https://www.acmicpc.net/problem/12840 문제창용이는 여름을 맞이하여 ‘정창용’ 이름이 쓰인 한정판 섬머 에디션 시계를 구입했다. 왠지 오늘은 001도 가고 싶지 않고 시계를 가지고 놀고만 싶다. 우린 방에 있는 창용이가 시계를 가지고 뭘 하는지 궁금하기만 하다. 창용이는 시계의 건전지를 분리했기 때문에 시계는 시간이 흐르지 않는다.창용이는 앞으로 시계를 돌리기도 하고 뒤로 시계를 돌리기도 한다. 입력으로는 초기 현재 시간이 주어지고 q개의 쿼리가 주어진다.한 쿼리는 T로 시작한다. (1 ≤ T ≤ 3, 0 ≤ c ≤ 10,000,000)T가 1일 때는 c를 입력으로 받아와서, 시계를 앞으로 c초 돌린다.T가 2일 때는 c를 입력으로 받아와서, 시계를 뒤로 c초 돌린다.T..
문제문제서쪽나라에서 특수훈련을 받은 정은이는 동쪽나라로 침투를 하게 되었다. 뛰어난 스파이였던 정은이는 동쪽나라의 정보를 입수하게 되었고 정보를 안전하게 서쪽나라로 전달하기 위해 아핀 암호(Affine Cipher)를 이용하기로 하였다.아핀 암호는 다음과 같은 식을 통해 구할 수 있다.E(X) = (aX + b) mod 26A부터 Z까지의 알파벳을 차례대로 0, 1, 2, ... , 25 라고 하자. a = 3이고, b = 1인 경우에 알파벳 A를 아핀 암호식에 대입하면 E(0) = (3 × 0 + 1) mod 26 이 되어 암호화된 결과는 B가 된다.a와 b, 그리고 알파벳 대문자로만 구성된 평문이 주어졌을 때, 이를 암호문으로 치환하는 프로그램을 작성하라.입력입력의 첫 줄에는 테스트 케이스의 개수 T..
6186번: Best Grass그래프 탐색 기본 문제이다.주변 풀들을 한 묶음으로 여기도록 세야한다.import sysinput = sys.stdin.readlinefrom collections import dequedef main(): r, c = map(int,input().split()) arr = [['.' for i in range(c+2)]] for _ in range(r): arr.append(['.']+list(input().strip())+['.']) arr.append(['.' for i in range(c+2)]) visit = [[0 for i in range(c+2)] for j in range(r+2)] ans = 0 def g..
https://www.acmicpc.net/problem/2164 import sysinput = sys.stdin.readline from collections import dequedef main(): n = int(input()) arr = deque([i for i in range(n,0,-1)]) while (1): if len(arr)==1: break arr.pop() x = arr.pop() arr.appendleft(x) print(arr[0])if __name__ == "__main__": main() 생각하지 않고 실제로 돌려봐도 시간 초과 안뜨려나? 했는데 정말 안 떴다. 2초라서 시도해보았다.
문제 https://www.acmicpc.net/problem/2566입력첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다.출력첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. Algorithm2차원 리스트상에서 최댓값과 그 인덱스를 찾으라는 문제지만 1차원 리스트에서 더 쉽기에 1차원 리스트로 받는다.1차원 리스트에서 2차원으로 받았을 때의 인덱스를 찾기 위해 1차원 리스트의 인덱스에서 9로 나눈 값과 나머지를 이용한 Codeimport sysfrom operator import indexlst = []fo..
문제 https://www.acmicpc.net/problem/2616문제기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌..
