9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.)
https://www.acmicpc.net/problem/9466

Description

  • 싸이클을 이루는 그룹은 제외하고, 이루지 못하는 학생들의 수를 얻어야 함.
  • 시간이 무려 3초지만 O(N)으로 해결해야 함.
  • 따라서 한 번 스캔하면서 싸이클을 이루지 못하는 학생들을 체크하고, 싸이클을 따라가다 해당 학생을 만나면 탐색을 중단해야 함.
  • vector_name.clear()를 이용해 초기화하는 것이 시간소모 적음.

 

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

int T, N;
vector<int> students;

void cal() {
	int answer = 0;
	int group_num = 1;
	vector<bool> visited(N, false);
	vector<int> group(N, 0);
	vector<int> visited_node;	// temporal cycling students

	for (int i = 0; i < N; i++) {

		// if the student already has a group num, skip 
		if (group[i] || visited[i] == true) continue;

		visited_node.clear();
		visited[i] = true;
		visited_node.push_back(i);

		int cur_node = students[i];
		// scan only !visited node && had no group(=0) 
		while (!visited[cur_node] && group[cur_node] == 0) {
			visited[cur_node] = true;
			visited_node.push_back(cur_node);
			cur_node = students[cur_node];
		}

		/*	if origin and destin. same after scan cycle, find where does the cycle starts.
			if it's not the node which starts cycle, put -1 to mark it's not groupable */
		int visited_size = visited_node.size();
		for (int j = 0; j < visited_size; j++) {
			if (visited_node[j] != cur_node) {
				group[visited_node[j]] = -1;
			}
			else {
				for (int k = j; k < visited_size; k++) {
					group[visited_node[j]] = group_num;
				}
				group_num++;
				break;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (group[i] < 0) answer++;
	}

	cout << answer << "\n";

	return;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		students = vector<int>(N, 0);

		for (int j = 0; j < N; j++) {
			cin >> students[j];
			students[j] -= 1;
		}
		cal();
	}

	return 0;
}

'스터디 > 알고리즘' 카테고리의 다른 글

C++ 백준 4673 - 셀프 넘버  (0) 2019.11.17
C++ 백준 4344 - 평균은 넘겠지  (0) 2019.11.17
C++ 백준 8958 - OX퀴즈  (0) 2019.11.17
C++ 백준 1546 - 평균  (0) 2019.11.17
C++ 백준 2577 - 숫자의 개수  (0) 2019.11.17

이렇게 시작된 이슬람의 지배 아래에서 많은 것들이 바뀌게 된다.

 

요즘은 이슬람 하면 무슬림 근본주의자들의 영향으로 타 종교에 대한 관용이란 없는 무자비한 이미지가
생각나기 마련이지만 알 안달루스에서는 아니었다.

 

기독교인들과 유대인들 같은 비무슬림 인구 모두는 '보호받는 사람들'이란 뜻인 딤미Dimmi 라고 불리며
종교의 자유를 지킬 권리가 주어졌다. 다만 비무슬림인들에게는 특별히 세금을 더 거두거나 신분상의 제약을 두는 식으로 완전한 평등을 주지 않음으로써 이슬람으로의 개종을 유도했다.

 

알 안달루스 시대 내내 이슬람으로의 개종은 꾸준히 증가했고, 이베리아 출신이지만 이슬람으로 개종한 사람들은

물라디Muladi 라 불렸다. 하지만 이 시기에도 계속해 비무슬림 인구는 함께 이베리아 반도에서 살아가고 있었고,
이 부분에 있어 이베리아 반도의 문화적, 종교적 다양성이 유지되었다고 생각한다. 

 

지금도 스페인의 옛 도시들에 가보면 시가지에 남아있는 유대인 지구를 볼 수 있고, 

그 도시들 스스로도 가톨릭, 이슬람, 유대교의 흔적이 혼재된 문화적 다양성이 풍부한 도시라고 홍보하는 내용 또한 쉽게 찾아볼 수 있다.

톨레도의 유대인 지구

알 안달루스 시기의 이베리아 반도는 아주 번성해서, 코르도바 아미르국의 수도였던 코르도바Córdoba
전성기 인구가 50만에 달하는, 유럽에서 손꼽히는 거대도시로 명성을 날렸다. 그 당시 세워졌던 거대 이슬람 모스크는 후에 성당으로 개조되어 지금은 메스키타Mezquita 라는 이름으로 아직도 수많은 관광객들이 이를 보기 위해 코르도바에 방문한다. 내부에서는 화려한 이슬람 건축문화와 가톨릭 건축문화를 동시에 느껴볼 수 있다.

메스키타, 아래 이슬람 특유의 아치 문양과 위 카톨릭 양식이 혼재되어 있다.

무슬림 통치자들을 위한 궁전, 성의 건축도 활발히 진행되었다.

지금도 많은 도시에는 알카사르Alcázar 라는 이름의 이슬람 성들이 많이 남아있고 특히 세비야, 코르도바, 말라가, 세고비아 등 도시의 알카사르들이 유명하다.
드라마와 노래로도 많이 알려진 그라나다의 나스르 왕조 궁전, 알함브라Alhambra (정확한 발음은 '알람브라') 궁전 또한 이런 목적을 가지고 지어져 지금까지도 그라나다를 먹여 살리고 있다.

 

뿐만 아니라 오래 이슬람의 통치를 받았던 도시들의 구도심은 아직도 이슬람 도시
특유의 복잡한 골목을 기본으로 한 도시구조가 아직도 남아있는 경우가 많다. 톨레도나 코르도바 등에서 체험해 볼 수 있다.

 

이렇게 오랜 기간 이베리아 반도 전역을 통치하며 뿌리내렸던 이슬람 문화, 특히 건축문화는
아직까지도 스페인의 정체성에서 큰 부분을 차지하며 그 힘을 계속해서 발산하고 있는 것 같다.

 

하지만, 문화적으로 엄청난 발전을 이뤘던 알 안달루스도 시간이 흐름에 따라 후 우마이드 왕조에서 여러 군소 왕국으로 찢기고, 다시 합쳐지고, 재정복 당하고, 또 갈라지며 세력이 약화됨과 동시에 북부의 미정복 지대로 남아있던 아스투리아스에서부터 시작된 국토회복운동, 레콩키스타Reconquista에 의해 위기를 맞이하게 된다.

 

다음에는 레콩키스타에 대해 더 자세히 알아보도록 하겠습니다.

 

다음에 만나요,

 

¡Hastpronto! 

툴루즈가 중심지인 시절의 서고트왕국

그렇게 서로마 제국의 붕괴와 함께 게르만족, 그중에서도 서고트족, 수에비족, 반달족이
이베리아 반도로 밀려들어와 각자 왕국을 세우고 싸움을 벌이는데,
결과적으로 서고트왕국이 승기를 잡고 더 큰 세력을 이루게 된다.

반달족은 아프리카로 건너가게 되는데, 현대 스페인의 남부지방의 명칭인 안달루시아Andalucía
'반달족의 땅'이라는 의미의 반달루스Vandalus 에서 유래했다는 말이 있다.
또한 요즘에도 자주 사용하는 단어 반달리즘Vandalism 은 반달족이
약탈과 파괴를 거듭한 민족이라고 잘못 알려진 데에서 유래했다고 한다.

그런 서고트 왕국은 위로는 우리가 역사책에서 프랑스, 이탈리아, 독일의 모태가 된 국가라고 배우는
프랑크왕국에 두들겨 맞아 아키타니아Aquitania (현 프랑스 남부지역)을 모조리 잃고

아래로는 동로마제국이 '여기 우리 땅이었는데?' 하며 들락날락거리는 고통을 받지만,, 
결국 서고트 왕국은 톨레도Toledo 를 중심으로 이베리아 반도를 통일하게 된다.

이 얼마나 깊은 역사의 톨레도인가,, 

이베리아 반도를 지배했던 서고트 왕국

현 프랑스 땅도 조금 가지고 있는데, 현재 까딸란을 사용하는 지역과 일치하는 건 우연이 아니겠지(?)

 

그렇게 서고트족에 의한 이베리아 반도의 평화가 찾아오는 건가? 생각할 무렵.. 다시 서고트 왕국은 내분에 휩싸였고

600년경 시작된 이슬람의 물결, 수백 년이 지난 지금도 스페인에 흔적이 남아있는 그 물결이

아라비아 반도를 휩쓸고 이슬람 제국이 되어 이베리아 반도로 다가오고 있었다.

우마이야 왕조 시절 이슬람 제국 (노란 영역까지)

이슬람 제국은 북아프리카계 무슬림(무어인, 베르베르족)을 앞세워 711년 지브롤터Gibraltar 에 상륙했고,
순식간에 이베리아 반도 대부분을 집어삼켰다. 그리고는 더 위로 올라가 프랑스까지 집어삼키려고 했으나
이는 프랑크왕국의 샤를Charles Martel
에 의해 저지당한다. 이 때 막지 못했다면..(?)

그때부터 이슬람 제국은 이베리아 반도에 집중하게 된다. 이 시기를 알-안달루스Al-Andalus 라고 한다.
이때부터 이슬람의 통치 아래 꽃 피우게 되는 스페인의 문화는 꽃피우게 되고, 번영을 맞이하게 된다. 

750년, 우마이야 칼리파조 아래의 이베리아 반도

하지만 이 고난의 시기, 살아남은 기독교의 땅이 있었으니, 바로 북부의 아스투리아스 왕국이었다.
다른 이베리아 반도 지역들과 비교해 매우 습하고 추우며, 산으로 가득 찬 지역이다 보니 무슬림들이 그렇게
큰 욕심을 내지도 않았고, 아스투리아스 왕국도 많은 성을 짓고는 방어만을 외치며 결사항전을 이어갔다.

오늘날까지도 스페인 북부에는 많은 중세 성Castillo 들이 남아있다.   


그러던 중 이슬람 세계의 지도자 자리를 두고 다툼이 벌어지게 되고, 패배한 가문의 일족 한 명이 간신히 살아남아 
기존 제국의 영향력이 덜 미치는 이베리아 반도까지 도망쳐 756년, 후後우마이야 왕조를 세운다. 
이는 코르도바 아미르국Emirato de Córdoba 이라고도 불린다.

 

간단하게 설명하면, 이슬람 제국은 선지자 무함마드의 뒤를 이은 칼리파가 다스리고 있었는데, 초기에 이 칼리파는
아들에게 물려주는 것이 아니라 선거를 통해 선출되었다. 그러던 중 무함마드의 진짜 핏줄이 칼리파에 선출되게 된다.
여기서부터 문제가 발생하는데, '다음 칼리파를 선거를 통해서 선출해야 한다' 파와 
'무슨 소리냐, 무함마드의 핏줄이 계속 칼리파가 되어야 한다' 파가 나뉘어 싸우게 된다.
이 두 파벌은 결국 종파까지 나뉘게 되어 현대의 수니파와 시아파가 된다.

※틈새 지식

기존 우마이야 칼리파조 이슬람 제국은 칼리파Caliph 가 다스리는 제국으로 칼리파는 이슬람 세계의 정치·종교를 아우르는 최고의 지도자였다. (정교 일체)

아미르emir 는 장군, 총독, 사령관 정도를 의미하는 아랍어로 추후 봉건 제후 정도의 위치를 차지하게 된다.
아랍 에미리트를 생각해보면 쉽다. 아랍 에미리트는 아미르국Emirate 들의 연합국이다.

 

 

드디어 스페인의 역사에서 큰 부분을 차지하는 알-안달루스 시대까지 왔네요.
다음 글에서는 이슬람의 통치 아래의 스페인 문화와 사회에 대해 다뤄보려고 합니다. 

 

다음에 만나요,

 

¡Hastpronto! 

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
#include <stdio.h>
#include <iostream>
#include "string.h"
using namespace std;
 
int Generate(int OG);
 
int main()
{
    bool Array[10001= { 0 };
 
    for (int i = 1; i < 10001; i++
    {
        int temp = Generate(i);
        if (temp < 10001)
        {
            Array[temp] = 1;
        }
    }
 
    for (int i = 1; i < 10001; i++)
    {
        if(Array[i] == 0printf("%d\n", i);
    }
 
    return 0;
}
 
int Generate(int OG) 
{
    int sum = OG;
 
    while (OG != 0)
    {
        sum += (OG%10);
        OG /= 10;
    }
 
    return sum;
}
 

1부터 순차적으로 수열의 다음 숫자를 생성한 뒤 생성된 숫자를 1~10000까지의 배열에서 True값으로 바꿔버린다.
그리고 난 후 False값을 가지는 숫자들 (셀프 넘버)만 출력한다.

 

bool type의 배열 초기화는 False, 0으로! 기억하자

'스터디 > 알고리즘' 카테고리의 다른 글

BOJ 9466_텀 프로젝트  (0) 2021.03.09
C++ 백준 4344 - 평균은 넘겠지  (0) 2019.11.17
C++ 백준 8958 - OX퀴즈  (0) 2019.11.17
C++ 백준 1546 - 평균  (0) 2019.11.17
C++ 백준 2577 - 숫자의 개수  (0) 2019.11.17

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
#include <stdio.h>
#include <iostream>
#include "string.h"
using namespace std;
 
int main()
{
    int C, N = 0;
    int Scores[1000= { 0 };
 
    scanf("%d"&C);
    for (int i = 0; i < C; i++
    {
        scanf("%d"&N);
        double sum = 0;
 
        for (int k = 0; k < N; k++)
        {
            int score = 0;
            scanf("%d"&score);
            Scores[k] = score;
            sum += score;
        }
 
        sum /= N;
        int count = 0;
 
        for (int k = 0; k < N; k++)
        {        
            if (Scores[k] > sum) count++;
        }
 
        printf("%0.3lf%\n", (double)count / N * 100);
    }
 
    return 0;
}
 
 

포인트는 마지막에 퍼센트를 계산할 때 double로 분자를 형변환 시켜주는 것. 

'스터디 > 알고리즘' 카테고리의 다른 글

BOJ 9466_텀 프로젝트  (0) 2021.03.09
C++ 백준 4673 - 셀프 넘버  (0) 2019.11.17
C++ 백준 8958 - OX퀴즈  (0) 2019.11.17
C++ 백준 1546 - 평균  (0) 2019.11.17
C++ 백준 2577 - 숫자의 개수  (0) 2019.11.17

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
#include <stdio.h>
#include <iostream>
#include "string.h"
using namespace std;
 
int main()
{
    int N = 0;
    char Ans[81= { 0 };
 
    scanf("%d\n"&N);
 
    for(int i = 0 ; i < N; i++) {
        scanf("%s", Ans);
        int count = 0;
        int sum = 0;
 
        for (int j = 0; j < strlen(Ans) + 1; j++) {        // \0 까지 세어줘야 함
            if (Ans[j] == 'O')
            {
                count++;
                sum += count;
            }
            else if (Ans[j] == 'X')
            {
                count = 0;
            }
            else if (Ans[j] == '\0')
            {
                printf("%d\n", sum);
            }
        }
    }
 
    return 0;
}
 


미리 사이즈가 81인 (문자열이므로 \0 감안) Char 배열을 선언해두고 입력받아 그대로 카운트 한 뒤, 출력

'스터디 > 알고리즘' 카테고리의 다른 글

C++ 백준 4673 - 셀프 넘버  (0) 2019.11.17
C++ 백준 4344 - 평균은 넘겠지  (0) 2019.11.17
C++ 백준 1546 - 평균  (0) 2019.11.17
C++ 백준 2577 - 숫자의 개수  (0) 2019.11.17
C++ 백준 10951 - A+B - 4  (0) 2019.11.14
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
#include <stdio.h>
using namespace std;
 
int main()
{
    double Scores[1000= { 0 };
    int N = 0;
    double max = 0;
    double sum = 0;
 
    scanf("%d\n"&N);
 
    for (int i = 0; i < N; i++) {
        int score = 0;
        scanf("%d"&score);
        Scores[i] = score;
    }
 
    for (int i = 0; i < N; i++) {
        if (Scores[i] > max) max = Scores[i];
    }
 
    for (int i = 0; i < N; i++) {
        Scores[i] = Scores[i] / max * 100;
        sum += Scores[i];
    }
 
    printf("%0.2lf\n", sum / N);
 
    return 0;
}
 

다른 건 별 문제가 없었는데, 소수점 아래 2자리까지 반올림해 출력하도록 하는 게 기억이 안나서 찾아봤다.

0.2lf로구나.

'스터디 > 알고리즘' 카테고리의 다른 글

C++ 백준 4344 - 평균은 넘겠지  (0) 2019.11.17
C++ 백준 8958 - OX퀴즈  (0) 2019.11.17
C++ 백준 2577 - 숫자의 개수  (0) 2019.11.17
C++ 백준 10951 - A+B - 4  (0) 2019.11.14
C++ 백준 2884 - 알람시계  (0) 2019.09.09

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
int main()
{
    int A, B, C, Result =0;
    int count[10= {0};
    
    scanf("%d\n%d\n%d\n"&A, &B, &C);
    Result = A*B*C;
    
    while(Result > 0){
        int num = Result % 10;
        Result /= 10;
        count[num]++;
    }
    
    for(int i = 0; i < 10; i++){
        printf("%d\n", count[i]);
    }
    
    return 0;
}
 

 

 

포인트는 각 숫자들을 곱한 값이 몇 자리 수일지 모르기에

 

몇 자리이던 상관없이 계산 가능하도록 %를 이용해 각 자리를 구하며 즉시 배열에 값으로 때려넣는 것,,!

'스터디 > 알고리즘' 카테고리의 다른 글

C++ 백준 8958 - OX퀴즈  (0) 2019.11.17
C++ 백준 1546 - 평균  (0) 2019.11.17
C++ 백준 10951 - A+B - 4  (0) 2019.11.14
C++ 백준 2884 - 알람시계  (0) 2019.09.09
C++ 백준 2753 - 윤년  (0) 2019.09.09

+ Recent posts