본문 바로가기

반응형

전체 글

(85)
파이썬 탐욕(그리디) 알고리즘 사용하기 탐욕 알고리즘? 그리디 알고리즘? 탐욕 알고리즘은 이름하고 유사한 구조를 가진 알고리즘이다. 탐욕 알고리즘을 다른 말로 그리디 알고리즘 혹은 욕심쟁이 알고리즘이라고도 한다. 탐욕이라는 이름 그대로 지금 당장의 문제가 하나 주워졌을때, 나중은 고려하지 않고 지금의 가장 최적의 답을 도출하는 알고리즘이다. 한가지 상황을 예시로 들자면 사자성어 "조삼모사"가 떠오른다. 누군지는 기억안나는데 암튼 누군가가 원숭이들을 기르는데, 먹이가 부족해서 먹이를 줄여서 원숭이들에게 아침에 3개 저녁에 4개를 준다고 하자 원숭이들이 화를 냈다. 그러자 주인이 아침에 4개 저녁에 3개를 주겠다고 하니 원숭이들이 좋아한다는 그런 내용의 사자성어이다. 내용 그대로 당장 지금의 상황만 중요한 원숭이들이 그리디 알고리즘과 흡사하다. ..
백준 9019번: DSLR 파이썬 코드(BFS) import sys from collections import deque t = int(sys.stdin.readline()) def bfs(a1,b1): queue = deque([]) queue.append([a1, ""]) visited = [0 for _ in range(10000)] while queue: now, string = queue.popleft() if now == b1: return string #D--------------------------------- temp2 = now now = now * 2 if now > 9999: now = now % 10000 if visited[now] == 0: queue.append([now, string + "D"]) visited[now]..
로지텍 M171 맥북에서 사용한 리뷰(광고X) 서론 마우스를 사야겠다고 한 몇달 전부터 고민했는데, 맥북에 달려있는 트랙패드를 주로 사용하고, 유니티 같은 드래그가 많이 필요한 작업을 할 때는 그냥 본체에 있는 유선마우스를 빼다써서 무선마우스를 살지말지 고민하다가 드디어 구매하였다. 그렇다고 막 비싼 걸 산건 아니고 M171이다. 연결성 로지텍 M171은 아쉽게도 블루투스를 지원하지 않는다. usb 수신기로 연결해야한다. 하루 정도 사용해본 결과 나쁘지 않다. 맥북에서 사용 중인데, 로지텍 답게 연결이 끊기는 일은 없다. 사실 지금 집에 무선마우스가 하나 있는데, 집에 굴러다니던거라 그런지 커서가 갑자기 튀거나, 뚝뚝 끊기는 현상이 있는데, M171은 그런건 없어서 좋다. 연결성: 5/5점 다만 블루투스가 지원 되지않음. 그립감 애매하다. 자동차로 ..
백준 1931번: 회의실 배정 파이썬 코드(그리디 알고리즘) import sys n = int(sys.stdin.readline()) mm = [] #mm은 회의실 목록 temp = 0 count = 0 for _ in range(n): start, end = map(int, sys.stdin.readline().split()) mm.append([end,start]) mm = sorted(mm) for i in range(n): if i == 0: temp = mm[i][0] count += 1 else: if temp
백준 15686번: 치킨 배달 파이썬 코드(백트래킹) import sys from itertools import combinations n,m = map(int, sys.stdin.readline().split()) home = [] chicken = [] for i in range(n): a = list(map(int, sys.stdin.readline().split())) for j in range(n): if a[j] == 1: home.append([i+1,j+1]) elif a[j] == 2: chicken.append([i+1,j+1]) INF = sys.maxsize temp = [] dislist = [] for k in combinations(chicken, m): distance = [INF for _ in range(len(home))]..
백준 13549번: 숨바꼭질 3 파이썬 코드(bfs) import sys from collections import deque n,k = map(int,sys.stdin.readline().split()) x = [-1, 1, 2] ll = [] def bfs(now,target): queue = deque([]) visited = [0 for _ in range(300009)] queue.append([now,0]) while queue: q,c = queue.popleft() visited[q] = 1 if q == target: count = c ll.append(count) for i in range(3): if i == 2: a = q * 2 if visited[a] == 0 and 0
백준 1912번: 최소비용 구하기 파이썬 코드(다익스트라) import heapq import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) INF = sys.maxsize graph = {} dist = [INF] * (n) queue = [] for _ in range(m): s,t,w = map(int, sys.stdin.readline().split()) if s-1 not in graph: graph[s-1] = [[t-1,w]] else: graph[s-1].append([t-1,w]) startpoint, endpoint = map(int, sys.stdin.readline().split()) def dijkstra(start): heapq.heappush(queue, [0, sta..
2개월만에 소식 남기기 블로그를 시작할때는 하루에 글 하나 씩 써야지라는 마인드였지만, 그건 한 한달 반 만에 깨지고 가끔 업로드하기로 마음을 바꿨는데, 이제 그 조차도 좀 힘들어졌다. 그렇다고 내가 바쁜 삶을 살고 있는가? 그것은 또 아니다. 그냥 여태껏 블로그에 글을 업로드 안한 이유를 살펴보자면, 50퍼센트는 블로그의 존재를 잊고 살았다. 그리고 나머지 50퍼센트는 가끔 블로그의 존재를 떠올렸을때도, "올릴거 없는뎅. 그냥 말아야지." 라는 생각으로 접었다. 근데 왜 다시 블로그에 글을 쓰기 시작했을까. 시험이 끝나고 오랜만에 글이 써보고 싶어서 쓴다. 사실 여태껏 블로그에 글을 올려도 나의 전공 쪽 프로그래밍을 통해 지식을 알리고 내가 공부한 것들을 다시 한번 정리하는 용도였기 때문에 살짝 숙제 같은 느낌으로 글을 써서..

반응형