천천히 가는 것을 걱정하지 말고 서있는 것을 걱정하라.

소개 현재 인덱스 위치 값과 이미 정렬된 부분 배열의 값들과 비교하여 들어갈 위치를 찾아 정렬한다. 성능이 좋아 다른 알고리즘의 일부로도 사용한다. 해당 삽입 지점 이후 배열 값들이 한 칸씩 밀리기 때문에 배열 길이가 길수록 효율이 떨어진다. 과정 코드 첫 번째 인덱스 $nums[i = 0]$ 의 값은 정렬되어 있다고 가정하고 시작한다. compidx를 이용하여 $i$ 인덱스의 값이 들어갈 인덱스를 정렬된 부분 배열 구간 ($0$ ~ $i - 1$) 에서 찾는다. public static void main(String[] args) { int[] nums = { 3, 7, 2, 5, 1, 4 }; int len = nums.length; for (int i = 1; i < len; ++i)..

소개 배열을 조회하면서 현재 위치에 들어갈 값 (남은 숫자들 중 가장 크거나 작은 값) 을 찾아 정렬한다. 과정 코드 현재 위치 $i$ 값과 배열의 나머지 모든 값을 비교하여 가장 작은 값을 가진 인덱스 $idx$ 를 $j$로 갱신한다. 두 번째 for문이 끝나면 $i$와 $idx$ 위치의 값을 바꾼다. public static void main(String[] args) { int[] nums = { 8, 5, 2, 6, 9, 4, 1, 3, 0, 7 }; int len = nums.length; for (int i = 0; i ..

소개 배열의 인접한 두 요소 값들을 비교하여 정렬한다. 과정 코드 $j$ 인덱스 값이 $j + 1$ 인덱스 값보다 크다면 두 숫자의 위치를 바꿔준다. 첫 번째 for문이 한 번 종료될 때마다 가장 마지막 인덱스에 숫자가 하나씩 정렬된다. public static void main(String[] args) { int[] nums = { 6, 7, 2, 8, 1, 4 }; int len = nums.length; for (int i = 0; i nums[j + 1]) Swap(nums, j, j + 1); } } } 결과 계산 복잡도 Time Complexity : for..

네트워크 유량 (Network Flow) ? 도입 네트워크를 이용해 수백 GB에 달하는 아주 큰 파일을 다운로드하는 중이라고 하자. 이렇게 전송받을 자료의 양이 많을 때 우리가 관심을 갖는 부분은 서버가 보낸 패킷이 내 컴퓨터에 몇 밀리초 만에 도착하느냐가 아니라, 1초에 몇 MB의 자료를 전송받을 수 있느냐이다. 네트워크를 구성하는 케이블들에는 일정한 대역폭이 있기 때문에, 단위 시간당 일정량 이상의 자료를 전송할 수 없다. 따라서 이렇게 큰 파일을 다운로드할 경우 최단 경로로만 1초에 1MB를 전송받는 것보다, 패킷을 여러 경로로 나누어 보내 그중 일부가 좀더 먼길을 돌아오더라도 초당 10MB를 전송받는 것이 훨씬 이득이다. 아래 그림 (a) 는 한 컴퓨터 네트워크의 구성을 표현하는 그래프를 보여준다..

그래프 (Graph) ? 도입 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 우리 주변에서 찾을 수 있는 예를 들면, 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 있을 것이다. 그래프의 정의 그래프 $G(V, E)$ 는 아래 요소들로 구성된 자료 구조이다. 어떤 자료나 개념을 표현하는 정점 (Vertex) 들의 집합 $V$. 정점들을 연결하는 간선 (Edge) 들의 집합 $E$. 아래 그림은 1 ~ 5까지의 번호가 주어진 정점들과 이들을 연결하는 간선으로 구성된 그래프들의 예시다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. 따라서 다른 모양이지만 위 그림은 모..

문제설명 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽으로 접습니다. 종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다. 위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다. 종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하..

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N - 1)번 집의 색은 i - 1번, i + 1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 솔루션 몇 가지 숫자를 표현해보면 규칙을 찾을 수 있다. 1을 표현할 수 있는 방법의 개수는 1. 2를 표현할 수 있는 방법의 개수는 2. 3을 표현할 수 있는 방법의 개수는..