본문 바로가기
반응형

전체 글288

[BOJ][Python]16395번 풀이 https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net t = [[0 for _ in range(31)] for _ in range(31)] t[1][1] = 1 for i in range(2,31): for j in range(1,31): t[i][j] = t[i-1][j-1] + t[i-1][j] n,k = map(int, input().split()) print(t[n][k]) 예전에 이항 계수 문제를 dp가 아닌 방법으로 풀었던 적.. 2022. 6. 3.
[BOJ][Python]1764번 풀이 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net import sys ssr = sys.stdin.readline n,m = map(int, ssr().split()) d = {ssr():i for i in range(n)} name = [] for _ in range(m): a = ssr() if a in d.keys(): name.append(a.rstrip()) print(len(name)) name.sort() for i in range.. 2022. 6. 3.
[CS]손실 압축, 무손실 압축 압축이라는 말은 일상생활에서 정말 많이 접할 수 있는 단어입니다. 초등학교 과학 시간에 피스톤이 연결된 밀폐용기에 마시멜로우를 넣고 가압을 하거나 감압을 하면서 압축이란 말을 들어보셨을 거고, 컴퓨터를 사용하다 보면 알집, 반디집 등의 프로그램을 이용해서 저장 공간의 효율을 위해 파일을 압축하기도 하죠. 오늘은 컴퓨터를 이용하면서 접하는 압축에 대해서 얘기를 좀 해볼까 합니다. 압축이란? 압축(壓 : 누를 압, 縮 : 줄일 축)의 사전적 정의는 '물질 따위에 압력을 가하여 그 부피를 줄임' 이라고 나옵니다. 좀 더 글의 내용과 어울릴 수 있도록 범용적으로 다시 적어보면 '무언가에 외부적 요인을 가하여 그 크기를 줄임' 정도로 설명하면 이후에 나올 내용과 잘 어울릴 것 같습니다. 컴퓨터 분야에서 압축을 하.. 2022. 6. 3.
[BOJ][Python]14916번 풀이 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net t = [-1 for _ in range(100001)] t[2],t[4],t[5],t[6],t[7],t[8] = 1,2,1,3,2,4 for i in range(9,100001): t[i] = min((t[i-2]+t[2]),(t[i-5]+t[5])) print(t[int(input())]) 이번에도 평이한 난이도의 문제입니다만 생각을 어떻게 하는지에 따라 결론에 다다르는 시간이 다를 것 같네요. 일단 가장 적은 갯수의 동전을 반환하기 위해서는 뭐가 됐든 숫자가 늘 때 1개만 늘어나는게 가장 바람직한 일이죠. 따라.. 2022. 6. 2.
[BOJ][Python]1620번 풀이 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net import sys input = sys.stdin.readline n,m = map(int, input().split()) d = {i:input().rstrip() for i in range(1,n+1)} t = dict(map(reversed, d.items())) for _ in range(m): a = input().rstrip() if not a[0].isd.. 2022. 6. 2.
[BOJ][Python]5089번 정리 https://www.acmicpc.net/problem/5089 5089번: Travelling Salesman Output consists of a single line for each week. It contains the word Week, followed by a space, followed by the week number, the first week being 1, followed by a space, followed by the actual number of towns to be visited, duplicates having been removed. www.acmicpc.net cnt = 0 while 1: cnt += 1 n = int(input()) if n == 0: break t .. 2022. 6. 1.
[BOJ][Python]13301번 풀이 https://www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net n = int(input()) if n == 1: print(4) else: t = [0 for _ in range(81)] t[0],t[1] = 1,1 for i in range(2,81): t[i] = t[i-1]+t[i-2] print(2*t[n-1]+2*(t[n-1]+t[n-2])) 그렇게 어려운 문제는 아닙니다. n=1인 경우에 점화식이 적용되지 않는 점을 잊지 마시구요. 피보나치는 정말 .. 2022. 6. 1.
[BOJ][Python]18679번 풀이 https://www.acmicpc.net/problem/18679 18679번: Banana The first line of input will contain a single integer N, the number of words in the dictionary (1 ≤ N ≤ 100). The following N lines will each contain a sentence of the format x = y where x is an English word and y is a Minionese word. The next line wil www.acmicpc.net n = int(input()) dict = {} for _ in range(n): a,b = input().split(' = ') dic.. 2022. 5. 31.
[BOJ][Python]9625번 풀이 https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net n = int(input()) t = [[] for _ in range(n+1)] t[0] = [1,0] for i in range(1,n+1): t[i] = [t[i-1][1],t[i-1][0]+t[i-1][1]] print(*t[n]) 이번 문제도 쉽습니다. 오히려 점화식을 찾기 위해서 하나씩 쓰다보면 헷갈릴 수 있는 문제라고 생각해요. A는 B로 바뀌고 B는 BA로 바뀌기 때문에 B는 갯수가 줄.. 2022. 5. 30.
[BOJ][Python]11723번 풀이 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net import sys input = sys.stdin.readline S = set([]) m = int(input()) for _ in range(m): line = input().split() if len(line)==1: if line[0] == 'all': S = set([i for i in range(1,21)]) else: S.clear() else: if line[0] == 'add': S.add(int(line[1])).. 2022. 5. 29.
반응형

티스토리툴바