문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한 사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 풀이 레벨3 문제치고는..
그래프
문제 설명 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다. 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다. 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 ..
문제 설명 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다. 그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가하려고 합니다. A의 집은 6번 지점에 있으며 B..
문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solutio..
Scatter plot 상관관계를 나타내는 scatter plot은 점으로 데이터를 표현한다. 수익과 할인율이 관계가 있을 거라 생각하고 그래프를 그려보자. 점이 하나 찍혀있다. 모든 물건에 대해 300,000원 정도의 수익이 났고 16% 정도 할인해 주었다는 뜻이다. 하지만 우리가 원하는 데이터는 이게 아니다. 고객별로 데이터를 나눠보자. 각 점은 고객에 대한 데이터이고 할인율과 수익을 볼 수 있다. 눈에 좀 더 잘 보이고 수익을 가져다주는 고객과 그렇지 않은 고객으로 분류해보자. 이것은 제품별로 본 것이다. 추세선을 추가하여 두 데이터사이에 관계를 볼 수 있다. Histogram 데이터 분포를 볼 수 있는 그래프이다. 데이터는 총 9994개의 행을 가지고 있다. 0에서 200달러 사이에 판매된 재품이..
바 차트(Bar Chart) 차트 중 가장 기본이 되는 막대그래프를 그려보자. 차원과 측정값을 적절히 지정하면 간단하게 그래프를 그릴 수 있다. 지역을 차원으로 매출을 측정값으로 지정하면 자동으로 바 차트를 그려준다. 데이터가 누워있는거 보단 위아래로 긴 차트가 좀 더 비교하기 쉬울 것 같다. 행과 열을 바꿔보자. 상단에 행과 열을 바꾸는 아이콘을 누르거나 ctrl + w를 누르면 돌릴 수 있다. 조금 더 눈에 잘 보이게 서식을 바꿔보자. 축 눈금자를 없애고 테두리를 입혀봤다. 라인 차트(Line Chart) 연속적인 데이터를 보기 쉬운 라인 차트를 그려보자. 라인 차트를 그릴 때는 날짜를 기준으로 분류하는게 일반적이다. 따라서 열에 주문 날짜를 행에 매출을 주어 그래프를 그리면 자동으로 라인 차트를 그..
그래프 그리기 ax = plt.subplots() ax = tips['total_bill'].plot.hist() 우선 시리즈에 있는 plot 속성에 정의된 hist 메서드를 사용하여 히스토그램을 그릴 수 있다. 투명도를 조절하려면 hist 메서드의 alpha, bins, ax 인자를 사용하면 된다. fig, ax = plt.subplots() ax = tips[['total_bill', 'tip']].plot.hist(alpha=0.5, bins=20, ax=ax) 밀집도, 산점도 그래프, 육각 그래프는 각각 kde, scatter, hexbin 메서드를 사용하면 된다. fig, ax = plt.subplots() ax = tips['tip'].plot.kde() fig, ax = plt.subplot..
기초 그래프 그리기 seaborn 라이브러리에는 tips라는 데이터 집합이 있다. tips 데이터 집합은 어떤 식당에서 팁을 지불한 손님의 정보를 모아둔 것이다. 데이터 불러오기 tips = sns.load_dataset("tips") print(tips.head()) print(type(tips)) 위의 데이터로 히스토그램을 그려보자. 히스토그램은 데이터프레임의 열 데이터 분포와 빈도를 살펴보는 용도로 자주 사용하는 그래프이다. 이때 데이터프레임의 total_bill, tip 등의 열을 변수라고 부르기도 한다. 그리고 변수를 하나만 사용해서 그린 그래프를 '일변량 그래프'라고 부른다. fig = plt.figure() axes1 = fig.add_subplot(1, 1, 1) 기본 틀을 만든다. axe..
데이터 시각화 데이터 시각화를 보여주는 전형적인 사례로 앤스콤 4분할 그래프(Anscombe's quartet)가 있다. 영국의 프랭크 앤스콤이 데이터를 시각화하지 않고 수치만 확일할 때 발생할 수 있는 함정을 보여주기 위해 만든 그래프이다. 앤스콤이 지적한 함정과 데이터 시각화의 필요성 앤스콤 4분할 그래프를 구성하는 데이터 집합은 4개의 그룹으로 구성되어 있으며 모든 데이터 그룹은 x, y 열을 가지고 있다. 그런데 이 4개의 데이터 그룹은 각각 평균, 분산과 같은 수칫값이나 상관관계, 회귀선이 같다는 특징이 있다. 그래서 이런 결과만 보고 '데이터 그룹 1, 2, 3, 4의 데이터는 모두 같을 것이다'라고 착가할 수 있다. 바로 이것이 앤스콤이 지적한 '함정'이다. 하지만 각 데이터 그룹을 시각화하..
그래프 탐색의 기본인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하는 문제를 풀어보았다. 예전에 공부해서 잘 할 수 있으려나 하고 생각했는데 생각보다 잘 풀렸다. 역시 기본 개념을 이해하고 있다면 구현하기 쉬운 거 같다. DFS에서는 재귀를 이용한다는 점을 알고 구현하니 훨씬 순조로웠다. 또한 BFS에서 Queue를 사용한다는 키포인트를 알고있었기 때문에 쉽게 문제를 풀 수 있었다. DFS에서는 방문하지 않은 노드일 경우 출력을 하고, 해당 노드에서 갈 수 있는 노드를 하나씩 dfs()를 이용하여 재귀시키면 간단하게 풀린다. 그렇게 재귀 호출되어 탐색을 시작한 노드에서도 똑같은 작업을 수행하기 때문에 최대한 탐색할 수 있는 노드까지 최대한 순회한 뒤 반환되어 나머지 노드를 순회한다. BFS..
