[자료구조] 프로그래밍 과제1

IT 프로그래밍/자료구조

[자료구조] 프로그래밍 과제1

기술1 2024. 10. 20. 14:14

1번

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	int *sum = new int(0);
	int *min = new int(INT_MAX);
	int *max = new int(INT_MIN);
	double* avg = new double(0);
	double* ars = new double(0);

	cin >> n;

	int* arr = new int[n];


	for (int i = 0; i < n; i++){
		cin >> arr[i];
		*sum += arr[i];
			
		if (arr[i] < *min)
			*min = arr[i];
		if (arr[i] > *max)
			*max = arr[i];
	}

	//평균
	*avg = *sum / n;
	
	//분산
	double *vari = new double(0);
	for (int i = 0; i < n; i++)
	{
		*vari += pow(arr[i] - *avg, 2);
	}
	*vari = *vari / n;
	
	//표준편차
	*ars = sqrt(*vari);

	std::cout << *min << " " << *max << " " << *avg << " " << *ars << std::endl;

	delete sum;
	delete min;
	delete max;
	delete avg;
	delete ars;
	delete vari;
	delete[] arr;

	return 0;
}

여기서는 정수형 변수를 동적으로 할당하여 사용하고 있습니다.
min은 배열에서 가장 작은 값을 찾기 위한 변수이고, max는 가장 큰 값을 찾기 위한 변수입니다.
avg는 평균, ars는 표준편차를 계산하기 위한 변수입니다.

n은 배열의 크기를 나타내는 변수입니다. 사용자가 배열의 크기를 입력하면 그 크기만큼 동적으로 배열을 할당합니다.

입력받은 배열 값을 sum에 계속 더해나가고, 배열의 각 값을 비교하면서 최솟값과 최댓값을 갱신합니다.

분산을 구하기 위해 배열의 각 값에서 평균을 뺀 값을 제곱한 후 이를 모두 더합니다.
그 후, 배열의 크기 n으로 나누어 분산을 구하고, 이 분산의 제곱근을 계산하여 표준편차를 구합니다.

2번

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;




struct Point2D {
	int x, y;
};

double distance(const Point2D& p1, const Point2D& p2) {
	return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2));
}


void resize(Point2D*& points, int& capacity) {
    // 새로운 배열을 현재 크기의 두 배로 생성
    int newCapacity = capacity * 2;
    Point2D* newPoints = new Point2D[newCapacity];

    // 기존 배열의 데이터를 새로운 배열로 복사
    for (int i = 0; i < capacity; ++i) {
        *(newPoints + i) = *(points + i);
    }

    // 기존 배열 삭제
    delete[] points;

    // 새로운 배열로 교체
    points = newPoints;
    capacity = newCapacity;
}


int main()
{
	ifstream infile("input2.txt");
	
	int n;
	infile >> n;


	int capacity = 4;
	int size = 0;

	Point2D* points = new Point2D[capacity];
	
	
	//배열에 점 좌표 입력받기
	for (int i = 0; i < n; ++i)
	{
		if (size == capacity) {
			resize(points, capacity);
		}

		infile >> (*(points + size)).x >> (*(points + size)).y;
		++size;
	}


	infile.close();
	
	double maxDistance = -1;
	Point2D p1, p2;

	for (int i = 0; i < size; ++i) {
		for (int j = i + 1; j < size; ++j) {
			double d = distance(*(points + i), *(points + j));
			if (d > maxDistance) {
				maxDistance = d;
				p1 = *(points + i);
				p2 = *(points + j);
			}
		}
	}

	// 결과 출력
	cout << p1.x << " " << p1.y << endl;
	cout << p2.x << " " << p2.y << endl;
	cout << maxDistance << endl;

	// 동적 메모리 해제
	delete[] points;
	
	return 0;
}

2차원 좌표계에서 여러 개의 점이 주어졌을 때, 가장 먼 두 점을 찾고 그 거리를 계산하여 출력하는 것입니다.

이 함수는 두 점 p1과 p2 사이의 유클리드 거리를 계산합니다.
sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2))는 두 점 사이의 거리 공식을 사용합니다.
- sqrt는 제곱근을 구하는 함수이며, pow(a, 2)는 a를 제곱하는 함수입니다.
- 이 함수는 두 점 사이의 직선 거리를 계산합니다.

void resize(Point2D*& points, int& capacity) {
    int newCapacity = capacity * 2;
    Point2D* newPoints = new Point2D[newCapacity];

    for (int i = 0; i < capacity; ++i) {
        *(newPoints + i) = *(points + i);
    }

    delete[] points;

    points = newPoints;
    capacity = newCapacity;
}

