n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 그래프의 1번 노드에서부터 가장 멀리 떨어진..
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.장르 내에서 많이 재생된 노래를 먼저 수록합니다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다. genres와 pl..
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 다이나믹 프로그래밍 문제라고 써있다. DP 문제는 언제 봐도 어렵다. 저번에 Knapsack 문제를 예시로 DP에 대해서 나름 설명을 한 포스팅도 썼었고, 더 예전에는 프로그래밍 과..
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요. 최대 2..
저번 달에 여느때처럼 집에서 쉬고 있었는데 아는 언니한테서 네이버 공채 한번 써보는게 어떻겠냐고 톡이 왔다. 되든 안되든 한번 써보는게 경험이 되지 않겠냐고... 근데 그 소식을 받았던게 지원 마감 하루 전이었고 (...) 그래서 지원서는 두시간만에 호다닥 써서 냈다. 문제를 해결한 자신만의 방법, 자신이 발전하게 된 계기, 네이버 서비스 개선 방안 같은걸 써서 내야 했는데 대학원 시절에 했던 것들이랑 최근에 했던 프로젝트에서 있었던 이슈 짤막하게 정리해서 적었다. 바로 그 주 주말에 코딩테스트가 있었는데 (코딩테스트까지는 지원만 하면 다 보게 해준다고 들었던 것 같다) 토요일이랑 일요일 중에 선택할 수가 있었다. 토요일은 너무 이른 시간이라 못일어날 것 같아서 오후 일정이었던 일요일로 선택. 코딩테스트..
얼마 전에 우연한 계기로 어떤 알고리즘 문제를 풀게 됐는데, 딱 보자마자 학부 시절 자료구조 시간에 배웠던 AOE Network와 Critical Path라는 개념이 떠올랐다. 그걸 이용해서 문제를 풀 수 있겠다는 생각은 들었지만, 문제는 그 개념만 떠올랐지 어떻게 구현하는지는 하나도 기억이 안났다. (...) 결국 제대로 풀지 못했다. 그래서 이번 포스팅에서는 AOV Network, AOE Network (둘은 비슷한 개념이다) 의 개념과 구현 방법에 대해 정리해 본다. 포스팅을 쓰기 위해서 옛날 그 학부 시절에 짰던 코드를 예토전생시켰는데, 날짜를 보니까 거의 6년이 됐더라. 까먹을 만도 하다... 그 코드를 봐도 하나도 이해가 안돼서 인터넷에서 강의자료를 찾아보면서 아예 다시 공부를 했다. 1) A..
100일 앱에 이은 남자친구를 위한 (물론 내 개인적인 공부를 위한 것이기도 하다) 프로젝트 2탄. 이지투는 그 파란만장한 역사 (...) 덕에 현재 제대로 돌아간다고 말할 수 있는 아케이드 리듬게임 중에 거의 유일하게 네트워크 개인화 시스템을 지원하지 않는 게임이다. 그래서 기록을 저장하고 남들이랑 공유하기 위해서는 직접 사진이나 영상을 찍어서 남기는 방법밖에는 없다. 남자친구가 이지투를 주로 하는데, 핸드폰 사진함에 '이지투 성과' 라는 폴더를 만들어서 성과 사진을 거기 모아서 관리를 하고 있더라. 딱 봐도 불편해 보이는데, 예전에 플레이했던 곡 기록을 찾으려면 쭉 내려가면서 사진 썸네일을 대충 보고 이건가 하고 눌러봐야 한다. 특히 같은 곡의 기록을 갱신했을 경우엔 예전 사진을 지우는데, 이걸 하기..
- DOM? Document Object Model. 그러니까 HTML을 구성하는 각 요소들. 자바스크립트의 DOM API를 이용하면 HTML 요소를 찾고 동적으로 변경시킬 수 있다. - document. 으로 접근가능한 메서드들 (링크) document.addEventListener() document.getElementById() document.getElementByName() document.querySelector() document.createElement() - element. 으로 접근가능한 메서드들 (링크) element.childNodes() element.classList() element.firstChild() element.contains() element.innerHTML - 유..
- JavaScript에서의 배열 > 선언: var a = []; > 한 배열 안에 모든 타입의 원소가 들어갈 수 있다. 숫자, 문자, 배열 (-> 2차원 배열), dict 등... > 선언할 때 길이를 정해주지 않는데... a[500] = 10; 이렇게 해줘도 에러가 발생하지 않고 알아서 배열 길이가 501이 된다. 이 상태에서 정의해주지 않은 중간 값들 (a[250] 이라던지) 을 띄워보면 undefined가 뜸. (아무 쓰레기값이 뜨는게 아니다) - 유용한 배열 메서드들: 자바의 ArrayList 메서드들이랑 크게 다르지 않다 > push() > indexOf() > join() > concat() 주의: 메서드에 따라 원래 배열을 조작하는 것도 있고, 원래 배열은 그대로 두고 새 배열을 반환하는 ..
부스트코스를 공부하면서 배웠던 서블릿과 JSP, 빌드 도구 Maven을 이용해서 조그마한 자바 웹 애플리케이션을 만들고 있었다. 로컬에서 테스트하면서 기능적인 부분을 거의 다 완성하고 나니 이걸 실제로 서버에서 돌리려면 어떻게 해야 하나, 라는 생각이 들었다. 이걸 누가 쓴다 치면 내 컴퓨터를 항상 켜놔야 서버가 돌아가는건데 그럴 수는 없으니까. 이럴 때 이용할 수 있는 서비스가 AWS 같은 클라우드 서비스다. 클라우드에서 VM을 만들고 그 안에 웹 서버 소프트웨어랑 내가 만든 애플리케이션을 넣어서 서버로 쓰는 것이다. 근데 이렇게 하려고 보니까 나는 윈도우에서 GUI로 작업을 했는데 서버용 VM은 리눅스 CUI라는 점이 생각났다. 윈도우에서 앱을 만들기 위해서 했던 과정들 (이클립스에서 Maven Pr..