Study_farobi

[소스코드/C++] DRAWRECT

Makeii 2016. 3. 6. 02:06

2016. 3. 6. 02:06

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*점이 3개 주어지면 사각형을 이루는 나머지 한 점을 찾을 수 있다.*/
#include <iostream>
#include <string>    //string을 사용하기 위해 필요한 헤더
#include <cmath>    //제곱근 계산을 하기위해 필요한 헤더
using namespace std;
 
void setPoint(int *x, int *y);    //입력받은 내용을 좌표로 변환
 
int main(){
    int count;    //테스트케이스의 횟수
    double long_distance;    //두 점 사이의 거리 중에서 가장 긴거리
    int *x = new int[3];    //입력된 좌표를 가지고 있는 배열
    int *y = new int[3];
    int temp_x = 0;
    int temp_y = 0;
    int *result_x;    //좌표를 토대로 계산되어 나오는 결과(x좌표)
    int *result_y;    //좌표를 토대로 계산되어 나오는 결과(y좌표)
 
    //테스트케이스의 횟수를 입력받는다.
    cin>>count;
    result_x = new int[count];
    result_y = new int[count];
    cin.ignore();
    //테스트케이스만큼 반복
    for(int i=0;i<count;i++){
        setPoint(x, y);
        //같은 좌표가 있는지 확인 - 혼자만 다른 좌표 찾아내기
        for(int j=1;j<3;j++){
            if(x[0]==x[j]) temp_x = j;
            if(y[0]==y[j]) temp_y = j;
        }
        
        if(temp_x==0){    //맨 처음이 다른 좌표이면
            result_x[i] = x[0];
        }
        else{
            result_x[i] = x[3-temp_x];
        }
        if(temp_y==0){
            result_y[i] = y[0];
        }
        else{
            result_y[i] = y[3-temp_y];
        }
        //사용한 변수 초기화
        temp_x = 0;
        temp_y = 0;
    }
 
    for(int i=0;i<count;i++){
        cout<<result_x[i]<<" "<<result_y[i]<<endl;
    }
    
    //메모리 해제
    delete []x;
    delete []y;
    delete []result_x;
    delete []result_y;
 
    return 0;
}
 
void setPoint(int *x, int *y){
    //cout<<"setPoint start!"<<endl;
    char *insert;    //좌표를 입력받을 변수
    string point;
    int int_pointX;    //X좌표를 int로 변환한 값을 저장할 변수
    int int_pointY;    //Y좌표를 int로 변환한 값을 저장할 변수
 
    insert = new char[20];
 
    //임의의 point를 3개 입력받음
    for(int i=0;i<3;i++){
        //cout<<"for start!"<<endl;
        fgets(insert, 20, stdin); //공백을 포함하여 입력받음
        point = insert;
        point.pop_back();
 
        int_pointX = (int)atof(point.substr(0, point.find(" ")).c_str());    //문자열인 X좌표를 int형으로 변환
        int_pointY = (int)atof(point.substr(point.find(" ")).c_str());    //문자열인 Y좌표를 int형으로 변환
 
        if((int_pointX>0&&int_pointX<1001)&&(int_pointY>0&&int_pointY<1001)){    //좌표가 (1, 1)~(1000, 1000) 사이에 있을 때
            x[i] = int_pointX;
            y[i] = int_pointY;
        }    
    }
    delete []insert;
}
Colored by Color Scripter
cs

지금 머리가 안돌아가서 너무 막 짠것 같음

내일 다시 보고 더 좋은 방법 없나 찾아봐야겠음

내가 찾은 방법은 3개의 좌표중 혼자 다른 좌표를 찾아 넣어주는 방법이었음

직사각형이 뷰포트에 평행하다면 좌표들도 뷰포트에 평행하니까

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*점이 3개 주어지면 사각형을 이루는 나머지 한 점을 찾을 수 있다.*/
#include <iostream>
#include <string>    //string을 사용하기 위해 필요한 헤더
#include <cmath>    //제곱근 계산을 하기위해 필요한 헤더
using namespace std;
 
void setPoint(int *x, int *y);    //입력받은 내용을 좌표로 변환
int findX(int *x);    //x를 찾음
int findY(int *y);    //y를 찾음
 
int main(){
    int count;    //테스트케이스의 횟수
    int *x = new int[3];    //입력된 좌표를 가지고 있는 배열
    int *y = new int[3];
    int *result_x;    //좌표를 토대로 계산되어 나오는 결과(x좌표)
    int *result_y;    //좌표를 토대로 계산되어 나오는 결과(y좌표)
 
    //테스트케이스의 횟수를 입력받는다.
    cin>>count;
    result_x = new int[count];
    result_y = new int[count];
    cin.ignore();
    //테스트케이스만큼 반복
    for(int i=0;i<count;i++){
        setPoint(x, y);
        //같은 좌표가 있는지 확인 - 혼자만 다른 좌표 찾아내기
        result_x[i] = findX(x);
        result_y[i] = findY(y);
    }
 
    for(int i=0;i<count;i++){
        cout<<result_x[i]<<" "<<result_y[i]<<endl;
    }
    
    //메모리 해제
    delete []x;
    delete []y;
    delete []result_x;
    delete []result_y;
 
    return 0;
}
 