배열이 꽉 찼을 때, 배열의 크기를 두 배로 확장하는 함수입니다.
새로운 배열을 현재 용량(capacity)의 두 배 크기로 할당하고, 기존 데이터를 새 배열로 복사한 후, 기존 배열을 삭제합니다.
확장된 배열의 크기와 그 주소를 갱신하여 프로그램에서 계속 사용할 수 있도록 합니다.

두 개의 중첩된 for 루프를 통해 모든 점들의 쌍을 확인하면서 각 쌍의 거리를 계산합니다.
가장 먼 두 점을 찾아내고, 그때의 거리를 maxDistance에 저장합니다.
p1과 p2에는 가장 먼 두 점이 저장됩니다.

3번

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXWORDS 100
#define MAXLEN 30


int main() {
	char* words[MAXWORDS];
	int n;
	scanf("%d", &n);
	char buf[MAXLEN];



	//방법1
	for (int i = 0; i < n; i++) {
		scanf("%s", words[i]);
	//방법 1의 문제점은 words[i]가 초기화되지 않았다는 점입니다. 메모리 접근 오류가 발생할 수 있습니다.
	//따라서 충분한 공간을 가질 수 있도록 동적 메모리 할당을 해줍니다. 
	
	//올바른 코드
		
	for (int i = 0; i < n; i++) {
		words[i] = (char*)malloc(MAXLEN * sizeof(char));
	}
		scanf("%s", words[i]);
	}

	//방법2
	scanf("%s", buf);
	words[i] = buf;
	//반복문 안에서 재사용되면서 모든 입력 문자열이 마지막에 입력된 문자열로 덮어집니다. 

	//해결방법 : 각 문자열에 대해 새로운 메모리를 할당해주면서 복사하는 방식으로 진행합니다.
	//올바른 코드
	for (int i = 0; i < n; i++) {
		scanf("%s", buf);
		words[i] = (char*)malloc((strlen(buf) + 1) * sizeof(char)); // 동적 메모리 할당
		strcpy(words[i], buf); // 문자열 복사
	}


	//방법3:
	scanf("%s", buf);
	strcpy(words[i], buf);
	}
	//초기화되지않은 포인터로 words[i]가 가리키는 메모리 공간이 제대로 할당되지 않아 메모리 접근 오류가 발생합니다. 

	//해결방법 : words[i]에 메모리를 할당한 후에 문자열을 복사합니다. 
	//올바른 코드
	for (int i = 0; i < n; i++) {
		scanf("%s", buf);
		words[i] = (char*)malloc((strlen(buf) + 1) * sizeof(char));
	strcpy(words[i], buf);
	}



	for (int i = 0; i < n; i++)
		printf("%s\n", words[i]);



	return 0;
}

문제점1) 초기화되지 않은 포인터로 인해 발생되는 문제

words[i]에 메모리를 할당하지 않은 상태에서 scanf로 문자열을 입력받으려 하고 있습니다. 초기화되지 않은 포인터에 접근하는 시도로 인해 메모리 접근 오류가 발생할 수 있습니다.

for (int i = 0; i < n; i++) {
    words[i] = (char*)malloc(MAXLEN * sizeof(char));
    scanf("%s", words[i]);
}

이는 동적 메모리 할당으로 메모리 접근 오류를 방지할 수 있습니다.

문제점2) buf 배열이 반복문 내에서 재사용되는 문제

scanf("%s", buf);
words[i] = buf;

이 코드는 buf라는 하나의 고정된 배열에 문자열을 입력받은 후, 해당 배열의 주소를 words[i]에 저장합니다. 이 경우 buf 배열은 반복문을 돌면서 계속 덮어쓰여져 결국 모든 입력 문자열이 마지막 입력된 문자열로 덮어지게 됩니다.

for (int i = 0; i < n; i++) {
    scanf("%s", buf);
    words[i] = (char*)malloc((strlen(buf) + 1) * sizeof(char)); // 문자열 길이에 맞게 메모리 할당
    strcpy(words[i], buf); // 문자열을 동적으로 할당한 메모리로 복사
}

buf에서 입력받은 문자열을 words[i]로 복사하면서, 각 단어에 맞게 메모리를 동적으로 할당합니다. strlen(buf) +1은 문자열 길이와 널 종결 문자 (\0)을 포함하기 위해 사용됩니다.

