1. 문제 출처 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 2. 풀이 bfs(너비 우선 탐색)를 이용하여 구하였다. 제일 어려웠던점은 아이러니하게 알고리즘 구현이 아닌 시간 초과 문제 였다.처음에는 deque 대신 리스트에 pop()을 하는 형식으로 구현 하였으나 시간 초과가 발생하였다. 이를 deque 자료형을 불러와 popleft 를 대신 사용 하였더니 해결되었다..
1. 문제 출처 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 처음에는 다음과 같이 치킨집의 개수가 M개가 되는 모든 경우의 수를 재귀로 구하였다. 하지만 시간 초과 되었다... # 입력 받기 N,M = map(int, input().split()) city = [0 for _ in range(N)] result = [] for idx in range(N): city[idx] = list(map(int, inp..
1. 문제 출처 https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 2. 풀이 N = input() nums = [] for num in N: nums.append(int(num)) left = sum(nums[:int(len(nums)/2)]) right = sum(nums[int(len(nums)/2):]) if left == right: print("LUCKY") else: print("READY")
1. 문제 출처 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 크게는 브루트 포스를 이용하여 모든 경우의 수를 구한 다음에 가장 결과가 큰값을 출력한다. 문제는 벽을 세우는 과정인데 이는 dfs ,bfs 2가지로 해결 할 수 있다. (시간이 오래 걸리므로 python3가 아닌 pypy3 로 실행해야 시간 초과가 되지 않는다.) bfs import copy from collections import deque # 움직이는 방향 dy = [0,0,..
1. 문제 출처 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 2. 풀이 몸의 좌표 배열은 머리가 앞에서 추가되고 꼬리는 뒤에서 빠져야 하기 때문에 자료 구조를 덱으로 생각하고 사용 하였고방향 전환 배열은 먼저 추가한 데이터를 먼저 빼서 사용해야 하기 때문에 큐 라고 생각 하고 사용 하였다. # 필요한 변수 선언 및 초기화 size = int(input()) apple_num = int(input()) apple_list = [] body = [[0..
1. 문제 출처 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 2. 풀이 연속되는 0,1을 0001110011->0101다음과 같이 한자리수로 바꾸어 준다음 각각의 0과 1의 개수중 가장 작은 수를 print하면 정답이 된다. # 데이터 받기 data = input() def solution(S): # 키값이 "1","0"인 dict 만들기 num_dict = {"1":0, "0":0} # 처음 값에 따라 업데이트 num_dict.update..
1. 문제 출처 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 2. 풀이 자세한 풀이는 내일 import sys sys.setrecursionlimit(10**6) N = int(input()) W = int(input()) distance_list = [[-1 for _ in range(W)] for _ in range(W)] r = [] def min_distance(cop1,cop2): if (cop1 ==(W))..
1. 문제 출처 https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 2. 풀이 파이썬의 slice 기능을 이용하면 간단하게 해결할 수 있다. s = input() # 전체 문자열을 역순으로 한 것과 문자열이 일치하면 이미 팰린드롬 문자열 이므로 # 문자열의 길이를 출력한다. if s == s[::-1]: print(len(s)) # 아닌 경우 else: # 최악의 경우의 수는 마지막 문자를 기준으로 앞뒤를 같게 하는 경우 이므로 # 최대 문자열의 전체 ..
