[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.
[Algorithm] 합이 같은 부분집합(DFS)
❐ 합이 같은 부분집합 ▶︎ 문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10} 이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있습니다. ▷ 입력 예제 1 3 5 6 7 10 ▶︎ 출력 예제 YES ▷ 내 답안 function solution(arr) { let answer = "NO"; let c..
2022. 10. 9.
