본문 바로가기

분류 전체보기92

프림 알고리즘 증명 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.
오.. 인생 첫 유투브 구독자 공부를 웬만하면 스스로 잘 안해서 [스터디 윗 미]용으로 스스로 스트리밍 하면서 공부하고있었다. 왜 다른 사람의 스터디 윗미를 안보고 직접 스터디 윗미를 하냐면 다른 분 걸 보게 되면 다른 사람 거 구경 좀 할 뿐 굳이 내 공부를 안하는데 내가 스트리밍하면 누군가 보고 있을 지도 모른다는 압박감(?) 때문에 더 딴짓 안하고 공부하게 되서 그렇다. 근데 당연하지만 따로 방송장비도 없고, 구독자 몇 명 달성 전에는 폰으로 스트리밍도 안되기 때문에 노트북 웹캠으로만 스트리밍을 할 수 있어서 되게 화면 가득히 팔 있고 공부하는 노트있고 상당히 투박한..! 스터디 윗미 인데 .. 이런식으로... 내가 봐도 스터디 윗미로는 너무 부담스러운 스트리밍이지만 그래도 항상 2시간 3시간씩 누군가 1명씩은 같이 보면서 공부.. 2021. 6. 7.
2021 삼성전자DS 대학생 인턴 면접 후기 망했다. 완전 망했다. SW역량 시험에 당연히 떨어질 거라고 생각해서 면접 연습을 안했던게 문제였다. 면접 비밀 서약서 작성했기 때문에 면접 내용과 관련된 이야기는 할 수 없다. 아침 8시까지 영통역 5번 출구 앞으로 모이는 거였는데 나는 7시 20분쯤 도착했다. 이 때는 사람이 없었는데 7시 30분부터 슬슬모이더니 40분쯤부터 줄을 이만큼 섰었다. 복장은 비지니스 캐주얼이라고 써있었는데 정말로 99%가 완벽한 정장이었다. 물론 나도 친구가 그냥 정장입는게 편하다고했어서 정장입고 갔었다. 버스타고 다같이 면접장으로간다. 개인적으로 면접장에 가는 것은 안된다. 면접장에서 대기실에서 인성검사를 하고 적성검사를한다. 나는 SW직무라 적성검사를 따로 치지 않았다. 면접장에서 면접 대기하는데 오래걸려서 같이 기다.. 2021. 5. 24.
네이버 지도 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.
2021 삼성 대학생 인턴십 sw역량테스트 후기 + 합격!! 경기도 수원에서 시험을 쳤다. 삼성답게 각 자리에 구비된 삼성노트북을 이용해서 시험을 친다. IDE로는 언어별로 eclipse, visual studio, pycharm을 사용하도록 한다. vscode가 있긴 했는데, vscode c/c++ 세팅을 항상 인터넷 보면서 해왔어서 인터넷이 연결 안되어있는 상황에서 세팅하는 것을 깔끔히 포기했다. 나는 c++로 시험을 응시했는데, visual studio에서 출력결과를 터미널로 어떻게 볼 수 있는지 몰랐는데 Q&A게시판에 상세히 적혀있었고, 파일 읽기하는법(freopen)도 다 적혀있어서 시험보는데 지장이 없었다. 나는 따로 단축키 세팅은 하지 않기 때문에 위 두가지 사항을 준비하는 것 외에는 준비 할 것이 없었다. 삼성 SW역량테스트는 항상 구현 / 시뮬레이.. 2021. 4. 26.
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.

티스토리툴바