개발자의시작

Selection Sort(선택 정렬) 선택 정렬은 버블 정렬, 삽입 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 선택 정렬을 살펴보기 전에 이전 포스팅에서 설명한 버블 정렬에 대해 먼저 이해하시면 선택 정렬을 이해하는데 도움이 될 겁니다. 아이디어 선택 정렬의 아이디어는 전체 데이터중 가장 작은 값을 앞으로 보내는 것입니다. 데이터의 앞에서부터 순서대로 선택하고 선택된 데이터의 뒤에 있는 데이터들 중 가장 값이 작은 데이터와 스왑(Swap)합니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 알고리즘과 코드를 살펴보겠습니다. 알고리즘 선택 정렬의 ..

Bubble Sort(버블 정렬) 버블 정렬은 삽입 정렬, 선택 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 아이디어 버블 정렬의 아이디어는 전체 데이터중 가장 큰 값을 맨뒤로 보내는 것입니다. 그렇기 때문에 버블 정렬의 전체 과정을 살펴보면 뒤에서부터 앞으로 정렬되는 과정을 보입니다. 전체 데이터 중 가장 값이 큰 데이터를 맨뒤로 보낸 후, 이미 정렬된 값을 제외한 데이터중 가장 값이 큰 데이터를 맨 뒤로 보냅니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 방법과 코드를 통해 알 수 있는데, 데이터를 비교하고 큰 값을 계속해서 뒤로 보내는데 이..

문제링크 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 한수라는 개념이 생소하지만 브루트 포스(Brute Force) 즉, 주먹구구식으로 해결하면 쉽게 해결할 수 있는 문제입니다. 문제의 설명대로 한수는 정수 X의 각 자리가 등차수열을 이루는 경우를 의미합니다. 여기서 주의하실 것은 입력에 사용되는 N은 1000보다 작거나 같은 정수입니다. 즉, 1000은 한수가 아니며 1000보다 ..

문제링크 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 문제 풀이 이번 문제는 계단 오르기 등의 문제와 유사하며 DP를 활용하면 쉽게 해결할 수 있는 문제입니다. 배열에 삼각형 모양..

문제링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 문제 풀이 이친수(pinary number)에 관한 문제입니다. 이친수는 아래의 두가지 성질을 만족합니다. 이친수는 0으로 시작하..

문제링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 전형적인 DP문제입니다. 세 가지 색상을 가지고 있으며, 이웃집(i-1, i+1)과 같은 색을 가질 수 없는 조건이 주어진 문제입니다. 다양한 접근 방법이 있을 수 있지만 저..

문제링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 이번 문제 역시 DP로 풀기 좋은 문제입니다. 2xn 크기의 직사각형을 1x2 도형과 2x1도형을 사용하여 채우는 방법의 경우의 수를 구하는 문제입니다. 염두하여야 할 것은, 2xn 직사각형을 채울 때 2x1크기의 도형은 계속해서 쌓을 수 있지만 1x2크기의 도형은 두 개가 합쳐질 경우 2x2도형으로 만들어 쌓아야 하는 것입니다. 점화식을 유도하기 앞서 경우를 나열해보겠습니다. 설명의 편의를 위해 ..

문제링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 문제 풀이 가장 전형적인 DP문제가 아닌가 생각됩니다. 각 계단에 도달할 때의 점수를 DP에 저장하는 방식으로 풀면 될 것 같습니다. 이 문제는 ..