문제 요약보드 게임에서 플레이어는 주사위를 굴려 1번 칸에서 100번 칸까지 이동해야 한다.사다리는 도착하면 더 높은 번호로 이동하고, 뱀은 더 낮은 번호로 이동하게 한다.100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 구한다. 풀이from collections import dequeimport sysinput = sys.stdin.readlinedef snakes_and_ladders(N, M, ladders, snakes): board = list(range(101)) # 보드의 각 칸 초기화 for start, end in ladders.items(): board[start] = end # 사다리 설정 for start, end in snakes.it..
분류 전체보기
문제 요약네 개의 명령어 D, S, L, R 가 있는 계산기두 정수 A, B가 주어졌을 때, A를 B로 바꾸는 최소한의 명령어 생성-> BFSBFS라는 건 어렵지 않게 생각해낼 수 있었는데.. 이 문제에서 가장 어려웠던 점은 시간 초과였다. 시간 초과 풀이from collections import dequedef D(n): return (2 * n) % 10000def S(n): return n - 1 if n != 0 else 9999def L(n): n = f"{n:04}" # 네 자릿수로 맞추기 return int(n[1:] + n[0])def R(n): n = f"{n:04}" # 네 자릿수로 맞추기 return int(n[-1] + n[:-1])def bfs(..
파이썬에서 이차원 리스트를 출력할 때, 각 행을 보기 좋게 출력하는 다양한 방법이 있다.이번 포스팅에서는 대표적인 5가지 방법을 정리해보려고 한다. 1. join과 map을 이용한 방법가장 많이 사용되는 방법 중 하나는 join과 map을 이용해 각 행을 문자열로 변환한 후 출력하는 것이다.for row in distances: print(' '.join(map(str, row)))map 함수는 리스트의 각 요소에 str 함수를 적용해 문자열로 변환하고, join 메서드는 이를 공백으로 구분하여 하나의 문자열로 합친다. 2. 언패킹 연산자 *를 이용한 방법파이썬의 print 함수는 여러 인수를 받을 때 기본적으로 공백으로 구분하여 출력한다. 이를 이용하면 보다 직관적으로 코드를 작성할 수 있다..
1. 정수 자릿수 맞추기정수의 자릿수를 맞추는 가장 일반적인 방법은 zfill 메서드, 포맷 문자열, 그리고 rjust 메서드를 사용하는 것이다. zfill 메서드zfill 메서드는 문자열의 왼쪽에 0을 추가하여 지정된 길이로 맞춘다.number = 42formatted_number = str(number).zfill(4)print(formatted_number) # 출력: 0042 포맷 문자열포맷 문자열을 사용하면 더 유연하게 숫자를 포맷할 수 있다. 예를 들어, 정수를 네 자리로 맞추려면 다음과 같이 한다.number = 42formatted_number = f"{number:04}"print(formatted_number) # 출력: 0042 rjust 메서드rjust 메서드는 문자열의 왼쪽에 ..
수학적 접근이 필요한 문제였다.문제에 주어진대로 단순히 브루트포스 탐색할 경우 시간, 메모리 초과가 났다. (아래에 틀린 코드 첨부) 발상우리가 구할 숫자를 R이라고 해보면R-x는 M으로 나누어 떨어지고, R-y는 N으로 나누어 떨어진다.즉 R은 M*p + x 또는 N*q + y이다. (p, q는 자연수)R의 초기값을 x로 선언하고 R값을 M만큼 증가시키면서 확인해보면 된다.(y로 선택할 시, 초기값 y, R값을 N만큼 증가시키면서 확인) 정답 코드최대 범위인 gcd를 구해 while문의 범위를 제한해주었지만,좀 더 단순하게 M*N으로 해도 이 문제에선 통과할 수 있었다.import sysimport mathinput = sys.stdin.readlineT = int(input())def cal(M,..
저장한 비밀번호를 찾아 출력하는 문제로,사전 자료형을 쓰면 간단하게 해결되는 문제였다. import sysinput = sys.stdin.readline# 저장된 사이트의 주소 수 N, 비밀번호 찾으려는 사이트 주소 수 MN, M = map(int, input().split())memo = dict()for _ in range(N): key, value = input().split() memo[key] = valuefor _ in range(M): find = input().rstrip() print(memo[find])
풀이 1: 플로이드-워셜플로이드-워셜: 모든 정점 쌍 최단 거리 계산시간 복잡도는 O(N^3) - 이 문제는 N 최댓값 100이므로 이 문제에서 사용할 수 있다.import sysinput = sys.stdin.readlineN, M = map(int, input().split())# 거리 배열 초기화INF = sys.maxsizedist = [[INF] * (N+1) for _ in range(N+1)]# 자신과의 거리는 0으로for i in range(1, N+1): dist[i][i] = 0# 친구 관계 입력for _ in range(M): A, B = map(int, input().split()) dist[A][B] = 1 dist[B][A] = 1# 플로이드-워셜for k ..
문제 요약한번 입었던 옷들의 조합 다시 안 입는 해빈이 - 알몸이 아닌 상태로 며칠 돌아다닐 수 있는가 풀이간단한 조합 문제이다.import sysinput = sys.stdin.readlineresult = []testcases = int(input()) # 테스트케이스 개수def combi(clothes_dict): count = 1 # 곱셈을 위한 초기값 for clo_type in clothes_dict: count *= (len(clothes_dict[clo_type]) + 1) # + 1 은 선택하지 않는 경우 포함 return count - 1 # 알몸인 경우 제외for _ in range(testcases): n = int(input()) # 의상 수 ..
문제 요약듣 명단, 보 명단 각각 주어지면듣 & 보 명단 구하기.이름 길이는 20 이하, 명단은 각각 500,000 이하.듣보잡의 수와 그 명단을 사전순으로 출력 아이디어명단을 사전순으로 출력해야한다 -> 출력할 때는 set(집합)을 쓰면 안 된다.set은 순서를 보장하지 못하기 때문.집합으로 입력 저장하고, 교집합 구한 후 리스트로 정렬 후 출력하면 된다. 풀이import sysinput = sys.stdin.readlinen, m = map(int, input().split())n_list = {input() for _ in range(n)}m_list = {input() for _ in range(m)}total = n_list & m_listresult = sorted(list(total))p..
문제 요약높이 H 지정 (0~양의 정수)H보다 큰 나무는 H 위의 부분이 잘리고, 낮은 나무는 잘리지 않는다.적어도 M미터의 나무를 집에 가져가기 위한 절단기 높이의 최댓값나무의 수 N (1 ≤ N ≤ 1,000,000)가져가야 하는 길이 M (1 ≤ M ≤ 2,000,000,000)-> input값이 매우 크다. 시간 복잡도를 신경 써야 한다는 힌트이다. 첫번째 시도: 브루트 포스(완전탐색) - 시간 초과import sysinput = sys.stdin.readlineN, M = map(int, input().split())trees = list(map(int, input().split()))trees.sort(reverse=True)h = trees[0]-1for i in range(h, 0, -1)..