void setPoint(int *x, int *y){
    //cout<<"setPoint start!"<<endl;
    char *insert;    //좌표를 입력받을 변수
    string point;
    int int_pointX;    //X좌표를 int로 변환한 값을 저장할 변수
    int int_pointY;    //Y좌표를 int로 변환한 값을 저장할 변수
 
    insert = new char[20];
 
    //임의의 point를 3개 입력받음
    for(int i=0;i<3;i++){
        //cout<<"for start!"<<endl;
        fgets(insert, 20, stdin); //공백을 포함하여 입력받음
        point = insert;
        point.pop_back();
 
        int_pointX = (int)atof(point.substr(0, point.find(" ")).c_str());    //문자열인 X좌표를 int형으로 변환
        int_pointY = (int)atof(point.substr(point.find(" ")).c_str());    //문자열인 Y좌표를 int형으로 변환
 
        if((int_pointX>0&&int_pointX<1001)&&(int_pointY>0&&int_pointY<1001)){    //좌표가 (1, 1)~(1000, 1000) 사이에 있을 때
            x[i] = int_pointX;
            y[i] = int_pointY;
        }    
    }
    delete []insert;
}
int findX(int *x){
    int same = 0;
 
    for(int i=1;i<3;i++){    //같은 원소가 있는 위치 찾기
        if(x[0]!=x[i]){
            same++;
        }
        else break;
    }
 
    return x[2-same];
}
int findY(int *y){
    int same = 0;
 
    for(int i=1;i<3;i++){    //같은 원소가 있는 위치 찾기
        if(y[0]!=y[i]){
            same++;
        }
        else break;
    }
    
    return y[2-same];
}
Colored by Color Scripter
cs

문제 제대로 안읽고 풀다가 점구하는 거에서 엄청 힘들었다.

문제를 제대로 읽어야 한다는 교훈을 다시 한번..

임의의 한 점을 구하는 것은 각 x의 배열과 y에 배열에서 겹치지 않는(중복X) 원소를 찾는 방법으로 하였다.

좌표 A B C가 존재한다고 할 때

1. A - B가 중복 : C가 다른 원소

2. A - C가 중복 : B가 다른 원소

3. A - B / A - C 모두 겹치지 않음 : A가 다른 원소

이 세가지 조건 중 하나를 만족하므로 겹치는 횟수(위치)를 찾아 제외시켰다.

처음에는 switch문으로 작성했는데 보니까 각 case와 결과에 대입하는 원소 사이에 규칙이 있길래 없애버리고 바로 return문으로 넣어버렸다.

한 5일 고생한 듯 하다...바보처럼..

저작자표시 변경금지 (새창열림)

'알고스팟 > 튜토리얼' 카테고리의 다른 글

[소스코드/C++] XHAENEUNG (0)	2016.03.06
[소스코드/C++] URI (0)	2016.03.03
[소스코드/C++] HOTSUMMER (0)	2016.03.01
[소스코드/C++] CONVERT (0)	2016.03.01
[소스코드/C++] MISPELL (0)	2016.02.29

[소스코드/C++] XHAENEUNG

Makeii 2016. 3. 6. 00:00

2016. 3. 6. 00:00

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/*입력받은 수식이 맞게 풀어진 것인지 확인하는 프로그램을 작성하라.
대신 답은 순서에 상관없이 개수만 맞으면 정답으로 간주한다.
ex) five -> vife 라도 정답처리*/
#include <iostream>
#include <string>
using namespace std;
 
#define MAX_SIZE 40
 
int convertNum(string str);    //입력받은 영단어를 숫자로 변환
string convertStr(int ans);    //숫자를 영어로 변환
string check(string answer, string write);    //입력받은 값과 계산한 값이 동일한지 체크
 