문제점 3) 초기화되지 않은 포인터에 복사하려는 문제

scanf("%s", buf);
strcpy(words[i], buf);

이 코드는 words[i]에 메모리를 할당하지 않은 상태에서 strcpy로 문자열을 복사하려고 시도하고 있습니다. 이로 인해 메모리 접근 오류가 발생할 수 있씁니다.

for (int i = 0; i < n; i++) {
    scanf("%s", buf);
    words[i] = (char*)malloc((strlen(buf) + 1) * sizeof(char)); // 문자열에 맞게 메모리 할당
    strcpy(words[i], buf); // buf에서 words[i]로 문자열 복사
}

이는 words[i]에 적절한 메모리를 할당한 후 문자열을 복사하여 메모리 접근 오류를 방지할 수 있습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXWORDS 100
#define MAXLEN 30

int main() {
    char* words[MAXWORDS]; // 단어를 저장할 포인터 배열
    int n;
    scanf("%d", &n); // 단어 개수 입력
    char buf[MAXLEN]; // 단어 입력을 받을 버퍼

    // 각 단어를 입력받아 동적 메모리 할당 및 저장
    for (int i = 0; i < n; i++) {
        scanf("%s", buf); // 단어 입력받기
        words[i] = (char*)malloc((strlen(buf) + 1) * sizeof(char)); // 문자열 크기에 맞게 메모리 할당
        strcpy(words[i], buf); // 입력받은 단어를 동적 메모리로 복사
    }

    // 저장된 단어 출력
    for (int i = 0; i < n; i++) {
        printf("%s\n", words[i]);
    }

    // 동적 메모리 해제
    for (int i = 0; i < n; i++) {
        free(words[i]); // 각 단어의 메모리 해제
    }

    return 0;
}

4번

#include <iostream>
#include <fstream>
#include <sstream>
#include <cctype>
#include <cstring>

using namespace std;


int main() {
    const int MAX_WORDS = 1000;
    const int MAX_WORD_LENGTH = 20;
    string words[MAX_WORDS];
    int wordCount = 0;

    ifstream infile("input4.txt");


    string word;
    while (infile >> word) {
        if (word.length() >= 2) {
            bool found = false;
            for (int i = 0; i < wordCount; ++i) {
                if (words[i] == word) {
                    found = true;
                    break;
                }
            }
            if (!found && wordCount < MAX_WORDS) {
                words[wordCount] = word;
                wordCount++;
            }
        }
    }

    infile.close();

    

    // 정렬된 단어와 빈도 출력
    for (int i = 0; i < wordCount; ++i) {
        cout << words[i] << endl;
    }

    return 0;
}

텍스트 파일로부터 단어들을 읽어들인 후, 중복되지 않은 단어들을 저장하고 출력하는 프로그램입니다. 단어는 파일에서 하나씩 읽어오며, 단어의 길이가 2이상인 것만 처리합니다.

infile >> word는 파일에서 하나의 단어를 읽어옵니다.
word.length() >= 2는 단어의 길이가 2 이상인 경우에만 처리하도록 합니다. 즉, 길이가 1인 단어는 저장하지 않습니다.
중복을 확인하기 위해 found라는 불리언 변수를 사용합니다. 이미 저장된 단어가 있는지 확인하는 루프를 통해, 배열에 같은 단어가 존재하면 found를 true로 설정하고 반복을 중단합니다.
중복된 단어가 없고(!found), 배열의 크기가 최대 단어 개수를 넘지 않았을 경우(wordCount < MAX_WORDS), 새로운 단어를 배열에 저장하고 wordCount를 증가시킵니다.

5번

#include <iostream>
#include <fstream>
#include <sstream>
#include <cctype>
#include <cstring>

using namespace std;

// 단어를 정리하는 함수
string cleanWord(const string& word) {
    string cleaned;
    for (char c : word) {
        if (isalpha(c)) { // 문자일 경우만 추가
            cleaned += tolower(c); // 소문자로 변환
        }
    }
    return cleaned;
}

