본문 바로가기
반응형

전체 글

 (57)
[프로그래머스][python]게임맵최단거리 DFS&BFS 프로그래머스 게임 맵 최단거리 https://school.programmers.co.kr/learn/courses/30/lessons/1844 def solution(maps): answer = 0 n=(len(maps)) m=len(maps[1]) a=0 b=0 maps[0][0]= 'x' while not(maps[n-1][m-1]=='x'): if (a+1=0) and maps[a][b-1]==1 : b-=1 maps[a][b] = 'x' else: return -1 for i in maps: for j in i: if j == 'x': answer += 1 return answer
[baekjoon 백준][python] 20044 greedy https://www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 www.acmicpc.net 1번풀이 # 20044 # greedy from heapq import heappush from collections import deque n = int(input()) item = list(map(int, input().split())) def function(n,item): ans = [] item.sort() item = deque(item) for n..
[baekjoon 백준][python] 5585 greedy https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 대표적인 greedy 문제 단위가 큰 화폐부터 거슬러 주면 된다. n = int(input()) def function(n:int): answer = 0 n = 1000 - n answer += n // 500 n = n % 500 answer += n // 100 n = n % 100 answer += n // 50 n = n % 50 answer += n // 10 n =..
[baekjoon백준][python] 2839 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net # 2839 # greedy n = int(input()) def function(n:int): rem = n % 5 val = n // 5 if rem == 0 : return val elif rem == 1: if val < 1: return -1 else: return(val-1+2) elif rem == 2: if val < 2: return -1 else: return(val-2+4) elif re..
[algorithm] heap [python] 파이썬 기본은 최소힙이다.heappushheapq.heappush(heap,item)heap=[]에 item 추가heappopheapq.heappop(heap)heap에서 가장 작은 원소를 pop & return비어있으면 index errorheapifyheapq.heapify(x)list x 를 heap 으로 변환 O(N)최대힙만들기heap_items = [1,3,5,7,9]max_heap = []for item in heap_items: heapq.heappush(max_heap, (-item, item))print(max_heap)주어진 리스트의 모든 값이 T 이상이 될 때까지 최솟값 두 개를 합치기import heapqdef my_heap_example(L, T): """ 주어진 비커의 리스트..
[algorithm] Stack&Queue [python] Stackpython list 자료구조를 사용하여 간단하게 구현stack = [0, 1, 2]print(stack)stack.append(3)print(stack)stack.pop()print(stack)'''[0, 1, 2][0, 1, 2, 3][0, 1, 2]'''Queuecollections.deque는 double ended queue의 약자로, doubly linked list 로 구성되어있음from collections import deque d = deque()print(type(d)) # #enque for i in range(10): d.append(i) print(d) '''deque([0,1,2,3,4,5,6,7,8,9])'''#enque from left d.appendleft(10..
[algorithm] BFS & DFS BFS (breadth first search)루트노드와 같은 거리에 있는 노드 우선Queue 사용graph_list = {1: set([3, 4]), 2: set([3, 4, 5]), 3: set([1, 5]), 4: set([1]), 5: set([2, 6]), 6: set([3, 5])}root_node = 1from collections import dequedef BFS_with_adj_list(graph, root): visited = [] queue = deque([root]) while queue: n = queue.popleft() ..
[algorithm] dynamic programming [python] 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 1 부분 문제 반복(Overlapping subproblems)과 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.\여기서 부분 문제 반복과 최적 부분 구조를 가지고 있다에서부분 문제의 해는 전체 문제의 해를 구할 때 필요해야한다.Tabulation하향식 Bottom-Up 방식이라고도 한다.최초 값부터 차례대로 계산해 나가는 방식이다def fibonacci_dp(num): f = [0, 1] for i in range(2, num+1): f.append(f[i-1] + f[i-2]) return fMemoization이전 계..
반응형

티스토리툴바