본문 바로가기
728x90
반응형

Algorithm & Data Structure

Algorithm & Data Structure 2022. 2. 1. 백준 - 1021번(덱) 파이썬의 deque 기능은 원형 큐와 비슷한 모습을 구현할 수 있다. 양쪽에서 값을 넣는 것이 가능하기 때문이다. 1 2 3 4 5 6 7 8 9 list.appendleft(list.pop()) 을 사용하면 시계 방향(내림차순) list.append(list.leftpop()) 을 사용하면 반시계 방향으로 탐색이 된다.(오름차순) 이번 문제의 핵심아이디어는 시계방향과 반시계 방향 중에 어디로 탐색하는 것인지 더 효율적인가에 대한 기준이 필요한 문제였다. index 기능이 시간복잡도에서 손해일 거라 생각해서 고려하지 않았지만 이게 정답이었다. 찾고자 하는 값의 index값이 전체 배열의 길이의 절반보다 작으면 반시계(오름차순)으로 찾는 게 효율적이고 index 값이 배열 길이 절반보다 크면 시계(내림차순..
Algorithm & Data Structure 2022. 1. 30. 백준 - 10989번(반복문, 아이디어(?)) 메모리가 극단적으로 제한된 오름차순으로 정렬 문제이다. 해결법은 입력받은 값의 인덱스에 해당 숫자가 몇 개 있는지 넣는 것이다. 4,3,5,5,6,7 이렇게 입력 받으면 arr [4]=1 , arr [3]=1, arr [5]=2, arr [6] =1, arr [7] =1 이런 식으로 된다. 변태 같은 문제다. import sys n = int(sys.stdin.readline().strip()) arr = [0] * 10001 for i in range(n): num = (int(sys.stdin.readline().strip())) arr[num] = arr[num] +1 for i in range(10001): if arr[i] !=0: for j in range(arr[i]): print(i)
Algorithm & Data Structure 2022. 1. 30. 백준 - 18528번(큐 구현하기) 큐란 무엇인가? 선입선출 구조이다. 스택은 프링글스 통에 자료를 차곡차곡 쌓아서 제일 먼저 넣은 친구를 가장 나중에 뺀다. 그러나 큐는 프링글스통에 밑에 구멍이 있는 파이프 같은 녀석이다. 가장 먼저 넣은 녀석을 가장 먼저 뺀다. 스택은 입구와 출구가 같고, 큐는 입구와 출구가 다르다. (입구, 출구) 0ㅁㅁㅁㅁ (입구) 0ㅁㅁㅁㅁ0 (출구) 1) collections 모듈에서 deque를 import 하지 못하는 상황에서는 다음과 같다. 넣기: insert(0,x) 를 실행시키면 리스트 가장 앞에 원소를 넣을 수 있다. 빼기: pop(0)을 실행시키면 리스트 가장 앞의 원소를 빼내고 출력할 수 있다. 이럴 경우 성능 측면에서 불리한 것이 많다. 각 연산의 시간 복잡도는 O(N)이다. 2) 그러나 col..
Algorithm & Data Structure 2022. 1. 30. 백준 - 1874번(스택) import sys n = int(sys.stdin.readline().strip()) ans = [] case = [] arr = [0] tmp = 0 GER = 1 trash = [] for i in range(n): arr.append(int(sys.stdin.readline().strip())) for i in range(n+1): case.append(i) im = arr[arr.index(max(arr)):] for i in range(len(im)-1): if im[i] < im[i + 1]: GER = 0 break if GER == 0: ans.append('NO') else: for i in range(1, n + 1): z = case.index(arr[i]) # 주어진 값의 case..
Algorithm & Data Structure 2022. 1. 29. 백준 - 4949번(스택, 전체탐색) import sys ans = [] arr = [[0]] while 1: if arr[-1][0] == '.': break arr.append(sys.stdin.readline().rstrip()) for k in range(1,len(arr)-1): tmp = [] for i in arr[k]: if i == '(' or i == '[' or i == ')' or i == ']': tmp.append(i) if '(' not in arr[k] and '[' not in arr[k] and ')' not in arr[k] and ']' not in arr[k]: ans.append('yes') x = len(tmp) if len(tmp) > 0: ##############판단 하는 부분##########..
Algorithm & Data Structure 2022. 1. 28. 백준 - 15954번(정수론, 전체탐색) import sys import math n,k = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) ans = [] def V(arr): av = sum(arr) / len(arr) temp = [] for i in arr: t = (i - av) **2 temp.append(t) a = sum(temp) / len(temp) ans.append(a) for t in range(k,n+1): for p in range(len(arr) - t + 1): V(arr[p:p+t]) x = math.sqrt(min(ans)) print(x) k개 뿐만아니라 k개 이상의 수를 모두 뽑아야 하는 부분을 ..
Algorithm & Data Structure 2022. 1. 27. 백준 - 9375번 import itertools import sys from functools import reduce from itertools import permutations n = int(sys.stdin.readline()) def multiply(arr): return reduce(lambda x, y: x * y, arr) sol =[] for i in range(n): c = int(sys.stdin.readline()) if c > 0: case = [] for k in range(c): case.append(str(sys.stdin.readline())) temp = [] for k in range(len(case)): temp.append((case[k].split())[1]) temp.sort() ..
Algorithm & Data Structure 2022. 1. 25. 백준 - 2981번 import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): arr.append(int(sys.stdin.readline())) arr.sort() ans = [] for i in range(2,arr[0]+1): cnt = 1 for j in range(1,len(arr)): if arr[0] % i == arr[j] % i: cnt = cnt + 1 if cnt == len(arr): ans.append(i) print(ans) 시간 초과가 났다. 2중 반복문이 시간을 많이 잡아 먹는것 같다. import sys import math def get_GCD(nums): _gcd = nums[0] for n in nums[1:]: _gcd =..
Algorithm & Data Structure 2022. 1. 25. 백준 - 13305(그리디 알고리즘) import sys n = int(sys.stdin.readline()) road = list(map(int, sys.stdin.readline().split())) road.append('a') price = list(map(int, sys.stdin.readline().split())) ans = 0 temp = price[0] for i in range(0, n): if price[i] < temp: temp = price[i] if road[i] != 'a': ans = ans + (temp * road[i]) elif road[i] == 'a': ans = ans + 0 print(ans) sort가 필요하지 않은 그리디 알고리즘 문제였다. 한 줄 풀이 : 가장 저렴한 가격을 기억해 두고 있다가..
728x90
반응형

티스토리툴바