int main() {
    const int MAX_WORDS = 1000;
    const int MAX_WORD_LENGTH = 20;
    string words[MAX_WORDS];
    int frequencies[MAX_WORDS] = { 0 };
    int wordCount = 0;

    ifstream infile("input4.txt");


    string word;
    while (infile >> word) {
        string cleanedWord = cleanWord(word);
        if (cleanedWord.length() >= 2) {
            bool found = false;
            for (int i = 0; i < wordCount; ++i) {
                if (words[i] == cleanedWord) {
                    frequencies[i]++;
                    found = true;
                    break;
                }
            }
            if (!found && wordCount < MAX_WORDS) {
                words[wordCount] = cleanedWord;
                frequencies[wordCount] = 1;
                wordCount++;
            }
        }
    }

    infile.close();

    // 단어와 빈도 정렬
    for (int i = 0; i < wordCount - 1; ++i) {
        for (int j = i + 1; j < wordCount; ++j) {
            if (words[i] > words[j]) {
                swap(words[i], words[j]);
                swap(frequencies[i], frequencies[j]);
            }
        }
    }

    // 정렬된 단어와 빈도 출력
    for (int i = 0; i < wordCount; ++i) {
        cout << words[i] << ": " << frequencies[i] << endl;
    }

    return 0;
}

이 코드는 텍스트 파일로부터 단어들을 읽어들이고, 각 단어의 빈도를 계산한 후, 알파벳 순서로 정렬하여 단어와 빈도를 출력하는 프로그램입니다. 각 단어는 소문자로 변환되며, 문자 이외의 특수 문자는 제거됩니다.

string cleanWord(const string& word) {
    string cleaned;
    for (char c : word) {
        if (isalpha(c)) { // 문자일 경우만 추가
            cleaned += tolower(c); // 소문자로 변환
        }
    }
    return cleaned;
}

기능: 주어진 단어에서 알파벳 문자만 남기고, 모든 문자를 소문자로 변환합니다. 이 함수는 단어에서 특수문자나 숫자를 제거하고, 대문자를 소문자로 바꿉니다.
작동 방식:
- 입력된 문자열 word의 각 문자를 확인하면서, 알파벳 문자(isalpha(c))만을 선택적으로 cleaned에 추가합니다.
- tolower(c)를 통해 대문자를 소문자로 변환합니다.

const int MAX_WORDS = 1000;
const int MAX_WORD_LENGTH = 20;
string words[MAX_WORDS];
int frequencies[MAX_WORDS] = { 0 };
int wordCount = 0;

ifstream infile("input4.txt");

MAX_WORDS: 최대 1000개의 단어를 저장할 수 있는 배열 크기를 설정합니다.
words: 단어를 저장할 배열입니다. 각 배열 요소는 문자열로 이루어져 있습니다.
frequencies: 각 단어의 빈도를 저장할 배열입니다. frequencies[i]는 words[i]에 저장된 단어의 빈도를 나타냅니다.
wordCount: 현재 저장된 단어의 개수를 추적합니다.
infile: input4.txt라는 파일을 열어 입력을 받기 위한 파일 스트림 객체입니다.

string word;
while (infile >> word) {
    string cleanedWord = cleanWord(word);
    if (cleanedWord.length() >= 2) {
        bool found = false;
        for (int i = 0; i < wordCount; ++i) {
            if (words[i] == cleanedWord) {
                frequencies[i]++;
                found = true;
                break;
            }
        }
        if (!found && wordCount < MAX_WORDS) {
            words[wordCount] = cleanedWord;
            frequencies[wordCount] = 1;
            wordCount++;
        }
    }
}

파일에서 단어를 하나씩 읽어오고, cleanWord 함수를 사용해 문자를 정리한 후 그 단어를 처리합니다.
**cleanWord**로 변환한 단어의 길이가 2 이상일 때만 처리하며, 길이가 1인 단어는 제외합니다.
중복 처리:
- 이미 words 배열에 존재하는 단어는 frequencies[i]++로 해당 단어의 빈도를 1 증가시킵니다.
- 중복되지 않은 새로운 단어는 words 배열에 추가하고, 빈도는 1로 설정합니다.

for (int i = 0; i < wordCount - 1; ++i) {
    for (int j = i + 1; j < wordCount; ++j) {
        if (words[i] > words[j]) {
            swap(words[i], words[j]);
            swap(frequencies[i], frequencies[j]);
        }
    }
}

알파벳 순서로 정렬: words 배열에 저장된 단어들을 서로 비교하여 알파벳 순서로 정렬합니다.
swap: 두 단어의 순서가 알파벳 순서에 맞지 않으면 swap 함수를 사용해 words[i]와 words[j]의 자리를 바꿉니다. 동시에 해당 단어의 빈도(frequencies[i]와 frequencies[j])도 함께 바꿉니다

6번

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int countWords(const string& str) {
    stringstream ss(str);
    string word;
    int wordCount = 0;

    while (ss >> word) {
        wordCount++;
    }

    return wordCount;
}

