[Algorithm] 두 배열 합치기(Two Pointers)
❐ 두 배열 합치기 ▶︎ 문제 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요. ▷ 입력 예제 [1, 3, 5], [2, 3, 6, 7, 9] ▶︎ 출력 예제 [1, 2, 3, 3, 5, 6, 7, 9] ▷ 문제설명 시간복잡도나 효율성을 고려하지 않고 문제를 풀 수 있는 가장 간단한 방법을 생각해보자. 두 개의 배열을 하나로 합친 뒤 자바스크립트의 sort( ) 메서드를 활용해서 배열을 정렬하는 방법을 떠올릴 수 있다. 이 방법은 간단하지만 최선이라고는 할 수 없다. 자바스크립트에서 사용되는 v8 엔진은 'Tim Sort'의 정렬 알고리즘을 사용하는데, 이것은 Merge Sort를 기반으로 최적화한 알고리즘이고 O(n log n)의 시간복잡도를 가진다..
2022. 11. 4.
[Algorithm] 경로 탐색(그래프-인접리스트)
❐ 경로 탐색(인접리스트) ▶︎ 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. ▷ 입력 예제 5, [ [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5] ] ▶︎ 출력 예제 6 ▷ 문제설명 인접행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방법이다. 인접 행렬은 정점이 연결되어 있는지 확인하기 위해서 graph[a][b]의 요소만 확인할 수 있기 때문에 직관적이고 구현하기 쉽다는 장점이 있다. 하지만 구현해야 하는 그래프의 정점(vertex, 노드)의 개수가 10억개라면 어떨까..
2022. 10. 23.
[Algorithm] 경로 탐색(그래프-인접행렬)
❐ 경로 탐색(인접행렬) ▶︎ 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. ▷ 입력 예제 5, [ [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5] ] ▶︎ 출력 예제 6 ▷ 문제설명 그래프를 그려 문제를 해결해 보자. 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 문제의 그래프는 정점이 단순히 연결되어 있을 뿐 아니라 방향을 가리키고 있다. 예를 들어 1번 정점(vertex, 노드)은 2, 3, 4번 정점을 가리키고 있고, 1번과 2번 정점은 서로를 가리키..
2022. 10. 22.
