본문 바로가기

컴퓨터78

다익스트라 알고리즘 Dijkstra's algorithm 일정 시간 복잡도 다익스트라 알고리즘은 시작 정점이 정해져있다. 정점을 선택해가며 진행하고 각 정점까지 총 가중치를 합한 값을 저장하고 비교해 나간다. 앞서 살펴본 프림 알고리즘의 일정 시간 복잡도와 유사하다. T(n) = 2(n-1)(n-1)로 모든 정점을 방문하기 위해서는 시작 정점을 제외하고 n-1개의 정점을 방문해야한다. 그러므로 repeat n-1번을 해준다 (가장 바깥쪽 반복문) 이 repeat내부에서는 각 정점까지 현재 진행상태에서의 최단거리를 비교하고 (n-1번) 이동할 정점을 고른 후에는 다시 각 정점까지의 거리를 업데이트한다 (n-1번) 그렇기 때문에 (n-1 + n-1)(n-1) = 2(n-1)(n-1)이 되는 것이다. 의사 코드를 보면 다음과 같다. void dijkstra(int n, const n.. 2021. 6. 9.
프림 알고리즘 증명 Prim's Algorithm Proof 그리디 알고리즘은 매 순간 최적의 결과만 추구하기 때문에 최종적으로 얻게 되는 결과가 최적의 결과인지는 알 수 없다. 그렇기 때문에 그리디 알고리즘은 최적의 결과인지 판단하는 것이 필요하다. 프림 알고리즘 역시 그리디 알고리즘에 속한다. 그러므로 프림 알고리즘을 통해서 얻는 결과가 최적 결과인지 확신할 수 없다. 그런데 프림 알고리즘 결과는 항상 최적의 결과라고한다. 이를 증명하는 법을 알아보자. G는 가중치가 있고 방향성이 없는 그래프이다. 이는 전체 정점 V와 전체 간선 E로 이루어져있다. F는 방문한 간선이다. F는 E에 속한다. Y는 V에 속하면서 간선 F를 통해 방문 했던 정점들이다. 그래서 G = (V,E) 이고 F ⊆ E, Y ⊆ V, F는 promising하다고 해보자. 이 때 promis.. 2021. 6. 8.
프림 알고리즘 Prim's Algorithm 일정 시간 복잡도 MST(minimum spanning tree)구하는 알고리즘 정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다. 트리가 N-1개의 간선을 가질 때까지 반복한다. 의사 코드를 보면 다음과 같다. void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선 { index i, vnear; number min; edge e; index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보 number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단) F = ∅; for(i = 2; i 2021. 6. 8.
네이버 지도 API로 웹에 지도 붙이기 (Web Dynamic Map) 네이버 지도 API를 Web에서 사용하는 법을 알아보도록 한다. 1. 네이버 클라우드에 가서 지도 API 이용 신청하기를 한다. (NAVER cloud platform 회원가입이 필요하다.) https://www.ncloud.com/product/applicationService/maps NAVER CLOUD PLATFORM cloud computing services for corporations, IaaS, PaaS, SaaS, with Global region and Security Technology Certification www.ncloud.com 네이버 클라우드 플랫폼의 서비스에서 Maps 이용신청하기를 누르자. 2. 네이버 클라우드 플랫폼 콘솔에서 Application 추가하기 Naver .. 2021. 5. 21.
Maximum Addressable Memory size 구하기 Addressable Memory (주소를 가진 메모리) 메모리가 주소값과 공간으로 구성되어있다. CPU는 주소값을 이용하여 메모리에 접근할 수 있다. 주소값을 이용하여 메모리에 접근하면 CPU는 메모리에 데이터를 쓰거나 데이터를 읽을 수 있다. 예를들어 3bit의 주소 공간을 가지고 있다면, 2^3 = 8로 8개의 주소 공간을 가질 수 있다. 메모리의 한 주소 공간의 크기가 1byte라고 하면 maximum addressable memory size는 8byte가 된다. 만약 한 주소 공간의 크기가 4byte라고 하면 maximum addressable memory size는 4*8byte = 32byte가 된다. 그래서 주소 공간 1개당 1byte라고 하고 instruction 32bit를 가져온다고.. 2021. 4. 14.
System Bus(Data Bus, Address Bus, Control Bus)와 관계 Data Bus - 시스템 모듈 사이에 데이터가 이동하기 위한 길을 제공해줌 - 32~512과 같이 여러개의 Line으로 이루어져있고 각 라인의 수는 Databus의 Width(32~512bits)를 의미한다. - 이는 한번에 얼마나 많은 bits를 이동시킬수 있는가이다(capacity). - 시스템의 전반적인 성능을 결정하는 요소이다. - 보편적으로 word의 너비이다. - 한 사이클에 얼마나 많은 데이터를 전송할 수 있는 지를 결정한다. - Memory에서 데이터를 전송하거나 전달 받는다. Address Bus - Data Bus의 데이터가 어디서 또는 어디로 이동해야하는지 결정한다. - CPU/Memory사이의 주소값 전달 - Width는 시스템의 최대 허용 메모리 용량을 결정한다. - I/O po.. 2021. 4. 12.
[Android] 기상청 동네예보 API (Rest API 사용하기) Java 1. Manifest 수정 - permission 허용, http 허용 우선 Rest API를 사용하기 위해서는 인터넷 네트워크 사용을 해야하기 때문에 Permission이 필요하다. App\manifests\AndroidManifest.xml에서 다음 [그림 1] 과 같이 사이에 다음 코드를 넣어준다. (참고: developer.android.com/training/basics/network-ops/connecting?hl=ko) 코드를 본문에 적고 싶은데 퍼미션 관련 코드는 필터링 되는 모양이다. 본문에 안나온다. 그래서 위 링크를 들어가서 복붙하는 것을 추천한다. 또 기상청에서 제공하는 EndPoint를 보면 "http://..."로 되어있는데 이는 안드로이드에서 "https"가 아니라고 에러를 만.. 2021. 4. 5.
Unity 안드로이드 모바일 Build And Run 했는데 Application이 설치가 안되어있는 경우 Console 창에는 Application Installed to device "~~" 떠서 설치가 성공했는데 테스트 핸드폰에는 해당 어플이 나타나지 않는 경우 (install fail 과는 다른 오류) File > Build Settings > Player Settings... > Setting for Android >Indetification > Package Name을 변경해주시면 잘 깔립니다. 테스트하다가 테스트 앱을 삭제했는데 삭제하고 빌드 다시하면 안드로이드 스튜디오처럼 다시 설치가 될 줄 알았는데 그런게 아니었어서 많이 당황했었습니다. 이렇게 하니까 다시 설치가 되네요. 2021. 2. 10.
MacOs 유니코드(UTF-8) 텍스트 인코딩이 적용되지 않습니다 오류 터미널에 들어가서, 열리지 않는 텍스트 파일이 있는 위치로 이동하고 iconv -c -f euc-kr utf-8 textFileName.txt > newTextFileName.txt 해주면 newTextFileName.txt를 통해 복원된 값을 확인할 수 있다. 2020. 7. 22.
안드로이드 스튜디오 git Merge 쉽게 하는 법 (conflict 없이!!) Android studio에서 git merge를 할때 어떻게 해야할 지 모르시는 분이나, git merge를 하자 충돌이 일어나시는 분, 또는 checkout branch 를 하고 싶은데 수정된 작업때문에 Conflict가 나거나 Abort가 나신분들은 참고하면 좋을 것 같습니다. 작업하던 파일에서 master branch 에 있는 파일을 불러오고 싶다면, VSC -> git -> stash 를 해주고 git pull origin master 를 해주면 됩니다. 작업하던 파일에서 git pull origin master를 하면, 네 이렇게 많은 충돌이 생깁니다. 그럼 여기서 하단 창의 Version Control에 들어가주시고, Merge Conflicts Resolve라 써있는 곳에서 Resolve를.. 2020. 7. 4.
[Flutter] 레이아웃 연습 플러터 레이아웃 연습한 모습 코드는 이하와 같음 import 'package:flutter/material.dart'; void main() { runApp(MyApp()); } class MyApp extends StatelessWidget { @override Widget build(BuildContext context) { return MaterialApp( home: Scaffold( backgroundColor: Colors.teal, body: SafeArea( child: Row( mainAxisAlignment: MainAxisAlignment.spaceBetween, crossAxisAlignment: CrossAxisAlignment.stretch, children: [ Containe.. 2020. 5. 16.
[flutter] Margin, Padding, layout cheat sheet 플러터 마진은 가히 혁명적인것 같다. 너무 간편하다. margin: EdgeInsets.all(숫자) 은 모든 방향 EdgeInsets.symmetric(vertical: 숫자 , horizontal: 숫자)은 상하 좌우 EdgeInsets.fromLTRB(left, top, right, bottom) 은 각자 줄수있고 EdgeInsets.only(left: 숫자)는 방향지정해서 하나. padding도 EdgeInsets 같은 방법으로 이용. 다만 margin은 outside of the widget이고 padding은 inside of the widget. 와 진짜 안드로이드스튜디오로 그냥 코틀린 레이아웃 지정해줬을때는 레이아웃, 마진, 패딩 하나하나 복잡하게 하는 요소중 하나였는데 플러터.. 마음에 .. 2020. 5. 16.

티스토리툴바