본문 바로가기

전체 글137

[python] 어항 정리 - 23291번 빡구현 문제이다 시간복잡도를 생각하지 않아도 되는 여유로운 문제여서 특별한 자료구조를 따로 사용하지는 않고 배열로만 풀었다. 어항 뒤집기 할때가 구현하기 빡세고, 물고기 수 비교해서 옮겨담을 때는 아래와 오른쪽만 비교해줘서 계산해주면 된다. (위랑 왼쪽을 같이 고려해주면 중복때문에 복잡해짐) 깊은복사를 위해 copy모듈을 가져와 사용했다. 파이썬의 슬라이싱 [ : ] 을 이용하면 단순한 1중배열에 경우에 한하여 깊은복사처럼 사용할 수 있지만, 2중배열부터 내부 배열의 주소를 얕은 복사해버리기 때문에 deepcopy를 사용하는 것을 추천한다. import copy n,k = map(int,input().split()) fishbowl = list(map(int,input().split())) def jug.. 2022. 12. 14.
[python] 슬라이싱을 이용한 copy [:]을 이용한 복사는 깊은 복사라고 오해하기 쉽다 파이썬 튜터(https://pythontutor.com/python-debugger.html#mode=edit)를 이용하여 2중 배열을 복사하였다. 2중 배열의 외부는 주소가 따로 표시되어 깊은 복사처럼 사용을 할 수 있는데 내부의 2중배열부분은 같은 주소를 참조하는 것을 볼 수 있다. 따라서 원본 배열과 복사한 배열에 각각 append를 했을 때 같은 주소로 값이 각각 들어가는 것을 확인할 수 있다. 2022. 12. 14.
[python] 별꽃의 세레나데 (Easy) - 26217번 출력값이 하나로 정해지지 않고 범위에만 들어가면 정답으로 되는 확률 문제이다. 입력값에 따라 결과가 어떻게 나오는지 적어보면 간단한 일반화된 공식을 찾을 수 있다. 2 -> 2/2 + 2/1 = 3 96 -> 96/96 + 96/95 + ... + 96/1 = 494.08...... from fractions import Fraction n = int(input()) numerator = [n for _ in range(n)] denominator = [i for i in range(n,0,-1)] result = 0 for i in range(n): result+=Fraction(numerator[i],denominator[i]) print(float(result)) 2022. 12. 13.
눈 치우기 - 26215번 그리디로 해결하였다. while문을 이용한 무한루프로 눈을 효율적으로 치우는데 결과값이 1440을 넘어가는순간 break를 걸고 -1을 출력한다. 눈이 많이 쌓인 순서대로 정렬해준 뒤 효율적으로 눈을 치워주면 된다. n = int(input()) house=list(map(int,input().split())) house.sort() house = house[::-1] result = 0 while True: if result > 1440: result = -1 break if n>1: result+=house[1] house[0]-=house[1] house.pop(1) n-=1 if house[0] == 0: house.pop(0) n-=1 house.sort() house = house[::-1] .. 2022. 12. 12.
평범한 배낭 - 12865번 동적계획법으로 해결할 수 있는 문제이다. 배낭에 담을 물건을 쪼깨어 일부분만 담을 수 있다면 그리디로 풀 수 있지만, 그렇지 않기 때문에 동적계획법을 써줬다. 만약 가방의 무게가 20이고, 들어갈 수 있는 물건 5개가 다음과 같다면, 무게, 가치 2 3 3 4 4 8 5 8 9 10 동적계획법의 표현결과는 다음과 같다. n,k = map(int,input().split()) jewels=[[0,0]] for i in range(n): inn = list(map(int,input().split())) jewels.append(inn) dp = [[0]*(k+1) for i in range(n+1)] for gem in range(1, n+1): for bag_weight in range(1, k+1): i.. 2022. 12. 10.
출제비 재분배 - 26145번 출제자들이 돈을 받고 검수자들은 받지 못한다. 출제자들은 돈을 받고나서 나머지 모든 사람들에게 돈을 나눠준다. 각 사람들 수만큼 배열을 만들고, 들어가고 나오는 돈을 계산해준다. import sys n,m = map(int,input().split()) money = list(map(int,input().split())) total_money = [0 for _ in range(n+m)] for i in range(n): inn = list(map(int,sys.stdin.readline().split())) money[i] -= sum(inn) for j in range(n+m): total_money[j] += inn[j] for i in range(n): total_money[i] += money[.. 2022. 12. 10.
큐빙 - 5373번 빡구현 문제이다. 시간복잡도 생각 안하고 가장 단순한 방식으로 노가다로 풀었다. 50%에서 자꾸 틀렸는데, 2일동안 답을 찾기 위해 디버깅해본 결과 출력 시 join을 안해주었다. 출력 양식에 띄어쓰기를 포함하지 않고 딱 붙여서 출력해야한다. 직접 테스트 해볼 때, 만들어둔 show2함수와 https://rubiks-cube-solver.com/ko/에서 비교해보며 오답을 찾아내었다. 모든 오류를 확인해볼수 있는 반례는 1 12 F- R- U- B- L- D- F+ R+ U+ B+ L+ D+ 이다. 모든 면을 전개도처럼 펼쳐서 일일이 확인해보면 어디서 틀렸는지 확인할 수 있다. 위 반례의 답은 직접 구해보길 바란다. global up, front, right, left, back, down up = [[.. 2022. 12. 8.
Identify, Sort, Index, Solve - 26150번 람다식을 이용해 정렬해주는 것이 관건이다. import sys n = int(input()) arr = [] for _ in range(n): arr.append(list(sys.stdin.readline().split())) for i in range(n): arr[i][1] = int(arr[i][1]) arr.sort(key = lambda x:x[1]) for i in range(n): idx = int(arr[i][2]) print(arr[i][0][idx-1].upper(),end='') 2022. 12. 4.
케빈 베이컨의 6단계 법칙 - 1389번 플로이드 워셜 알고리즘으로 풀었다. 그래프에 친구들 간 관계의 비용을 계산한 후, 저장한다. 그래프에서 각 사람별로 친구들간 관계의 비용이 가장 낮은 사람을 구해준다. import sys from copy import deepcopy from math import inf n, m = map(int,input().split()) graph = [[inf]*n for _ in range(n)] for i in range(m): a,b = map(int,sys.stdin.readline().split()) graph[a-1][b-1] = 1 graph[b-1][a-1] = 1 def floyd(graph): d = deepcopy(graph) for a in range(n): for b in range(n):.. 2022. 11. 30.
경로 찾기 - 11403 플로이드 워셜 알고리즘으로 해결하였다. 마지막에 inf 인 것들은 0으로 바꿔주고 나머지들은 모두 1로 바꿔주고 출력하였다. import sys from copy import deepcopy from math import inf n = int(input()) graph = [[inf]*n for _ in range(n)] for i in range(n): inn = list(map(int,sys.stdin.readline().split())) for j in range(n): if inn[j]: graph[i][j] = 1 def floyd(graph): d = deepcopy(graph) for a in range(n): for b in range(n): for c in range(n): d[b][c].. 2022. 11. 30.
플로이드 - 11404번 동적 계획법 방식의 플로이드 워셜 알고리즘을 사용하는 문제이다. 그래프의 모든 정점에서 다른 정점들 까지의 최소 비용을 구해야한다. 갈 수 없는 곳은 math 모듈의 inf 무한대를 사용하여 표현해주고 마지막에 출력할 때 0으로 바꿔준다. 원본 그래프를 손상시키지 않기 위해 deepcopy를 사용했다. import sys from copy import deepcopy from math import inf n = int(input()) m = int(input()) graph = [[inf]*(n) for _ in range(n)] for i in range(m): a,b,c = map(int,sys.stdin.readline().split()) if graph[a-1][b-1]==inf: graph[a-.. 2022. 11. 29.
듣보잡 - 1764번 시간을 줄이기 위해 집합 자료형을 사용해준다. 마지막에 결과를 사전순으로 출력해야하기 때문에 리스트로 바꿔준 뒤, 출력해준다. import sys a,b = map(int,input().split()) arr=set() result=set() for _ in range(a): inn = sys.stdin.readline().strip() arr.add(inn) for _ in range(b): inn = sys.stdin.readline().strip() if inn in arr: result.add(inn) print(len(result)) result = list(result) result.sort() for i in result: print(i) 2022. 11. 14.

티스토리툴바