0과 1의 쉼터

풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(people)이 또 다른 파티에 참석하게 될 경우 지민이는 마찬가지로 진실만을 말해야 한다. Disjoint Set 구현 풀이 즉, 한 명이라도 진실을 아는 사람이 있는 파티(know_truth)에 참석한 사람들(people)의 Disjoint Set 관계 간 동일 그룹 및 동일 root node를 가지게 되는 것이다. 파티에 참석한 모든 인원을 공통 조상으로 묶어주자. M개의 파티는 진행되는 파티마다 새로 진실을 알게 되는 사람들이(people) 늘어날 수 있으니, 파티를 모두 마친 후 지민이가..

풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net..

풀이 의상의 종류별로 개수를 세고, 의상을 입어볼 수 있는 모든 경우에서, 모든 의상을 다 입은 경우만 빼면 된다. 소스코드 #include #include #include using namespace std; int main(){ int T, n; cin >> T; while (T--){ cin >> n; map info; map::iterator iter; string name, kinds; while (n--){ cin >> name >> kinds; if (info[kinds]) info[kinds]++; else info[kinds] = 1; } int result = 1; for (iter = info.begin(); iter != info.end(); iter++) result *= (ite..

풀이 구조체 배열의 index와 문자열을 이용해 숫자를 입력받을 떄는 별도의 탐색없이 출력이 가능하지만, 문자열 검색시에는 탐색을 필요로 하고, 이 과정에서 시간 초과가 발생해 map을 사용해 풀이했다. 소스코드 #include #include #include #include using namespace std; map name; map num; int main(){ int N, M; scanf("%d %d", &N, &M); char temp[21]; for (int i = 0; i < N; i++){ scanf("%s", temp); name[temp] = i; num[i] = temp; } for (int i = 0; i < M; i++){ scanf("%s", temp); if (temp[0]

풀이 0을 입력받으면 pop, 아니면 push이다. 연산 효율을 위해 일단 입력받고 0이면 top를 -2만큼 감소시켰다. 소스코드 #include int main(){ int K; scanf("%d", &K); int stack[K], top = -1, sum = 0; for (int i = 0; i < K; i++){ scanf("%d", &stack[++top]); if (!stack[top]) top -= 2; } for (int i = 0; i

풀이 '(', '[' 일때는 stack에 삽입해주고, ')', ']' 일때, top이 -1이 아니고, stack[top]에 '(', '['가 있을때, top를 감소한다. 만약 그렇지 않다면, "] ["나 ") (" 처럼 짝이 안맞는 경우이므로 출력을 위해 top값을 -2로 갱신하고 반복문을 빠져나온다. 소스코드 #include #define MAX 101 int main(){ char str[MAX], stack[MAX]; while (1){ gets(str); if (str[0] == '.') break; int top = -1; for (int i = 0; str[i] != '.'; i++){ if (str[i] == '(' || str[i] == '[') stack[++top] = str[i]; e..

풀이 우선 Test Case를 입력받아 Queue에 저장하고, 최댓값을 찾았을 때의 index가 입력받은 M과 일치하기 전까지 최댓값을 제거하고, cnt를 증가시켜주는 방식으로 풀이했다. 소스코드 #include int main(){ int T, N, M; scanf("%d", &T); while (T--){ scanf("%d %d", &N, &M); int queue[N], idx = 0, cnt = 1; for (int i = 0; i < N; i++) scanf("%d", &queue[i]); while (1){ int max = 0; for (int j = 0; j < N; j++) max < queue[j] && (max = queue[j]); while (queue[idx] != max) id..

풀이 다음과 같은 규칙이 존재한다. 둘째 줄부터 입력받은 수까지 push를 해주어야 하며, push는 이전에 입력된 수보다 큰 수가 입력될 때만 발생한다. push가 발생하거나, 이전에 입력된 수보다 작은 수가 입력될 경우 불필요해 생략한 후 pop가 발생해야한다. 만약, pop이 발생하지 않았다면, 스택을 이용해 수열을 만들 수 없다는 의미이다. 따라서, 둘째 줄부터 입력받는 n개의 수들을 저장할 필요가 없다. 소스코드 #include int main(){ int n; scanf("%d", &n); int stack[n], top = 0, val, idx = 0, num = 0; char op[2*n]; for (int i = 0; i < n; i++){ scanf("%d", &val); for (in..

풀이 C로 풀기에는 난이도에 비해 번거로움이 많아 C++로 풀이했다. 기본적인 pop, push, empty, front를 사용하는 문제이기 때문에 C++에 이미 구현된 queue 라이브러리를 사용하면 된다. 순서(cnt)가 K로 나누었을 때 나머지가 존재하면, queue의 앞에있는 수를 제거하고, 뒤에 추가해준다. 아니라면, queue의 앞에있는 수를 출력해주고, pop하여, 마지막 요소인지 아닌지에 따라 출력 형식을 달리해준다. 소스코드 #include #include using namespace std; int main(){ int N, K, cnt = 1; cin >> N >> K; queue Q; for (int i = 1; i

풀이 본래 Queue를 이용해 푸는 문제지만, 다음과 같은 규칙성이 존재해 간단하게 풀이했다. N이 1일때, 결과가 1이다. N >= 2 일때, N에서 N보다 작은 2의 제곱을 뺀 값에 2를 곱해준 값이 결과와 일치한다. 65~128까지의 N은 N보다 작은 2의 배수인 64를 뺀 값에 2배를 곱하여 출력할 것이다. 129 ~ 256의 N또한 마찬가지로 N보다 작은 2의 배수인 128를 뺀 값에 2배를 곱하여 출력할 것이다. 소스코드 #include int main(){ int N, sq = 1; scanf("%d", &N); for (; sq