[2025 1학기 알고리즘 스터디] 신지은 #2주차
알고리즘 스터디 2주차 시작합니다.. 야호
1. 1로 만들기(https://www.acmicpc.net/problem/1463)
저는 문제를 읽고 힌트에서 멈칫했습니다. 10은 2로 나누어지는 값인데 왜 2로 안 나누고 9가 된 것인가?..
알고 보니 10 -> 5 -> 4 -> 2 -> 1도 가능하지만 연산 횟수가 더 길어서 10 -> 9 -> 3 -> 1로 만드는 것이라네요.
#include <iostream>
using namespace std;
int wink[1000001];
int makeOne(int n) {
wink[1] = 0;
for (int i = 2; i <= n; ++i) {
wink[i] = wink[i - 1] + 1;
if (i % 2 == 0 && wink[i / 2] + 1 < wink[i])
wink[i] = wink[i / 2] + 1;
if (i % 3 == 0 && wink[i / 3] + 1 < wink[i])
wink[i] = wink[i / 3] + 1;
}
return wink[n];
}
int main() {
int n;
cin >> n;
int result = makeOne(n);
cout << result << endl;
return 0;
}
어떤 수를 입력하든 1로 만들어야 하는 문제인데 편리한 기능을 가진 다른 헤더 파일을 사용하는 것보다 반복문이나 입출력으로 간단하게 구현하고 싶어서 iostream만 사용했습니다. 이 문제의 핵심은 1을 빼는 것, 2로 나누는 것, 3으로 나누는 것으로 이루어진 3가지 연산 중에 가장 적은 횟수로 1에 도달하는 경로를 찾는 것입니다.
makeOne함수(최소 연산 횟수 계산 함수)를 만들 때 시작점을 설정합니다. 1은 이미 목표 숫자니까 연산이 필요없고 2부터 n까지 모든 수에 대해 연산 횟수를 계산합니다. 1을 뺀 경우를 먼저 넣은 이유는 항상 가능한 연산이기 때문입니다. 2, 3으로 나누는 건 배수일 때만 가능하니까 이렇게 설정했습니다. wink[i]는 일단 wink[i - 1] + 1로 초기에 설정해줍니다. 만약 i가 2로 나누어 떨어지면, 즉 i = x * 2가 가능한 형태라면 x * 2는 i를 만들 수 있습니다. 3으로 나눠지는 경우도 마찬가지로 wink[i / 3] + 1연산으로 i에 도달할 수 있습니다.
겪은 오류 및 해결
이 문제를 풀면서 오류가 난 부분들이 있었는데 처음에 int wink[1000001]; 부분을 int wink[1000000];로 했다가 입력만 되고 출력 결과는 나오지 않는 오류를 겪었습니다. chatgpt에게 물어보니 n의 최댓값은 1000000인데 배열은 0번부터 시작이므로 wink[1000000]에 접근하려면 배열 크기는 최소 1000001이어야 한다고 합니다. 현재 코드에서 n = 1000000 같은 큰 값이 들어오면 메모리가 초과될 수 있고 그렇게 되면 출력이 안 되거나 프로그램이 조용히 죽는 문제가 발생할 수 있다고 합니다. 이렇게 배열 크기 관련 버그는 조용히 죽는 경우가 많으니 입력 범위보다 1 더 크게 선언하는 습관을 들이면 좋을 것 같습니다!!!
2. 계단 오르기(https://www.acmicpc.net/problem/2579)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n; //사용자 숫자 입력
int score[301] = { 0 }; //전부 0으로
int wink[301] = { 0 }; //전부 0으로
for (int i = 1; i <= n; ++i) {
cin >> score[i]; //계단마다 점수 부여
}
wink[1] = score[1];
if (n >= 2) { //계단이 2개 이상일 경우
wink[2] = score[1] + score[2]; //
}
if (n >= 3) {
wink[3] = (score[1] > score[2] ? score[1] : score[2]) + score[3];
}
for (int i = 4; i <= n; ++i) {
int a = wink[i - 2] + score[i];
int b = wink[i - 3] + score[i - 1] + score[i];
wink[i] = (a > b ? a : b);
}
cout << wink[n] << endl;
return 0;
}
어.. 여기부터 다 날아가서 다시 씁니다아악.
score[i]는 i번째 계단에 적힌 점수이고 wink[i]는 i번째 계단에 왔을 때 얻을 수 있는 최대 점수를 저장합니다.
wink[1] = score[1] -> 첫 번째 계단은 무조건 밟아야 하기 때문에 그대로 점수를 가져옵니다.
wink[2] = score[1] + score[2] -> 계단이 2개 이상일 경우엔 1번 계단 -> 2번 계단을 밟는 것이 유일한 경로이므로 두 점수를 더해줍니다. wink[3] = (score[1] > score[2] ? score[1] : score[2]) + score[3] -> 3번째 계단까지 가는 경로는 1 -> 3 또는 2 -> 3이 있고, 1번과 2번 중 큰 점수를 골라서 3번을 더해줍니다. 4번 계단부터는 2가지 경우의 수를 비교해서 최댓값을 선택합니다. 연속 3칸을 방지하기 위해서 2칸 올라오는 경우(wink[i-2] + score[i])와 2칸 올라오고 1칸 올라오는 경우(wink[i-3] + score[i-1] + score[i])의 수로 나누어 줍니다. 최종적으로 i번째 계단에 도착했을 때 얻을 수 있는 최대 점수인 wink[n]이 출력됩니다.
3.가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int A[1001]; // 수열 A
int wink[1001]; // wink[i]는 A[i]를 마지막으로 하는 LIS 길이
for (int i = 1; i <= n; ++i) {
cin >> A[i];
wink[i] = 1; // 최소 자기 자신 하나는 있으니까 1로 초기화
}
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (A[j] < A[i] && wink[i] < wink[j] + 1) {
wink[i] = wink[j] + 1;
}
}
}
int maxLen = 0;
for (int i = 1; i <= n; ++i) {
if (wink[i] > maxLen) {
maxLen = wink[i];
}
}
cout << maxLen << endl;
return 0;
}이 문제에서는 수열이 주어졌을 때 그 안에서 증가하는 부분 수열 중 가잔 긴 것의 길이를 구하는 문제입니다.
일단 A[i]에 수열의 각 원소를 저장하고 wink[i]에 가장 긴 증가수열의 길이를 저장해 줍니다. 모든 수는 최소 자기 자신 하나만으로 수열이 가능하므로 모두 1로 초기화 시켰습니다. 이 코드들 중에서 제일 중요하다고 생각하는 부분은 wink 배열을 채우는 것인데 중첩 반복문 안에 조건으로 j < i를 넣어 이전의 모든 원소들과 비교를 시켜줍니다. 그리고 A[j] < A[i] 라면 증가수열의 조건을 만족하고 wink[i] < wink[j] + 1이면 wink[i]를 갱신 시켜줍니다.
예를 들어
수열 A: 10 20 10 30 20 50 가 있고 wink 배열을 채운다고 생각해보면
A[1] = 10 -> wink[1] = 1
A[2] = 20
** A[1] < A[2] -> wink[2] = wink[1] + 1 = 2
A[4] = 30
** A[1] = 10 < 30 -> wink[4] = wink[1] + 1 = 2
** A[2] = 20 < 30 -> wink[4] = wink[2] + 1 = 3
** A[3] = 10 < 30 -> wink[4] = wink[3] + 1 = 2 => 이미 wink[4]가 3이므로 건너뜁니다.
** wink[4] = 3
최종적으로 반복문을 사용하여 wink[1]부터 wink[n]까지 보면서 최댓값을 찾아 maxLen에 저장하고 출력해 주는 것입니다!
알고리즘 2주차 스터디 끝! 중간고사 파이팅..
