김머성 블로그

[LeetCode 문제풀이] 149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/ Max Points on a Line - 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 평면상의 점 위치가 임의의 갯수 만큼 주어지고 해당 점들을 관통하는 직선을 그어서 이을 수 있는 점의 최대 갯수를 구하는 문제이다. 거의 한달은 푼 것 같다. 로직은 단순한데 코너케이스가 너무 많이 발생했다. 씨특키를 썼기 때문에 잘 짠 코드가 아님에도 불구하고 시간 점수는 잘 받은 ..

가치 그래프를 활용해서 문제 풀기 - 순한맛

전에 설명했었던 그래프에 가치망을 더해서 문제풀이를 해보겠다. 특히 넓이우선 탐색의 문제 풀이에서는 다른 풀이방법들(그리디, 백트래킹)로는 정상적인 답 도출이 어려운 문제들을 그래프로 풀어보겠다. 간단한 가치망을 가지고 있는 깊이 우선 탐색문제부터 풀어보도록하자. [문제 출처] jungol.co.kr ...더보기 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생..

깊이 우선 탐색 / 넓이 우선 탐색 + 그래프를 알고리즘상으로 표현하기

++참고 인프런 이재규님 강의 깊이 우선 탐색은 depth first search라고 해서 DFS라고 불리우는 탐색법이다. 그래프의 모든 정점들을 효율적으로 방문하기 위한 알고리즘이며 여러가지 결과가 나올 수 있다. 현재 방문한 정점에 연결된 정점 중 방문하지 않은 정점을 방문한다. 재귀적인 특성을 가지고 있고 스택을 활용해서 재귀호출을 제거 할 수 있다. 넓이 우선 탐색은 breadth first search라고 해서 BFS라고 불리우는 탐색법이다. 깊이 우선 탐색과 마찬가지로 그래프의 정점들을 순회하기 위한 알고리즘이며 여러가지 결과가 나올 수 있다. 현재 방문한 정점에 연결된 모든 정점을 한번씩 방문한다. 더 이상 현재 정점에 연결된 정점 중 방문하지 않은 정점이 없을 때, 다음 정점으로 이동해서 ..

구글 컴퓨트 인스턴스 생성 첫 성공

성공은 했는데 .net 라이브러리에 대한 문서가 없어서 만들기 넘 힘들다. 우선은 작성되어있는 써머리 보고 더듬더듬 해보다가 정 힘들면 또 그냥 Rest API로 덮어야겠다. ps. 네트워크나 디스크같은 설정들을 왜 인터페이스로 구현한건지 진짜 개 궁금하다. 대체 왜?? 머하러?? 불편하면 불편하지 편한건 없는거같은데

그래프 개념

참고: 인프런 이재규님 강의 그래프란, 정점과 간선으로 이루어진 객체간의 연결 상태를 표현하는 방법을 의미한다. 정점과 간선의 절대적인 위치는 중요하지 않고 오직 연결 상태만이 중요하다는 특징이 있다. 즉, 위상적인 표현 방법이다. 위상적 : 좀 추상적인 개념이다. 절대적인 위치보다 객체간의 상대적인 위치와 상태가 중요하다는 의미로 이해하면 된다. 경로 : 말 그대로 정점 v1에서 v2로 가는 경로의 모든 순서 집합 단순 경로 : 같은 정점을 2번 지나지 않는 경로 부분 그래프 : 그래프 a가 그래프 b의 교집합이라면 a를 b의 부분 그래프라고 한다. 싸이클(회로) : 시작과 끝 정점이 같은 경로 신장트리 : 회로가 없는 그래프 완전 그래프 : 모든 정점이 간선으로 이어져있는 그래프. 정점의 갯수가 v개..

2019/02/07 프로젝트 진행 정리

코드 자체는 정리해야하지만 유튜브쪽은 처음 계획했던거 거의 다 만든 것 같다. 동영상 검색 / 다운로드까지 구현은 다했고 코드 정리만 하면 될 것 같음 근데 작동 안하는 코드를 싹다 주석처리하면서 짜는 바람에 정리할게 한 두가지가 아니다. ㅅㅂ 내일은 테스트 프로그램 제작 시작하니까 오늘 이정도에서 마무리해야겠다. 1. 인코딩된 URL은 String으로 출력이 안된다. (GetAsync로 받은 문자열)이거 때문에 거진 3일동안은 왜 안되는지 모르고 video_info 못받아오고 있는 줄 알고 별의 별짓을 다 해봄 ㅡㅡ; 2. 진행률은 비디오 다운로드 자체만 카운트 가능함. 웹에서 비디오 정보 따오는 건 전체량을 정확하게 알 수 없기 때문에 파악이 불가능하다. 3. mp3는 아직 짜진 않았는데 mp4받는거..