동찬 코드 일지

강의 출처 : https://www.inflearn.com/course/lecture?courseSlug=%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=146721 학습 페이지 www.inflearn.com 문제 : https://leetcode.com/problems/network-delay-time/ # 접근 방법 목적지와 도착지가 있고 가는데 필요한 비용이 주어져있으므로 가중치 그래프를 활용한 문제인 것과 다익스트라 알고리즘을 적용해야 겠다는 생각이 들어야 한다. 다익스트라 모든 노드를 돌았을 때 최소 값을 출력 -> 최소 비용 중 가장 높은 것 출력(Output) 해..

강의 출처 : 요약 : 가중치 그래프에서 사용하는 알고리즘 가중치 그래프란 ? 비용이 가장 작게 드는 경로는 ? 생각할 경우가 2가지 있다. 1. 가중치가 없는 경우 (모든 경로의 가중치는 1) 가장 짧은 경로가 가장 비용이 적게 든다. 이 경우는 이전과 동일한 BFS를 이용 2. 가중치가 있는 경우 비용이 가장 적게 드는 경로를 경유해야 한다. 간선마다 가중치가 주어진 경우 BFS를 사용하지 않고 이때 다익스트라 알고리즘을 사용해야 한다. 다익스트라 다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단경로를 RETURN 하는 알고리즘 방문할 수 있는 노드중에 가장 비용이 작은 곳 방문 (우선순위가 높은 곳 방문) # 다익스트라 원리 1. 우선순위큐에 시작노드 추가 우선순위큐 구현..

힙 자료구조는 완전 이진 트리 그 자체이다. 완전 이진 트리 자료구조를 구현 할 수 있다면, 그 구현한 것이 곧 힙 자료구조(우선순위 큐)가 된다. Heap 완전 이진 트리 (complete binary tree) 형태의 자료구조 이다. 1. min heap : 부모 노드의 값이 자식 노드의 값보다 작은 트리 형태의 자료구조 2. max heap : 부모 노드의 값이 자식 노드의 값보다 큰 트리 형태의 자료 구조 형제 노드 간에는 대소 관계가 정해지지 않는다. Root 노드가 가장 큰 값을 갖는다. 일반적으로 모든 요소를 구현 한다면 매우 복잡해 질 것이다. 하지만 Linked List로 구현 한다면 ? 저장 및 표현 이 매우 간편해진다. 트리에 인덱스번호를 붙이고 순차적으로 Linked 리스트를 이용하..

우선순위 큐에서 이진 트리 (Binary Tree) 를 이용한 힙 자료구조에 대해 다루었다. 이전에 배웠던 이진 트리를 정리해보며 복습하는 시간을 가졌다. 이진 트리는 Tree 자료구조의 한 종류로 자식 (child) 를 최대 2개만 가지는 (left, right) 트리 자료구조이다. Tree 자료구조는 비선형적 자료 구조 이며 계층 구조를 표현 할 수 있다. 이 계층 구조의 특성으로 인해 우선순위 큐에서 활용 될 수 있다. 구현 파이썬으로 구현한 이진 트리 from collections import deque class Node(): def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.ri..

강의 출처 : https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC Queue 큐 - 선입선출 (FIFO - IN - FIRST - OUT) 데이터를 큐에 enqueue 하게 되면 dequeue 하게되면 먼저 들어온 순서대로 출력 이때 먼저와 나중으로 시간 순서에 따라 데이터 추출이 이루어지기 때문에 Array List 혹은 Linked List로 구현했었다. Pirority Queue 우선순위 큐 - 우선순위가 가장 높은 값이 먼저 추출 시간 순서가 아닌 우선순위가 높은 것 부터 dequeue() 결론적으로 우선순위 큐는 힙 (Heap..

" 나는 무엇 때문에 개발자가 되고 싶었나" 물론 누구에게나 마찬가지인 "돈"의 목적이 없다고 말할 수 없다. 하지만 여기에는 나만의 이야기가 있다 나는 예전부터 컴퓨터가 무척 좋았다. 그건 초등학교 입학기 전인 어린이였을 때도 마찬가지였다. 화면 안에서는 현실 만큼 즐겁게 할 수 있는 것들이 너무나 좋았다. 5살 때 무렵 아빠가 물으셨다 "컴퓨터"가 뭐야? 나는 정확히 모니터 안에 있는 마우스 포인터 가리키며 당당히 말했다. "이게 컴퓨터에요!" 아빠는 웃으시며 정답을 말씀하셨지만, 당시 어떠한 말인지 하나도 몰랐던 내가 컴퓨터에게 일을 시키려고 열심히 노력하고 있다. 나는 이러한 컴퓨터로 사람들에게 즐거움을 주고 싶다. 그래 무엇이든 좋다. 그래서 학창 시절에는 내가 많이 즐겼던 게임을 직접 만들고 ..

이번에는 순차 자료구조 중 첫번째 Linked List를 학습하였다. Liked List는 C언어의 순차적으로 저장되는 배열과 비슷하지만, 저장되는 메모리 주소가 직접적 연결되어 있지 않고 논리적인 포인터를 활용하여 다음 값의 주소값을 이전값이 가지고 있다는 특징이 있다. 이로인해 배열 중간에 값을 추가할때 시간복잡도가 훨씬 효율적이다. 먼저 Linked List의 ADT를 정리하였다. Operations: void ListInit (List * plist); - 초기화 할 리스트이 주소값 인자로 전달 - 리스트 생성 후 제일 먼저 호출 되어야 함 void LInstert (List * plist, Ldata data); - 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다. - 데이터의 참조를 ..

프로젝트 제출 후 보고서를 작성하였다. 별도의 양식을 사용하지 않고 작성하여 보았다. 하나하나 일지를 기록한것을 적는 느낌보다. 내가 구현한 기능이 무엇인지 핵심적인 내용만 첨부하려고 하였다. 프로젝트 제목 진행자 진행 기간 사용 언어 목차 1. 개요 2. 예시 실행 결과 3. 세부 진행 상황 및 내용 3. 사용자 메뉴얼 4. 개선사항 Pyinstaller 모듈로 진행 한 소스파일을 바탕으로 실행 파일을 만들어 제공 하도록 하였다. 그리고 사용자가 메뉴얼도 첨부하여 사용자 입장에서 프로그램의 설치 및 환경설정과 사용법도 첨부하도록 하였다. 프로젝트 개선 사항 항목 - 하위 폴더 탐색 기능 추가 - 시간복잡도 및 공간 복잡도 파악 - 에러 핸들링 (존재하지 않는 디렉터리 지정 등) - 소스코드에 세부적인 ..

https://www.acmicpc.net/problem/14501 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는..

파일의 이름으로 파일을 검색하는 name_finder() 함수 구현 추상 자료형 정의 자료구조 때 학습한 ADT를 먼저 정의한 후 코드를 구현하여 보았다. 검색할 파일 이름 입력 : if matching_files: 총 N개의 파일을 찾았습니다. 찾은 파일 디렉터리 : 1번 파일 : 2번 파일 : 3번 파일 : else: 찾는 파일이 없습니다. # name_finder 구현한 코드 def name_finder(): target_name = input("검색할 파일의 이름 입력 : ") target_name = target_name.strip()+".json" # 앞뒤 공백 제거 files = [f for f in os.listdir('.') if os.path.isfile(f) and f.endswith..