본문 바로가기

백준99

수 찾기 - 1920번 단순하게 배열에 있는지 없는지를 따지게 되면 시간초과가 뜨는 문제이다. 탐색 중, 이분탐색을 사용하여 풀면 빠르다. 문제 해결을 위해 이분탐색하는 함수를 만들어주었다. return값은 인덱스를 뽑아낸다. n = int(input()) ns = list(map(int,input().split())) m = int(input()) ms = list(map(int,input().split())) ns.sort() # 이분탐색 함수 def bin_search(target, arr): start = 0 end = len(arr)-1 while start target: end = mid-1 else: start = mid+1 return None for i in ms: idx = bin_search(i,ns) if.. 2022. 9. 15.
A → B - 16953번 그리디 문제로 인식하고 풀었다. 처음 숫자부터 목표숫자까지 커지게 만들지 말고, 목표숫자부터 처음숫자로 작아지게 만들면 쉽게 해결할 수 있다. n,m = map(int,input().split()) res = 1 while m>n: res+=1 if m%2 == 0: m = int(m/2) elif m%10 == 1: m = m//10 else: res=-1 break if m != n: res = -1 print(res) 2022. 9. 14.
AC - 5430번 입력받는 배열을 파싱한 후 deque로 변환하여 다루면 빠른 속도로 해결할 수 있다. deque의 속도는 O(1) 이고, 리스트의 속도는 O(n)이기 때문이다. 하지만 deque의 reverse(deque.reverse())는 속도가 리스트의 reverse와 비슷하게 느리다. 따라서 deque로 구현하되 reverse를 최대한 적게 사용하는 방법으로 코드를 짜야한다. 문제에서 입력받는 수행할 함수 p에서 R이 나올 때 마다 reverse를 하지말고, 상황에 따라서 deque.pop()과 deque.popleft()를 적절하게 사용해주면 된다. 그리고 deque.reverse()는 가장 마지막에 검사하여 적용해주면 된다. from collections import deque import sys n = in.. 2022. 9. 13.
주유소 - 13305 기름값이 가장 적은 도시가 어디인지 먼저 알아내야한다. 그 도시가 처음 출발하는 도시면 간단하고, 아닐 경우, 처음 도시에서 기름값이 가장 싼 도시까지 가는 도중에 그나마 기름값이 싼곳을 거쳐가면 최소비용을 구할 수 있다. 그리고 가장 마지막 도시의 기름값을 알 필요가 없어서 저장하지 않거나 입력받고 삭제하는 것을 추천한다. n = int(input()) distance = list(map(int, input().split())) cost = list(map(int, input().split())) cost.pop() first_cost = cost[0] min_cost = min(cost) min_cost_loc = cost.index(min_cost) pay = 0 p_cost = first_cost.. 2022. 9. 12.
DFS와 BFS - 1260번 DFS는 재귀로 구현하고, BFS는 스택으로 구현한다. 먼저 그래프를 만들어준다. DFS 방문했던 곳을 체크하기위한 배열을 준비한다. 방문시 방문했다고 표시한다. 그 다음 방문한 곳의 그래프를 검사하여 방문하지 않은 곳을 DFS함수에 넣어서 재귀적으로 탐색을 진행한다. BFS 방문했던 곳을 체크하기위한 배열을 준비한다. 방문시 방문했다고 표시한다. 방문한 곳을 스택에 넣는다. 스택에서 꺼내서 출력을 한다. 꺼낸 것의 그래프를 탐색하여 아직 방문하지 않은 곳을 스택에 넣는다. 스택이 빌 때까지 반복하면 모든 끝까지 탐색할 수 있다. import queue import sys from collections import deque input = sys.stdin.readline nodes, edges, sta.. 2022. 9. 10.
나무 자르기 - 2805번 이분탐색으로 해결해야 시간초과가 안생기는 문제이다. 처음에 나무 최대 길이에서 1씩 줄여가면서 답에 근접할 때 멈추는 방식으로 풀었었는데 역시나 시간초과가 발생했다. 이분탐색을 이용하여 나무 최대길이를 high, 최소길이인 0을 low로 둔다. 무한루프를 통해 중간길이를 계산하며 나무가 잘린 길이를 계산해준다. 만약, 나무가 잘린 길이가 너무 많다면 low = mid로 해주고, 나무를 덜 잘랐다면 high = mid를 해준다. 나무를 자를 길이는 양의 정수로만 계산되므로 무한루프의 종료지점을 high - low > 1로 해준다. import sys input = sys.stdin.readline n, m = map(int, input().split()) l = list(map(int, input().sp.. 2022. 9. 8.
소수 구하기 - 1929번 최대 범위까지(n) 소수를 다 구한 뒤 하나씩 비교하다보니 시간초과가 떴다. m 부터 n까지 수를 생성하면서 즉시 소수인지 판별하니 됬다. 숫자 n이 소수인지 판별하려면 n의 제곱근이하의 수들을 나눠보면 된다. m,n = map(int,(input().split())) a = [] for i in range(m,n+1): condition = True if i==1: continue for j in range(2, int((n+1)**0.5 + 1)): if i%j == 0 and i != j: condition = False break if condition == True: print(i) 2022. 9. 6.
소수 찾기 - 1978번 유명한 에라토스테네스의 체 방식으로 소수를 찾아준다. 1000이하의 소수를 미리 찾아 둔 후 검사해야하는 숫자들을 하나씩 검사해준다. n = int(input()) l = list(map(int, input().split())) a = [] for i in range(2,1000): a.append(i) for i in a: for j in a: if j%i == 0 and j != i: a.remove(j) cnt = 0 for i in l: if i in a: cnt+=1 print(cnt) 2022. 9. 6.
k번째 수 - 11004번 배열로 숫자들을 입력받고 정렬한다. 정렬된 배열에서 인덱스를 이용해 원하는 수를 뽑아낸다 n, k = map(int,(input().split())) l = list(map(int,(input().split()))) l.sort() print(l[k-1]) 2022. 9. 5.
괄호 - 9012번 올바른 괄호의 형태가 나왔을 때만 판별해야한다. 괄호중 ')'가 먼저 나오게 되면 항상 올바르지 않은 상황이니 'NO'가 나와야하며, 이 경우를 걸러내는 목적으로 코드를 짜면 빠르게 결과를 도출해낼 수 있다. '(' 가 나왔을 경우 체크용 변수에 1을 더해주고 ')' 가 나왔을 경우 -1을 더해준다. (체크용변수는 0부터 시작) 체크용 변수가 음수가 되면 break를 걸어 'NO'가 출력되게 하고 나머지 경우에 대해서는 'YES'를 출력한다. n = int(input()) for i in range(n): check = 0 #괄호 체크용 변수 result = 'YES' #최종 결과 확인용 변수 v = input() for j in v: if j =='(': check+=1 elif j == ')': ch.. 2022. 9. 4.
단어정렬 - 1181번 파이썬 배열의 매소드인 sort는 문자도 정렬해준다. 그냥사용한면 알파벳순으로 정렬해주고 sort(key = len) 처럼 사용하면 길이를 파악할 수 있는 자료형에 한에서 길이순으로 정렬을 해준다. 문제 조건에 맞게 sort()를 먼저한 후, sort(key = len)을 다음에 사용하여 정렬해준다. n = int(input()) l =[] for i in range(n): l.append(input()) l = set(l) l = list(l) l.sort() l.sort(key=len) for i in l: print(i) 2022. 9. 3.
직각삼각형 - 4153번 직각삼각형인지 아닌지 판별하는 방법은 매우 간단하다. 무한루프를 통해 0, 0, 0 입력 받을 때 break를 걸어주면 된다. while True: l = list(map(int, input().split())) if l[0]+l[1]+l[2] == 0: break else: l.sort() if l[2]**2 == l[0]**2 + l[1]**2: print('right') else: print('wrong') 2022. 8. 31.

티스토리툴바