1. 위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. [그림 1]을 보자. [그림 1]은 임의로 만든 마법사로 전직을 한후 배워야하는 스킬의 관계도다. 각 스킬에 대한 관계도를 정리하면 다음과 같다. 에너지 볼트는 맨 처음에 배우는 기본 마법이다. 매직클로를 배우려면 에너지볼트를 먼저 배워야한다. 메테오를 배우려면 먼저 매직클로, 텔레포트를 배워야한다. 마력 흡수를 배우려면 먼저 에너지 볼트를 배워야한다. 텔레포트를 배우려면 먼저 마력흡수, 매직클로를 배워야한다. 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 먼저 마법사로 전직하면 에너지 볼트를 찍고, 그 다음엔 마력 흡수 또는 매직클로를 찍는다. 그리고 텔레포트를 찍고 최종적으..

1. 가중치 그래프 가중치 그래프는 간선에 가중치를 할당한 그래프를 말한다. 가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다. 크루스칼(Kruskal) 알고리즘은 비용, 거리, 시간을 최소화하는 신장트리를 만들기 위해 나온 알고리즘이다. 즉, 모든 가중치의 합이 최소 값이 되어야 한다는 것이다. 최소 값이 나오게 하려면, 가중치를 오름차순으로 n-1만큼 더하면 된다. 그런데 앞에서 크루스칼 알고리즘에 대해 설명할 때 신장트리라는 말을 한 적이 있다. 신장 트리란, n 개의 정점을 가진 그래프 G에서 모든 정점이 n-1개의 간선으로 이루어진 트리를 말한다. 2. 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘은 두 가지 방법이 있다. 첫 번째 방법은 가중치가 높..

1. 문제 설명 문제 설명을 보고 내가 난독증인가 했다. 나만 이해를 못한건가 싶어서 바로 질문하기 버튼을 누르니, 나같은 사람이 정말 많았다. 출제자도 논란이 많은 것을 알고 그런지 모르겠지만, 문제 맨 밑에 H-index에 대한 설명이 담긴 위키링크를 걸어뒀다. 위키에서는 H-index를 다음과 같이 구하라고 써있었다. 배열을 내림차순으로 정렬해라. 인덱스 번호[배열 인덱스 + 1] 내림차순 정렬: [4, 3, 2, 1] index + 1 b-a); let idx = 1; while(idx

1. 그래프 그래프란 연결되어있는 원소 간의 관계를 표현하는 자료구조를 말한다. 버스 노선도, 전철 노선도, 인간관계를 나타내는 연결구조는 구조가 너무나도 다양하고 복잡하기 때문에 선형 자료구조나 트리로 표현할 수 없다. 그래프는 연결할 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)로 구성된다. 그래프 G를 G = (V, E)로 정의하는데, V는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선의 집합을 의미한다. 2. 그래프의 종류 (1) 무방향 그래프 무방향 그래프는 간선에 방향이 없는 그래프를 말한다. 무방향 그래프는 정점 V₁과 정점 V₂를 연결하는 간선을 (V₁, V₂) 로 표현한다. 아래 [그림 1]은 무방향 그래프를 나타낸 그림이다. 위 무방향 그래프 G를 정점의 ..

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한사항 numbers의 길이는 1 이상 100,000 이하이다. numbers의 원소는 0이상 1,000 이하이다. 정답이 너무 클 수도 있으니 문자열로 바꾸어 return한다. 입출력 예 [6, 10, 2] "6210" [3, 30, 34..

이 포스팅은 동빈나님의 코딩테스트 & 알고리즘 대회 핵심 노트 - 투 포인터, 구간 합이라는 강의를 보고 쓴 것이다. 배열의 특정 연속된 구간을 처리하기 원하는 경우 문제에서 연속된 데이터 구간을 처리하기를 원한다면? 다양한 접근 방법을 떠올려 보는 것이 중요! 자주 사용되는 기법들로는 어떤 것들이 있을까? 이 강의에서 나오는 대단한 풀이를 보고 그냥 지나칠 수가 없었다. 세상엔 정말 날고 기는 사람들이 많다는 것을 다시 한 번 느낀다. 분명히 프로그래머스라는 사이트에서 이러한 유형의 문제를 풀때 이중 반복문을 남발했던 것 같은데... 요새 자료구조를 복습하는 입장에서 볼 때, 과거의 나는 효율성이라고는 1도 고민하지 않고 문제를 풀었던 것 같다. 이 강의는 배열의 특정 연속된 구간을 처리하는 것을 목적..