본문 바로가기
반응형

전체 글

 (141)
파이썬 다익스트라 알고리즘 사용하기 다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0, ..
파이썬으로 스택 알아보고 구현하기 서론 스택은 자료구조 중 대표적인 선형구조이다. 우리가 흔히 게임이나 일상생활에서 "스택 쌓였다"라는 표현을 사용하는데, 완전히는 아니더라도 어느 정도 비슷한 개념을 가지고 있다. 스택 스택은 선형구조의 자료구조로서 일상생활 속에서 꽤나 많이 볼 수 있다. 예를 들어 프링글스 과자를 생각하면 쉽다. 우리가 프링글스를 먹을 때 가장 먹게 되는 감자칩은 가장 마지막에 넣은 감자칩이지 않을가? 이렇게 가장 늦게 넣은 것이 가장 먼저 나온다는 개념을 가졌다면 스택이다. 다른 예시로는 종이컵 더미가 있겠다. 종이컵 더미도 가장 늦게 쌓은 종이컵이 가장 먼저 나오니 말이다. 이를 가장늦게 넣은 것이 가장 먼저 나온다고 해서, 후입선출이라부른다. 스택은 한 곳에서 삽입과 삭제가 일어난다. 나중에 서술할 큐라는 다른 ..
메모리 영역(코드영역, 데이터영역, 힙영역, 스택영역) 서론 메모리 영역은 총 4가지로 나뉜다.(BSS까지 포함하면 5가지) 그리하여, 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 무엇인지 알아보고 각각 어떤 특장을 지니는 지 서술하려한다. 메모리 영역 프로그램이 실행하려면, 당연히 메모리의 공간을 할당을 받아야하고 이 공간을 메모리 영역이라 지칭한다. 코드 영역 이름 그대로 우리가 작성한 코드를 저장하는 공간이다. 텍스트영역이라고도 불리며, 이 공간은 컴파일 할 때 Read-Only이다. 어찌보면 당연한데, 우리가 파이썬을 실행할 때 컴파일할 당시에 코드로 실행하지, 컴파일한 후에 코드를 수정해도 적용되지 않는 이유가 이 때문이다. 데이터 영역 데이터 영역은 전역변수, 정적변수, 배열, 구조체를 저장한다. 이러한 것들은 프로그램이 실행되는 와중에 값이..
맥에서 라즈베리파이 제로 w 기본 설정, 기본 셋팅 서론 시험이 끝나고 가지고 놀려고, 라즈베리파이 제로 W 모델을 중고로 저렴하게 구입하였다. 방학동안 간단하게 웹서버 한번 운영해보려고, 구입했다. 필자는 현재 기본세팅을 마친 후 라즈비안을 올리고, 아파치와 mariadb를 설치해두었다. 기본세팅은 간단하지만, 필자와 같이 라즈베리파이가 처음이라면 헤맬 수 있으니 같이 한번 기본셋팅을 해보도록 하자.(라즈베리파이 제로 W 모델을 기준으로 설명) 준비물: 라즈베리파이 제로 W(다른 라즈베리파이 모델도 괜찮습니다.) 마이크로 SD카드(필자는 16GB, 다이소에서 구입)(8GB이상 권장) 마이크로 SD카드 리더기(만약 본인이 마이크로 sd카드를 꽂을 수 있는 일반 sd카드가 있다면 일반 SD카드도 괜찮습니다.) 컴퓨터 시작! 일단 마이크로 sd카드에 운영체제..
파이썬 탐욕(그리디) 알고리즘 사용하기 탐욕 알고리즘? 그리디 알고리즘? 탐욕 알고리즘은 이름하고 유사한 구조를 가진 알고리즘이다. 탐욕 알고리즘을 다른 말로 그리디 알고리즘 혹은 욕심쟁이 알고리즘이라고도 한다. 탐욕이라는 이름 그대로 지금 당장의 문제가 하나 주워졌을때, 나중은 고려하지 않고 지금의 가장 최적의 답을 도출하는 알고리즘이다. 한가지 상황을 예시로 들자면 사자성어 "조삼모사"가 떠오른다. 누군지는 기억안나는데 암튼 누군가가 원숭이들을 기르는데, 먹이가 부족해서 먹이를 줄여서 원숭이들에게 아침에 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
반응형

티스토리툴바