int main(){
    int count;    //테스트케이스
    char *insert = new char[MAX_SIZE];    //입력받을 라인
    string line;    //연산을 수행할 문자열
    int A, B;    //영어로 입력받은 수를 숫자로 변환하여 저장할 변수
    char operate;    //산술 기호 저장할 변수
    string C;    //입력한 답
    string answer;    //연산한 결과값의 문자열
    int ans;    //연산한 결과값
    string *result;
 
    //테스트 케이스 수 입력
    cin>>count;
    result = new string[count];
    cin.ignore();
    //테스트 케이스 수만큼
    for(int i=0;i<count;i++){
        //산술식 입력받음
        fgets(insert, MAX_SIZE, stdin);
        line = insert;
        line.pop_back();    //개행문자 삭제
 
        //입력받은 문자열 쪼개기
        //A
        A = convertNum(line.substr(0, line.find(" ")));
        line.erase(0, line.find(" ")+1);
        //Operate
        operate = line.at(0);
        line.erase(0, 2);
        //B
        B = convertNum(line.substr(0, line.find(" ")));
        line.erase(0, line.find(" ")+3);
        //C
        C = line.substr(0);
 
        //cout<<A<<" "<<operate<<" "<<B<<" "<<C<<endl;
        //cout<<"분리까지 OK"<<endl;
 
        //연산
        switch(operate){
        case 43:    //+
            ans = A+B;
            answer = convertStr(ans);
            break;
        case 45:    //-
            ans = A-B;
            answer = convertStr(ans);
            break;
        case 42:    //*
            ans = A*B;
            answer = convertStr(ans);
            break;
        }
        //cout<<"연산까지 OK"<<endl;
        if(ans<0||ans>10){    //결과값이 0=<C<=10이 아니라면
            result[i] = "No";
        }
        else{    //입력받은 문자열 C의 길이와 답의 길이가 같을 때만(같지 않으면 답이 아니므로 비교해볼 필요가 없음)
            if(C.length()==answer.length()) result[i] = check(answer, C);
            else result[i] = "No";
        }
    }
 
    for(int i=0;i<count;i++){
        cout<<result[i]<<endl;
    }
 
    //할당 해제
    delete []result;
    delete []insert;
    return 0;
}
 
int convertNum(string str){    //입력받은 영단어를 숫자로 변환
    //2글자만 비교하여 숫자를 판별함
    char num = str.at(0);
    char num_same = str.at(1);
 
    switch(num){
    case 122:
        return 0;
    case 111:
        return 1;
    case 116:
        if(num_same==119) return 2;
        else if(num_same==104) return 3;
        else return 10;
    case 102:
        if(num_same==111) return 4;
        else return 5;
    case 115:
        if(num_same==105) return 6;
        else return 7;
    case 101:
        return 8;
    case 110:
        return 9;
    }
}
string convertStr(int ans){    //숫자를 영어로 변환
    switch(ans){
    case 0:
        return "zero";
    case 1:
        return "one";
    case 2:
        return "two";
    case 3:
        return "three";
    case 4:
        return "four";
    case 5:
        return "five";
    case 6:
        return "six";
    case 7:
        return "seven";
    case 8:
        return "eight";
    case 9:
        return "nine";
    case 10:
        return "ten";
    default :
        return "";
    }
}
string check(string answer, string write){    //입력받은 값과 계산한 값이 동일한지 체크
    int arr_write[26] = {0,};    //모든 값 0으로 초기화
    int arr_ans[26] = {0,};
    int index = 0;
    bool check = true;
 
    for(int i=0;i<write.length();i++){    //각 위치에 글자수 할당
        arr_write[write.at(i)-97]++;
        arr_ans[answer.at(i)-97]++;
    }
    while(index<26){    //배열이 끝날 때까지 비교
        if(arr_write[index]!=arr_ans[index]){    //같지 않은 부분이 있다면
            check = false;
            break;
        }
        index++;
    }
 
    //모두 겹치면 YES, 아니면 NO
    if(check) return "Yes";
    else return "No";
}
Colored by Color Scripter
cs

출력값을 올바르게 출력하지 않아 틀린 바보같은 짓을 했다..

문제를 꼼꼼히 읽고 풀자 제발 ㅠㅠㅠㅠ

처음에 답과 입력한 문자열 비교하는 것을 아스키코드의 합으로 생각했었는데 겹칠 가능성이 너무 농후해서 접었음

알파벳 갯수만큼의 배열을 생성해서 하나하나 체크하는 것이 더 나았다고 생각함

배열 초기화 방법이 for밖에 생각이 안났었는데 {0, }방식이 있다는 것을 까먹어서 삽질할 뻔했음

숫자를 영어로 변환하는 함수도 default를 넣지 않아 에러가 났었음

계산시 <0, >10 을 고려하지 않아서 생긴 실수

너무 어렵게 생각하지 말고 차근차근 생각할 것

저작자표시 변경금지 (새창열림)

'알고스팟 > 튜토리얼' 카테고리의 다른 글

[소스코드/C++] DRAWRECT (0)	2016.03.06
[소스코드/C++] URI (0)	2016.03.03
[소스코드/C++] HOTSUMMER (0)	2016.03.01
[소스코드/C++] CONVERT (0)	2016.03.01
[소스코드/C++] MISPELL (0)	2016.02.29

[C++자료구조론] 1. 성능분석과 측정

Makeii 2016. 3. 3. 01:26

