네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2. 풀이과정 n의 경우의 수 = (n-1에서 1x2블럭을 추가했을 때) + (n-2에서 2x1블럭 2개 혹은 2x2블럭 1개를 추가했을 때) 정리하면, f(n) = f(n-1) + f(n-2) * 2로 수식을 나타낼 수 있다. n = int(input()) x, y = 1, 3 for i in range(n-2): temp = y y = y + x*2 x = temp if n == 1: print(x) else: ..

1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 과정 n = int(input()) graph = [[*map(int, input().split())] for _ in range(n)] shark = 2 dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]#위왼오아 #먹을 물고기 찾기 def find(n1, n2): q = [] q.append((n1, n2, 0)) visited = [[0 fo..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이 과정 일반 DFS 문제와 다른점은 벽을 부수고 이미 지나간 경우보다 벽을 안 부수고 돌아서 다시 지나갈 때가 더 길지만 이 값도 저장해두어야 한다. 나중에 나온 벽을 부수고 갔을 때가 최단 경로가 될 수 있기 때문이다. 아래는 추가적으로 테스트 케이스를 만든 것이다. 입력 : 6 5 00000 11110 00000 01111 01011 00000 출력..

1. 문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 2. 풀이 과정 1. 주어진 문자열이 "AFCA"이라면 A = 1000+1, F = 100, C = 10으로 자릿수만큼 수를 더해준다. 다음 문자열을 읽을 때는 이 값에 누적으로 더해주면 된다. 2. 누적으로 더한 수들을 정렬해서, 제일 큰 수를 가진 알파벳부터 9 => 8 => 7 ... 순으로 할당하는 것이 제일 큰 수를 만들 수 있다. 따라서 출력값은 (해당 알파벳이 가진 수..

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 풀이 과정 현재 위치에서 선택할 수 있는 방안은 2가지다. 1) 이전 값에 연속해서 더하기 2) reset하고 현재값부터 다시 시작하기 따라서, 현재값과 연속해서 더한 값 중에 큰 수를 선택해나간다. n = int(input()) arr = list(map(int, input().split())) for i in range(1, len(arr)): arr[i] = max(arr[i], arr..

1. 문제 2. 풀이 과정 Python 정규 표현식을 이용하여 parsing을 하였다. 여기서 사용된 정규표현식만 살펴보자면 아래와 같다. import re #1. findall text = "hello my id is a1" #문자로 이루어진 문자 1개이상으로 구성된 것 모두 찾기 test = re.findall(r'[a-zA-Z]+',text) print(test) #['hello', 'my', 'id', 'is', 'a'] #2. search text = '' #다음 패턴으로 이루어진 문장 하나 찾기 #[^>]* = >이 아닌 것 0개 이상으로 구성된 것 #[\S]* = 공백이 아닌 것 0개 이상으로 구성된 것 url_str = re.search(r']*content="https://([\S]*)"..

1. 문제 2. 풀이 과정 방법 1) 배열로 tree를 구성한 후, 순회 import sys sys.setrecursionlimit(10**6) class Node(object): def __init__(self, i, data_set): self.left_idx = -1 self.idx = i self.right_idx = -1 self.num = data_set[0] self.x = data_set[1] self.y = data_set[2] def pre_order(t, i, result): if i == -1: return result.append(t[i].num) pre_order(t, t[i].left_idx, result)#왼 pre_order(t, t[i].right_idx, result)#..

1. 문제 2. 풀이 과정 from collections import Counter def solution(food_times, k): food_num = len(food_times) #현재 음식 개수 counting = Counter(food_times) #시간별 음식 개수 time_list = list(counting.keys()) #시간 목록 time_list.sort() pre_time = 0 for time in time_list: if k

1. 문제 2. 풀이 과정 from itertools import combinations def solution(relation): row = len(relation) col = len(relation[0]) answer = set() for i in range(1, col+1): for com in combinations(range(col), i): #속성들의 조합 #최소성 검사 minimality = True for a_tup in answer: if set(a_tup) & set(com) == set(a_tup): minimality = False break #최소성을 만족, 유일성 검사 if minimality: temp = set() for k in range(row): temp.add(tupl..

1. 문제 2. 풀이 과정 def solution(N, stages): rate = [0]*(N+2) total = len(stages) #도전자 수 for stage in stages: rate[stage] += 1 result = [] for i, r in enumerate(rate[1:N+1], start = 1): if total == 0: result.append((0, i)) continue temp = rate[i]/total #실패율 total -= rate[i] #스테이지에 도달한 플레이어 수 result.append((temp, i)) return list(map(lambda x:x[1], sorted(result, key = lambda x:x[0], reverse = True)))