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

1. 셸 정렬 셸 정렬은 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다. 전체 원소에 데헤 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하면 전체 연산 횟수를 줄일 수 있다. 셸 정렬에서 부분집합을 만드는 기준이 되는 간격을 매개변수 h에 저장한다. h에 대해 h가 1이 될 때까지 1/2씩 감소시키고, 각 단계마다 셸 정렬을 순환 호출한다. 처음에 h는 입력 배열의 길이에 1/2한 자연수를 초기화 값으로 받는다. 셸 정렬의 전체 연산 횟수는 간격 h에 의해 영향을 받기 때문에 알고리즘의 성능을 분석하기가 쉽지 않다. 일반적으로 셸 정렬의 시간 복잡도를 $$ O(n^{1.25}) ..

1. Array.fill([]) 자료구조 책을 보고 기수정렬을 프로그래밍할 때 였다. 기수 정렬 포스팅에서는 버킷이라는 객체를 만들때 오브젝트 자체를 생성했지만, 원래는 이 차원 배열을 만들려고 했었다. 하지만 그러지 못했다. 왜냐하면 Array.fill([]) 함수 때문이었다. 다음 프로그램을 보자. const arr = new Array(3).fill([]); arr[0].push(1); /* 이 함수의 출력은? */ console.log(arr); /* 정답 */ /* [ [1], [1], [1] ] */ 위 프로그램의 출력 결과는 무엇일까? 나는 arr의 첫 번째 원소 배열에만 1이라는 요소가 추가될 줄만 알았다. 하지만 결과는 아니었다. 모든 원소 배열에 1이 추가됐던 것이다. 내가 키워드를 잘..

1. 기수 정렬 기수 정렬은 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하는 배열이다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키 값의 길이만큼 기수 정렬을 반복한다. 숫자는 기본적으로 10진수로 표현되기 때문에, 키 값을 가진 원소들을 정렬할 때는 0부터 9까지 총 10 개의 버킷을 사용한다. 정렬의 반복 횟수는 입력 배열의 원소 중 최대 값의 길이 만큼이다. 예를 들어 [103, 3, 22]를 기수정렬을 이용하여 반복해야 할 때, 입력 배열 중에서는 103이 최댓값이므로, 기수 정렬의 반복횟수는 103의 길이인 3이 된다. 2. 동작 순서 길이가 5인 입력배열 [3, 55, 7, 17, 1]..

문제설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하..

1. 계수 정렬 앞에서 포스팅한 것 중 제일 빠른 알고리즘을 고르자면 O(Nlog₂N)의 속도를 가지는 퀵 정렬, 병합 정렬, 힙 정렬이 있었다. 하지만 이번 포스팅에서는 이 세 개의 정렬보다 더 빠른 속도 O(N)의 속도를 가지는 계수 정렬에 대해서 포스팅하려고 한다. 단, 아래와 같은 조건이 주어졌을 경우다. 5 4 3 2 1 1 1 1 3 4 5 5 2 2 2 다음과 같은 5이하의 원소를 가진 배열의 원소들을 오름차순으로 정렬하시오 2 . 동작 순서 동작 순서는 다음과 같이 간단하다. 1에서 5까지의 원소의 개수를 카운팅한다. 카운팅한 개수만큼 원소들을 나열한다. 끝. 그림을 이용해서 설명을 해보도록 하겠다. 밑의 배열을 오름차순으로 정렬하려고 한다. 5 이하의 모든 자연수의 개수를 세기위해 5라는..