1. 문제 출처 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 2. 풀이 그냥 구현을 해보자 # 시간 초과 N = int(input()) home_list = list(map(int,input().split())) def solution(): # 최소길이 구하기 min_dis = total_distance(home_list[0]) antenna = home_list[0] for idx in range(1,N): if min_dis > total_distance(ho..
1. 문제 출처 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 2. 풀이 이 문제는 list.sort()대해 물어보는 문제인 것 같다. sort 함수에는 어떤 값을 기준으로 정렬한 것인지 key 파라미터를 통해 정할수 있다. N = int(input()) student_list = [] for _ in range(N): student_list.append(input().split()) # lambda통해 함수를 정의한다...
1. 문제 출처 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 2. 풀이 해당 문제는 1 ->2->....->K 순으로 바이러스가 움직이기 때문에 2차원 리스트을 queue처럼 이용하고자 하였으나, 그것보다 temp라는 3차원 배열에 코드와 같이 index + 1 과 같은 바이러스 번호를 가진 좌표를 모으고 2차원으로 펴준 queue를 생성한다. 그러면 자동적으로 바이러스 번호가 작은 순으로 나오게 된다. 예시)..
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..
