J's tistory

🔎 문제선택 문제는 n개의 숫자들 중에서 k번째로 작은 수를 찾는 문제이다.이를 위해 몇 가지 간단한 해결 방법을 생각해 볼 수 있다.최소 숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 해당 숫자를 제거한다.숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는다.하지만 위 경우는, 최악의 경우 $O(kn)$과 $O(nlogn)$ 수행 시간이 걸린다. 🔎 핵심 아이디어선택 문제는 숫자 찾기 문제이므로, 임의의 숫자를 효율적으로 찾을 수 있는 이진 탐색(Binary Search)에서 아이디어를 얻을 수 있다.📌 이진 탐색 (Binary Search) 이란?정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교하여, 입력을 1/2로 나눈 두 부분 중에서 한 부분만 이어서 탐색한다. Sm..

🔎 문제한수는 크기가 $2^{N}⨉2^{N}$인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 $2^{N-1}⨉2^{N-1}$로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 $2^{2}⨉2^{2}$  크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다.🔎 입력첫째 줄에 정수 N, r, c가 주어진다.🔎 출력r행 c열을 몇 번째로 방문했는지 출력한다.🔎 제한$1 ≤ N ≤ 15$$0 ≤ r, c ✅ 예제 1입력2 3 1출력11✅ 예제 2입력3 7 7출력63 📌..

🔎 퀵 정렬이란?퀵 정렬은 분할 정복 알고리즘으로 분류되지만, 사실은 정복 후 분할하는 과정이다.또한, 부분 문제의 수는 2개로, 각 부분 문제의 크기는 일정하지 않다. 💡 정렬 과정퀵 정렬은 피봇(pivot)이라고 하는 배열의 한 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 가운데 위치시킨다. 그다음 분할된 부분 문제들에 대해서도 똑같은 과정을 순환적으로 반복한다. ⚠️ 주의할 점이때 피봇은 분할된 왼편이나 오른편, 그 어느 부분에도 해당되지 않는다.  🔽 그림으로 이해하기위 그림을 보면 60이 피봇으로 선정되어, 60보다 작은 숫자들은 왼편으로, 60보다 큰 숫자들은 오른편으로 이동하였다. 이제 퀵 정렬 알고리즘에 대해 ..

🔎 문제아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기..

🔎 합병 정렬이란?합병 정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘이다. 즉, $n$개의 숫자들을 $n/2$개 씩 2개의 부분문제로 분할하고, 각각의 부분문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 다시 합병하여 정렬한다. 합병 과정이 문제를 정복하는 것이다. 합병(Merge)이란?합병은 2개의 각각 정렬된 숫자들을 하나의 정렬된 숫자들로 합치는 것이다. 🔽 다음은 각각 원소들이 정렬되어 있는 배열 A와 B를 합병하여 배열 C에 저장되어 있는 것을 보여준다. 🔎 합병 정렬 알고리즘MergeSort(A, p, q){ // 입력: A[p] ~ A[q] if(p  Line 3 : 정렬할 부분의 원소의 수가 2개 이상인 경우에만 ..

🔎 분할 정복 알고리즘이란?분할 정복 알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하고, 이들의 해를 취합하여 원래 문제의 해를 얻는 방식이다.이때, 분할된 입력에 대한 문제를 부분문제(subproblem)라고 하고, 부분문제의 해를 부분해라고 한다.부분문제는 더 이상 분할할 수 없을 때까지 분할한다. 🔽 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 $\frac{n}{2}$인 예시분할 과정은 다음과 같다.처음에 주어진 문제가 3개의 부분문제로 분할되고, 각 부분문제의 입력의 크기는 $\frac{n}{2}$이다.분할이 두 번 진행되면 부분 문제의 크기는 다시 각각 3개로 분할(총 ..

🔎 알고리즘이란?알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다. 여기서 주어지는 문제는 컴퓨터를 이용하여 해결할 수 있어야 한다. 따라서 알고리즘에는 입력이 주어지고, 알고리즘이 수행되면 문제에 대한 답이 출력된다.  알고리즘의 일반적인 특성은 다음과 같다. 정확성💡알고리즘은 모든 입력에 대해 올바른 해를 주어야 한다.만약 어떤 알고리즘에 대해서는 올바른 해를 출력하고, 다른 몇몇 알고리즘에 대해서는 올바르지 않은 결과를 출력한다면 이는 알고리즘이라고 할 수 없다. 수행성💡알고리즘의 각 단계는 컴퓨터에서 수행할 수 있어야 한다.알고리즘에 애매모호한 표현이 있으면 프로그래밍 언어로 바꿀 수 없으므로, 컴퓨터에서 수행시킬 수 없다. 유한성💡알고리즘은 유한한 시간 내에 수행되어야 한다.알고리즘의..

문제어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 코드 : C++가능한 자릿수는 3자리 까지 가능하다.이때, 자연수가 1자릿수이거나 2자릿수인 경우는 항상 각 자릿수가 등차수열이 된다.따라서 입력으로 받은 숫자가 100미만인 경우는 항상 입력 받은 수를 그대로 출력했고,자릿수가 3인 경우에만 백의 자릿수와 십의 자릿수의 차이가 십의 자릿수와 일의 자릿수와 똑같은지 ..

🔎 문제B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 ⌨️ 입력첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다. 💻 출력첫째 줄에 B진법 수 N을 10진법으로 출력한다. 1. C++#include #include using namespace std;int charToNum(char c){ if ('0' > binaryString >> n; long long result = stringToNu..

🔎 문제가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. ⌨️ 입력첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의..