1. 문제https://www.acmicpc.net/problem/30237코드포스 Round899 B번 문제입니다.2. 풀이차집합 계산하기U = S1 ∪ S2 ∪ S3 ∪ ... ∪ Sn 이라고 해봅시다. 먼저 우리가 구하는 S는 완전탐색으로 생각해볼 수 있습니다. S₁부터 Sn까지 모든 부분집합을 Subset이라고 하면, 모든 Subset에 대해서 U - Subset을 비교하는 방법입니다. 즉,  전체합집합과의 차집합을 비교하는 것으로 생각할 수 있습니다. 하지만 Subset을 모두 탐색하면 O(2ⁿ)이므로 시간초과가 발생합니다.따라서 전체집합에서 원소를 하나씩 빼보는 방식을 생각했습니다. x ∈ U인 임의의 x에 대해 U - x를계산하면  x를 가지고 있는 모든 Si도 빠져야 합니다. 예를 들어 t..

1. 문제https://www.acmicpc.net/problem/1562 1562번: 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net 2. 풀이DP적 접근비슷한 문제로 [백준 18044] 쉬운 쉬운 계단수가 있습니다. 이 문제를 먼저 이해해야 합니다. 이 문제는 기본적으로 [18044 쉬운 계단수]와 동일하게 최적 부분구조와 반복되는 부분문제를 가집니다. 하지만 쉬운 계단 수와는 다르게 "0부터 9까지 숫자가 모두 포함되어야 한다"는 조건이 추가되었습니다. 기존의 두 가지 정보를 이용한 DP 테이블로는 원하는 답을 얻을 수 없습니다. 따라서 부분문제를 해결할 때 "현재 구성된 계단수의 숫자의 조합"이라는 정보도 추가되어야..

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 DP적 접근 문제를 읽고 세번째까지는 구조도를 그려봤습니다. 구조를 보면 결국 완전탐색을 통해 모든 경우의 수를 찾는 문제입니다. 그런데 다음 자리로 늘어나는 과정에서 완전탐색의 시간복잡도는 O(2ⁿ)이 됩니다. 따라서 DP나 그리디를 써야 하는데 아까 그린 구조도를 살펴보면 두 가지 특징을 가집니다. 반복되는 부분문제(Overlapping Subproblems) 다음 자리로 늘어나는 과정에서 같은 부분문제들이 반복됩니다. 최적 부분구조(Optimal Substructur) 위의 부분문제들..

1. 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 2. 풀이 접근 방법 문제의 조건 중 "어떤 파티에서는 진실을 듣고 또다른 파티에서는 과장된 이야기를 들었을 때에도 거짓말 쟁이로 간주된다" 라는 표현이 핵심 포인트입니다. 저는 이 문제를 해결하는 과정에서 유니온 파인드를 떠올렸습니다. 처음에는 단순히 모든 파티들을 탐색하며 진실/거짓 여부를 확인하고 개수를 세어 주려고 했습니다. 하지만 테스트 케이스를 검증하다가 보니 예외가 존재합니다. 현재 ..

자료구조와 알고리즘은 컴퓨터 과학에서 기초로 다룰 만큼 근간이 되는 학문입니다. 이번 포스팅에서는 자료구조와 알고리즘에 대해 알아보고 둘의 관계를 다루어 보겠습니다. 이번 글에서는 전반적으로 흐름에서 자료구조와 알고리즘의 관계에 대해 다룰 예정입니다. 구현 방법, 예시 등은 다른 글에서 다루었으니 필요하시면 찾아보세요! 1. 자료구조 자료구조란? 효율적으로 데이터를 접근/수정하기 위해 데이터를 조직화하는 방법입니다. 그렇다면 자료구조는 왜 중요할까요? 어떤 자료구조를 사용하느냐에 따라 데이터의 처리 속도나 메모리 사용량이 크게 달라집니다. 따라서 자료구조는 프로그램의 실행 속도를 결정짓는 매우 중요한 개념입니다. 자료 구조의 특징 상황에 맞는 자료구조를 선택하려면 다음 세 가지 특징을 만족해야 합니다. ..

1. 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 2. 접근 방법 그리디를 떠올릴 수만 있다면 아주 쉬운 문제입니다. 하지만 그리디를 떠올리기 쉽지 않으므로 항상 일관된 알고리즘적 사고가 필요한 것 같습니다. 따라서 평소처럼 일관된 방법으로 접근했습니다. 아이디어 완전 탐색으로 생각해볼 때 나올 수 있는 모든 가지수는 1000!입니다. 팩토리얼의 허용 범위는 11이므로 불가능합니다. 완전 탐색이 불가능하여 DP로 접근해보았습니다. 이 문제의 조건을 보니 조합이 아니..

이번 포스팅에서는 유니온 파인드 알고리즘에 대해서 알아보겠습니다. 유니온 파인드를 알기 위해 간단한 트리의 개념을 알아야 합니다. 트리가 처음이라면 먼저 간단하게라도 트리의 개념과 트리 순회를 알아보고 오는 것을 추천드립니다.유니온 파인드 알고리즘은 기본 구현보다 최적화 방법과 문제 적용이 더 중요합니다. 최적화 원리까지 이해하고 문제 적용하는 것을 강력 권장합니다. 1. 유니온 파인드란?다음과 같이 여러 노드간의 연결 관계가 주어졌다고 해봅시다.임의의 두 노드가 주어졌을 때 유니온 파인드 알고리즘을 이용하면 두 노드가 같은 집합에 속하는지 확인할 수 있습니다. 예를 들어 1과 2는 같은 집합, 3과 5도 같은 집합, 4와 6은 다른집합입니다. 유니온 파인드를 이용하면 이러한 연산을 O(1)에 바로 알 ..

두 가지 방법으로 접근할 수 있다. 1. LIS를 두번한 다음 비교하기 2. 반복문을 돌며 기준점을 잡고 증가하는 부분 수열과 감소하는 부분 수열을 구한 뒤 최댓값 구하기