Altiora Petamus

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🤔생각해보기 DFS와 BFS의 기본 개념을 익히기 위한 문제다. 자바에서는 2차원 배열로 edge 들을 설정한 뒤에 해결했었는데 파이썬에서 딕셔너리를 활용하여 풀어보았다. 개인적으로는 2차원 배열이 가독성이 끔찍하다고 느껴져서인지 어려워하는 편인데 딕셔너리를 활용해보니 이해하기도 편하고 훨씬 쉽게 해결 할 수 있는 것 같다. 성공 코드 from collections import deque from collections imp..

2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 🤔생각해보기 소수를 찾는 것은 여러가지 방법이 있지만, 평소 애용하는 방법은 제곱근을 통해서 구하는 방법이다. math.sqrt() 의 효율성에 대해 여러 의견이 있긴하던데, 아직까지 느려서 실패한 적은 없는 것 같다. 로직은 다음과 같이 처리하면 된다. 소수인지 검사해서 배열 prime에 담는다. prime이 비어있다면, -1 을 출력하고 값이 있다면 합과 최소값을 각각 출력한다. 성공 코드 # 소수 # 기본수학 2 # 소수를 찾아서 리스트에 넣기 # 배열에서 최소값 m..

11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 🤔생각해보기 n을 i 로 나눠보고 나머지가 0 이라면 출력, n //= i 를 사용하여 n을 몫으로 재설정 n이 i로 나누어지지 않는다면 i += 1 i^2가 n과 같아질 때까지 실행 만약 n = 10이라면, 2 로 나누어지고 n = 5 가 된다. 5는 소수이므로 i는 증가만 하다가 5가 되면서 루프를 빠져나오게 되고 결과가 2와 5만 출력되게 된다. 5는 소수이므로 ⇒ 소수를 판별하는 과정은 제곱근을 활용한다. 자세히 생각해보니 i와 n이 같아질 때까지 검사하는 것은 시간복잡도만 증가시킬 것 같았다. 애초에 루프를 i의 제곱이 n과 같아질 때까지만 실행시키면 된다. 성공 코드 n ..

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 🤔생각해보기 꽤나 매콤한(?) 문제였습니다. 시간초과 제한이 상당히 타이트한데, 하나하나 짚어봅니다. 먼저 제시된 함수를 보면 뒤집는 것과 첫번째 숫자를 버리는 것입니다. 파이썬을 평소 즐겨 사용해왔다면 collections deque 모듈에 존재하는 다음과 같은 함수를 바로 떠올릴 수 있을 겁니다. reverse() popleft() 위 메소드만 잘 사용하면 "예제는" 통과하는 답을 나오게 할 수 있습니다. 하지만 위 메소드 중 어느 하나라도 사용한다면 얄짤없이 바로 시간초과가 발생합니다. 한마디로 함정카드인 것이죠..

2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 🤔생각해보기 문제에서 정답을 구하는 법을 다 설명해주는 쉬운 문제 중 하나이다. 성공 코드 from collections import deque N = int(input()) cards = deque([i for i in range(1, N + 1)]) while len(cards) > 1: # 카드뭉치의 윗장를 버린다. cards.popleft() # 아래로 옮긴다. cards.rotate(-1) # 남은 카드 한장 print(cards[0]) 코드에 특별한 ..

2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 🤔생각해보기 최소공배수를 구해야하는거 같긴한데 어떤 수의 최소 공배수를 구해야할지, 도무지 어떤 방법으로 접근해야할지 감이 안와서 여러가지 방법을 시도했지만 시간 초과나 실패가 발생했다... 타 블로그를 참고해보니 '입력값들의 차이가 일정하며 그 차이들의 최대공약수의 약수가 정답'이라는 정보를 얻고 로직을 만들어봤다. 성공 - PyPy3가 아니라 Python3로 제출 import math N = int(input()) nums = sorted([int(input()) for _..

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 🤔생각해보기 파이썬의 정렬은 람다를 사용할 수 있다. 다중 조건일 경우 튜플로 넣어주면 되므로 아주 간단하게 해결할 수 있다. 성공 코드 N = int(input()) position = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: (x[0], x[1])) for pos in position: print(*pos) 갑자기 ..

문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 입력 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 ..