2016. 3. 3. 01:26

공간 복잡도(space complexity) : 프로그램을 실행시켜 완료하는데 필요한 메모리의 양(RAM관련)

고정 부분

프로그램의 입출력 특성과 관계 X - 횟수, 크기 등에 상관 X
보통 명령어 공간, 단순 변수, 일정 크기의 요소 변수, 상수들을 위한 공간을 포함

가변 부분

풀려고 하는 문제의 인스턴스에 의해 크기가 결정되는 변수가 필요로 하는 공간과, 참조된 변수가 필요로 하는 공간, 순환 스택 공간으로 구성

공간복잡도 S = C(상수) + Sp(인스턴스 특성)
Sp는 함수가 얼마나 콜되는가에 따라 달라지는 것 같음
변수가 여러개 있다고 해서 Sp가 올라가는 것은 아님
순환의 깊이에 따라 Sp가 올라갈 수도 내려갈 수도 있음

시간 복잡도(time complexity) : 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간(CPU관련)

프로그램에 소요되는 시간은 컴파일 시간 + 실행 시간 - SUM(명령어들의 수행시간 * 명령어들이 몇번이나 실행됐는지 센 결과)
컴파일 시간은 인스턴스 특성과는 무관하며 컴파일된 프로그램을 재컴파일 하지 않고 여러번 수행된다는 가정 하에 무시 가능 - 프로그램 실행 시간만 고려해도 OK
각 단계수(실행 횟수)를 고려하여 시간 복잡도를 계산

주석 : 단계수 0
선언문 : 변수/상수 정의문, class, struct, union, template, 접근자, 함수 타입 결정문 등은 단계수 0

비실행문이거나, 관련 함수가 기동되는 비용에 포함되므로

산술식 및 지정문

산술식 : +, -, *, / 등은 단계수 1, 다만 함수 호출을 포함하는 산술식은 예외
지정문 : = 등은 단계수 1, 다만 인스턴스 특성의 함수를 대입하는 경우 인스턴스 특성과 같은 단계수를 가짐

반복문 : 제어 부분만 단계수 고려, 반복문이 실행되는 횟수
스위치 명령문 : 수행되는 식의 단계수와 동일, 각 조건의 비용은 자신의 비용 + 앞서 나온 모든 조건의 비용
if-else문 : 각 수행문에 따라 단계수 할당
함수 호출

매개변수가 인스턴스 특성에 의존하는 값이 아니라면 단계수 1, 의존하는 값이라면 값 인자의 크기가 단계수, 순환적이라면 지역변수도 고려

메모리 관리 명령문 : new, delete, sizeof 등 단계수 1

new와 delete의 경우 생성자와 소멸자를 묵시적으로 호출할 수 있는데 이때는 함수 호출과 같은 방법으로 계산됨

함수 명령문 : 단계수 0
분기 명령문 : continue, break, goto, return 등 단계수 1, return 반환값; 일 경우 반환값이 인스턴스 특성의 함수라면 단계수는 반환값과 같음

밑의 예제를 통해 시간 복잡도를 조금 쉽게 이해하며 계산해보기

각 라인당 몇번 실행되는지 구한 후 다 더하면 OK

내가 변화시키고 싶은 특성들을 정해두고 그 특성에 맞춰 시간 복잡도를 계산하는 것이 좋음

균형 분기점(break even point) : 시간 복잡도가 큰 A와 작은 B가 있을 때 A가 B보다 빠를 수 있는 조건이 되는 n이 존재함. 그 때의 n이 균형 분기점
점근 표기법

Ο(빅오) : 알고리즘 실행 시간의 상한을 나타냄 - 최악의 경우
Ω(오메가) : 알고리즘 실행 시간의 하한을 나타냄 - 최고의 경우
Θ(세타) : 알고리즘 실행 시간의 평균을 나타냄 - 평균의 경우

저작자표시 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

연결 리스트(이중연결, 단방향, 순환)의 헤드 포인터와 헤더 노드 (0)	2016.09.19
정렬 알고리즘에 대한 용어? (0)	2016.06.11

PREV 이전 1 ···14 15 16 17 18 19 20 ···24 NEXT 다음

함수 값
log n	n	n*log n	n^2	n^3	2^n
0	1	0	1	1	2
1	2	2	4	8	4
2	4	8	16	64	16
3	8	24	64	512	256
4	16	64	256	4096	65536
5	32	160	1024	32768	4294967296

Study_farobi

[소스코드/C++] DRAWRECT

'알고스팟 > 튜토리얼' 카테고리의 다른 글

[소스코드/C++] XHAENEUNG

'알고스팟 > 튜토리얼' 카테고리의 다른 글

[C++자료구조론] 1. 성능분석과 측정

'자료구조' 카테고리의 다른 글

+ Recent posts

티스토리툴바