int main() {
    string input;

    while (true) {
        cout << "$ ";  

        getline(cin, input);  // 사용자 입력 받기

        if (input == "exit")  // 'exit' 입력 시 종료
            break;

        cout << input << " : " << input.length() << " : " << countWords(input) << endl;
    }

    return 0;
}

countwords

기능: 이 함수는 주어진 문자열에서 단어의 개수를 세는 역할을 합니다.
작동 방식:
- stringstream ss(str)를 사용하여 입력 문자열을 stringstream으로 변환합니다. stringstream은 문자열을 스트림처럼 처리할 수 있는 클래스입니다.
- while (ss >> word)는 공백을 기준으로 단어를 하나씩 추출하며, 각 단어를 추출할 때마다 wordCount를 1씩 증가시킵니다.
- 최종적으로 wordCount는 문자열에 포함된 단어의 수를 나타내며, 그 값을 반환합니다.

main

while (true) 루프:
- 이 루프는 사용자가 'exit'을 입력할 때까지 무한히 반복됩니다.
- cout << "$ "는 사용자에게 입력을 기다리고 있다는 표시(프롬프트)를 출력합니다.
- getline(cin, input)은 사용자가 입력한 문자열을 받아 변수 input에 저장합니다. getline은 줄바꿈을 기준으로 전체 문자열을 읽어들입니다.
입력 처리 및 종료 조건:
- if (input == "exit"): 사용자가 'exit'을 입력하면 break를 통해 무한 루프를 종료하고 프로그램이 종료됩니다.
입력된 문자열의 정보 출력:
- cout << input << " : " << input.length() << " : " << countWords(input) << endl;:
  - 입력된 문자열을 그대로 출력합니다.
  - input.length()는 입력된 문자열의 길이(문자의 개수)를 계산합니다.
  - countWords(input)는 입력된 문자열에 포함된 단어의 개수를 계산하여 출력합니다.

#include <iostream>
using namespace std;


int main() {
	int n;
	cout << "n 값을 입력하세요 (2에서 10000사이)";

	cin >> n;

	bool isPrime[10001];

	for (int i = 2; i <= n; i++) {
		isPrime[i] = true;
	}

	for (int i = 2; i * i <= n; i++)
	{
		if (isPrime[i]) {
			for (int j = i * i; j <= n; j += i)
				isPrime[j] = false;
		}
	}

	//소수 출력
	cout << "소수 :";
	for (int i = 2; i <= n; i++) {
		if (isPrime[i])
			cout << i << " ";
	}
	cout << endl;

	return 0;
}

n: 사용자로부터 입력받은 값으로, 이 값은 2부터 n까지의 소수를 찾는 범위를 지정합니다.
입력된 n 값이 2에서 10,000 사이여야 하며, 이 프로그램은 10,000까지의 소수를 계산할 수 있습니다.

이 부분은 에라토스테네스의 체 알고리즘을 구현한 부분입니다.
작동 방식:
1. i가 소수라면, i의 배수는 소수가 아니므로 모두 false로 설정합니다.
2. 반복문은 i * i <= n까지 수행됩니다. 이는 소수를 구하기 위해 n의 제곱근까지만 확인하면 충분하기 때문입니다.
3. i의 배수(i * i, i * i + i, i * i + 2*i, ...)는 모두 소수가 아니므로 isPrime[j]를 false로 설정합니다.

위에서 구한 소수들을 출력합니다.
**isPrime[i]가 true**인 숫자들만 출력합니다. 즉, 소수로 판별된 숫자들만 출력됩니다.

'IT 프로그래밍 > 자료구조' 카테고리의 다른 글

[자료구조] 그룹 엑티비티 3 전문 (1)	2024.10.22
[자료구조] 그룹 액티비티 3 (0)	2024.10.22
[자료구조] 그룹액티비티2 (1)	2024.10.20
[자료구조] 프로그래밍과제1 그룹액티비티 (0)	2024.10.20
스택과 C++ STL 컨테이너 (0)	2024.10.15

현재글[자료구조] 프로그래밍 과제1

기술 블로그

string 설명, 거듭제곱 구하는 법, 빈곤 정의, 오블완, 빈곤이란, x5x6, 말레이시아 경제, 티스토리챌린지, 백준 10813, C++, strtok기능, 따배시 강의, 빈곤의 사회학적 정의, 따배시, 빈곤이란 무엇인가?, 녹색혁명, 백준2284번, 따배시 강의 요약, 프로그래밍 예제, 빈곤의 원인,

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

기술 블로그