[CS50 Practice - #Average Temperatures]
Average High Temperatures
Learning Goals
- 구조체(structs) 작업 연습
- 정렬 알고리즘 적용 연습
Background
우리는 역사상 가장 더운 날씨로 매년 기록을 깨고 있는 것 같습니다. 기후 과학자들은 가까운 미래의 상황을 더 잘 예측하고 대비할 수 있도록 수년에 걸쳐 "new normals"이라고 불리는 것을 추적합니다. 공식 normals은 30년 단위로 계산되며 연간 단위로 구성됩니다. 연간/계절, 월간, 일별, 시간별 평균과 약 15,000개의 미국 기상 관측소에서 수집한 기온, 강수량 및 기타 기후 변수에 대한 통계로 구성됩니다.
7월은 미국의 대부분의 대도시에서 일년 중 가장 더운 달입니다. 화씨 80도 이상의 주간 기온은 거의 모든 곳에서 정기적으로 발생합니다. 예외는 태평양 연안의 일부 도시입니다.
이 문제에서는 10개 도시의 평균 최고 기온 값을 내림차순으로 정렬합니다.
Hints
- 한 구조체를 다른 구조체에 복사할 때 개별 요소를 할당할 필요가 없습니다. 전체 구조체는 하나의 명령문으로 할당될 수 있습니다.
- void 함수가 어떤 값도 반환할 수 없더라도 return 문을 사용하여 함수를 종료할 수 있습니다.
Demo
Getting Started
- GitHub 계정을 사용하여 cs50.dev에 로그인합니다.
- 터미널 창 내부를 클릭하고 cd를 실행합니다.
- 코드 공간에 temps.zip이라는 zip을 다운로드하려면 wget https://cdn.cs50.net/2022/fall/labs/3/temps.zip을 실행하고 Enter를 누르세요. wget과 다음 URL 또는 해당 문제에 대한 다른 문자 사이의 공백을 간과하지 않도록 주의하세요!
- 이제 unzip temps.zip을 실행하여 temps라는 폴더를 만듭니다.
- 더 이상 ZIP 파일이 필요하지 않으므로 rm temps.zip을 실행하고 프롬프트에서 “y”와 Enter를 차례로 입력하면 됩니다.
Implementation Details
main 함수는 temps 배열을 초기화하고, sort_cities 함수를 호출하고 정렬된 순서로 배열을 인쇄합니다. 원하는 O(n2) 정렬 알고리즘(버블 정렬, 선택 정렬 또는 삽입 정렬 등)을 사용하여 배열을 온도별로 내림차순으로 정렬합니다.
생각해보기
어떤 정렬 알고리즘을 선택했으며 그 이유는 무엇입니까?
나의 풀이
문제
// Practice working with structs
// Practice applying sorting algorithms
#include <cs50.h>
#include <stdio.h>
#define NUM_CITIES 10
typedef struct
{
string city;
int temp;
}
avg_temp;
avg_temp temps[NUM_CITIES];
void sort_cities(void);
int main(void)
{
temps[0].city = "Austin";
temps[0].temp = 97;
temps[1].city = "Boston";
temps[1].temp = 82;
temps[2].city = "Chicago";
temps[2].temp = 85;
temps[3].city = "Denver";
temps[3].temp = 90;
temps[4].city = "Las Vegas";
temps[4].temp = 105;
temps[5].city = "Los Angeles";
temps[5].temp = 82;
temps[6].city = "Miami";
temps[6].temp = 97;
temps[7].city = "New York";
temps[7].temp = 85;
temps[8].city = "Phoenix";
temps[8].temp = 107;
temps[9].city = "San Francisco";
temps[9].temp = 66;
sort_cities();
printf("\nAverage July Temperatures by City\n\n");
for (int i = 0; i < NUM_CITIES; i++)
{
printf("%s: %i\n", temps[i].city, temps[i].temp);
}
}
// TODO: Sort cities by temperature in descending order
void sort_cities(void)
{
// Add your code here
}버블 정렬 (나의 첫번째 풀이)
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
// TODO: Sort cities by temperature in descending order
void sort_cities(void)
{
// Add your code here
// ● 내림차순 버블정렬
// ● 실행 시간의 상한 O(n^2) | 실행 시간의 하한 Ω(n^2)
// ** 실행 시간의 상한 최대치로 구현;;
// (n-1)*(n-1)
for (int i = 0; i < NUM_CITIES; i++)
{
for ( int j = 0; j < NUM_CITIES; j++ )
{
if (temps[j].temp < temps[j + 1].temp)
{
avg_temp tmp; // 구조체 복사
tmp = temps[j];
temps[j] = temps[j + 1];
temps[j + 1] = tmp;
}
}
}문제점 : 시간복잡도를 최대로 갖는 방법으로 정렬함
버블 정렬 (실행 시간의 상한 최소화)
// TODO: Sort cities by temperature in descending order
void sort_cities(void)
{
// Add your code here
// ● 내림차순 버블정렬
// ● 실행 시간의 상한 O(n^2) | 실행 시간의 하한 Ω(n^2)
// ** 실행 시간의 상한을 최소로 하는 방법
// 더 이상의 교환이 없으면 멈춘다.
int counter = 1; // 교환 횟수를 카운터 변수 할당 (0이 아닌 숫자 아무거나)
avg_temp tmp; // 구조체 복사
while (counter != 0) // 조건문이 참이 될 때까지 반복 (counter가 0이면 중단)
{
counter = 0; // 카운터 0으로 초기화
for (int i = 0; i < NUM_CITIES; i++)
{
if (temps[i].temp < temps[i + 1].temp)
{
tmp = temps[i];
temps[i] = temps[i + 1];
temps[i + 1] = tmp;
counter ++;
}
}
}선택 정렬
// TODO: Sort cities by temperature in descending order
void sort_cities(void)
{
// Add your code here
// ● 내림차순 선택정렬
// ● 실행 시간의 상한 O(n^2) | 실행 시간의 하한 Ω(n^2)
int start = 0; // 비교 시작 지점
int counter = 1; // 조건문이 참이 될 때까지 반복 (counter가 0이면 중단)
avg_temp tmp; // 구조체 복사
while (counter != 0) // 조건문이 참이 될 때까지 반복 (counter가 0이면 중단)
{
counter = 0; // counter 초기화
for (int i = start; i < NUM_CITIES; i++)
{
if ( temps[start].temp < temps[i + 1].temp )
{
tmp = temps[start];
temps[start] = temps[i + 1];
temps[i + 1] = tmp;
counter ++; // 교환이 이루어지면 counter + 1
}
}
start ++; // 반복문이 종료된 후 start지점 + 1
//(temps[0] -> temps[1] -> temps[2] -> temps[3] .. -> temps[9])
}중첩 반복문으로 풀이하는 방법도 있는 듯 하다.
원하는 답이 나오는 데에만 집중하지 말고 더욱 효율적인 코드가 무엇일지 고민하는 습관이 필요하다는 것을 느꼈다.
버블 정렬에서 처음 couter를 넣는 방법으로 접근했었는데 while문이 생각처럼 되지 않아
방법을 이리저리 찾다가 중첩 for문으로 정렬이 되길래 오 됐다! 했는데 그건 정렬만 된거지 시간복잡도를 고려를 안했다는 것을 해외 유튜브 풀이를 보고 알았다.
오히려 couter로 접근하는 법이 더 좋은 방법이었다. 차근차근 고민해도 된다! 좋은 코드 짤 것
