본문 바로가기
반응형

Computer Science77

[알고리즘 algorithm] 다익스트라 알고리즘- 파이썬 코드와 예제 최단 경로 문제를 푸는 알고리즘으로 가장 잘 알려진 다익스트라 알고리즘을 파이썬 코드로 작성하면 다음과 같다. 기본 문제 : leetcode.com/problems/network-delay-time/ Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = co.. 2021. 4. 9.
[자료구조] DFS 정복을 위한 재귀 연구 프로젝트 재귀함수를 빠르게, 쉽게 작성하려면 어떻게 해야 할까?? 문제마다 재귀함수로 접근을 하려고 하면 항상 머릿 속이 하얘지고 머리가 아파오기 때문에 많은 분석을 통하여 나름의 작성 법칙을 만들어 보기로 했다. 여러 dfs 문제 코드를 보면서 그 속에서 공통점을 찾아보자. 재귀를 작성할 때 헷갈리는 것들 - while을 쓸지 if를 쓸지 - while을 쓸지 for를 쓸지 - return을 쓸지, return으로 무엇을 넘겨줄지 - 재귀함수로 무슨 인자를 넘겨줄 것인가 - 백트래킹을 어떻게 할것인가? 즉 말단 노드에서 어떻게 처리할 것인가 연구(계속 업데이트 중) - 재귀함수에서 while을 쓰면 엄청 복잡해짐 - 재귀함수는 보통 while 보다는 for/if 안에 들어있음 / 아님 아예 밖에 있거나 - 백트.. 2021. 4. 4.
[자료구조] 그래프- 깊이우선탐색(dfs)와 너비우선탐색(bfs) 구현 ** '파이썬 알고리즘 인터뷰(박상길 저)' 내용을 참고하여 작성하였습니다. 그래프: 객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조 오일러 경로: 모든 간선을 한번씩 방문(= 한붓 그리기) 해밀턴 경로: 모든 정점을 한번씩 방분 그래프 순회: 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정 그래프 순회에는 깊이우선탐색(Depth-First Search)와 너비우선탐색(Breadth-First Search)가 있다. 일반적으로 DFS가 BFS에 비해 더 널리 쓰인다. DFS - 스택이나 재귀로 구현. 백트래킹을 통해 뛰어난 효용을 보인다. BFS - 큐로 구현한다. BFS는 재귀로는 구현 불가능. * 백트래킹: 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 .. 2021. 4. 3.
[자료구조] 해시테이블의 개념- 개별 체이닝, 오픈 어드레싱 방식 해시테이블: 해시테이블 또는 해시맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료구조다. 해시테이블의 핵심은 해시함수다. 해시함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다. 해시테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라고 표현한다. 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용. 즉, 최적 검색이 필요한 분야에 사용한다. # 좋은 해시함수의 특징 - 해시 함수 값 충돌의 최소화 - 쉽고 빠른 연산 - 해시 테이블 전체에 해시값이 균일하게 분포 - 사용할 키의 모든 정보를 이용하여 해싱 - 해시테이블 사용 효율이 높음 충돌 처리에는 두가지 방법이 존재한다. 개별체이닝 방식과 오픈 어드레싱 방식 개별체이.. 2021. 4. 3.
데이터베이스 모델링 기초 옛날에는 어떤 프로그램을 작성할 때, 계획하고 분석하기 보다는 일단 코딩해보는 습관때문에 결국 문제가 발생하여 모든 프로그램을 삭제하고 처음부터 다시 코드를 짜게 되는 일이 많았다. 이는 분석과 설계 작업을 등한시하는 소프트웨어 분야의 고질적 문제점이었다. 이러한 문제점 해결을 위해 '소프트웨어 개발 방법론'이 나타나고 이 분야를 '소프트웨어 공학'이라고 부르게 되었다. 소프트웨어 공학에서 가장 전통적으로 사용되는 모델은 폭포수 모델이다. 프로젝트 계획 - 업무 분석 - 시스템 설계 - 프로그램 구현 - 테스트 - 유지보수 이 모델에서 가장 핵심적인 부분은 업무 분석과 시스템 설계로, 전체 과정 중 50프로 이상을 차지한다. 데이터베이스 모델링은 분석과 설계 단계에서 가장 중요한 작업중 하나다. 데이터베.. 2021. 4. 1.
[자료구조] 큐queue 정의 및 데크deque와 힙큐heapq 사용법 큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다. 큐는 FIFO(First-In-First-Out) 선입선출의 구조를 가진다. 간단히 말하면 선착순이다. 맛집에서 줄을 서는 것과 같다. 큐는 스택과 마찬가지로 리스트로 큐의 모든 연산을 구현할 수 있다. 하지만 동적 배열인 리스트는 큐연산에 적합하지 않아서 데크(deque)라는 별도의 자료형을 써야 좋은 성능을 낼 수 있다. 데크 : 더블엔디드큐(Double Ended Queue)의 줄임말로, 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상자료형이다. 데크는 pop( )과 popleft( ) 모두 시간복잡도 O(1)을 가지므로 매우 성능이 좋은 자료형이다. import collections .. 2021. 3. 31.
반응형

티스토리툴바