본문 바로가기

PS 문제 풀이/SWEA75

[SWEA] 10763 조 신나 출처: SWEA Approach 문제 설명은 풀이에 비해 복잡한데, 🤦‍♂️ i 번째 인덱스의 배열 값을 입력받을 때, 입력값이 i와 동일하지 않으면 ans 변수가 올라간다. 소수점 6번째 자리까지 출력하기 위해 float 타입으로 캐스팅하였다. #include int N, val, ans, TC; int main(void) { // freopen("input.txt", "r", stdin); scanf("%d", &TC); for (int tc = 1; tc 2021. 5. 23.

[SWEA] 1849 영준이의 무게측정 출처: SWEA Approach Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com #include const int MAX_N = 1e6 + 2; char cmd; int N, M, TC, a, b, w; int parent[MAX_N], rank[MAX_N], W[MAX_N]; int Find(int n) { if (parent[n] == n) return n; W[n] += W[parent[.. 2021. 5. 23.

[SWEA] 1843 영준이의 숫자 고르기 출처: SWEA Approach bit 연산을 이용해서 자료를 재배치하는 문제이다. - 배열 index N은 가장 큰수(마지막수)가 N인 경우의 수이다. - 전체가 다 들어오고 나서 셈하는 것이 아닌 들어 올때마다 갱신된다. ▶ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com #include #define LL long long const int MOD = 1000000007; const int MAX_N = 1e5; int N, S, TC, srr[MAX_N + 1]; .. 2021. 5. 23.

[SWEA] 4534 트리 흑백 색칠 출처: SWEA Approach 메모제이션을 이용해서 풀 수 있는 문제이다. DP[Color][Node] = Node에서 Color를 가질 때, 가질 수 있는 최대 색칠 방법 수 - DP[흰색][node] = DP[검은색][next] + DP[흰색][next] - DP[검은색][node] = DP[흰색][next] 변수 계산에서 int 범위를 벗어나기 때문에 long long 타입이 필요하고 MOD로 나머지 연산(%) 처리해야 한다. ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각.. 2021. 5. 22.

[SWEA] 9236 곰돌이 출처: SWEA Approach ① Input Data를 입력 받아 base[][]에 저장한다. 벌(bee)과 곰돌이(bear) 이동을 확인하기 위해 BFS를 여러번 해야 하는데 이를 위해 base[][]를 원본으로 활용 - 곰돌이 위치(M), 집 위치(D), 벌의 초기 위치(H)를 표시한다. ② 벌들을 확산시킨다. 확산되는 원리는 BFS 방식을 이용한다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 z.. 2021. 5. 22.

[SWEA] 4747 사막에서 만난 지니 출처: SWEA Approach 문제를 맞추려면 조건 中에서 3 ≤ N ≤ 2000 와 1 ≤ V ≤ 10000 조건을 만족해야 한다. 개수 상관없이 3명의 아이들에게 동일한 값어치를 분배할 때, 각자 받은 물건의 값어치는 배낭에 있었던 물건들의 {총 값어치 ÷ 3} 이다. ex) {1, 2, 3, 4, 5} → 1 + 2 + 3 + 4 + 5 → 15 ÷ 3 = 5 (=아이들이 받은 물건의 값어치) 즉, 평균(avg)에 해당하는 것을 알 수 있다. 다음 고려해야 할 부분은 어떻게 분배해야 할 것인지이다. Input Data에서 한 사람당 받은 물건의 총 값어치를 알 수 있기에 1번에게 물건 배정 → 2번에게 물건 배정까지 한다면 남은 한 사람 3번은 나머지 물건을 가지며 될 것이다. 문제에서 "항상 물.. 2021. 5. 22.

[SWEA] 7794 동환이의 알뜰살뜰 출처: SWEA Approach 문제에서도 명시되어 있지만 할인금액은 아래와 같이 계산할 수 있다. 1% → 0.99 2% → 0.98 3% → 0.97 ex) 100만원, 3% 할인 적용 → 100 × 0.97 = 97만원 36만원, 2% + 3% 할인 쿠폰 적용 → 36 × 0.98 × 0.97 = 34.2216만원 구조체 배열 coupon[]에 할인 정보 저장 ex) 상품가격 = 100, 쿠폰 가격 = 1, 할인율 = 2 → {쿠폰 가격, 쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {1, 0.97, 2} ex) 상품가격 = 100, 쿠폰 가격 = 2, 할인율 = 2 → {쿠폰 가격, 쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {2, 0.97, 1} ▶ 동일한 할인.. 2021. 5. 21.

[SWEA] 8569 개미 관찰 출처: SWEA Approach Parametric Search 를 적용하는 문제이다. [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다. Binary Search (이분 탐색) Binary Search (이분 탐.. zoosso.tistory.com Lower Bound를 이용하는데 해당 개념에 대해 모른다면 아래 내용도 함께 참고 ▶ Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O.. 2021. 5. 20.

[SWEA] 8744 도로 제거 출처: SWEA Approach N개의 도시를 서로 한번씩 연결하면 (N × (N-1)) ÷ 2 의 간선이 생긴다. ex) N = 4 → (4 × 3) ÷ 2 = 6 "어떤 k개의 도로 폐쇄해도 서로 다른 두 도시간에 이동할 수 있음이 유지되도록 하고 싶다" 위 문제 조건을 이해한다면 어렵지 않게 구현할 수 있는 문제이다. 위 모습은 2(= M) 개의 간선을 제거한 상태이다. (각 도시에 남아있는 도로 개수는 {빨간 숫자}로 표시) "이동될 수 있음"을 보장하면서 도로를 추가로 제거한다면 도로 {② ↔ ④} 1(=k)개를 제거하거나 도로 {① ↔ ④}를 1(=k)개를 제거할 수 있다. 하지만 어떤 k개의 도로를 폐쇄해도 서로 다른 두 도시로 이동되어야 하기 때문에 제거되는 1개 도로가 {③ ↔ ④}가 된.. 2021. 5. 19.

[SWEA] 1248 공통조상 출처: SWEA Approach 노드 [8]의 부모노드는 [5]이며, [13]의 부모노드는 [11]이다. 위로 올라가면 공통 조상격인 [3]과 [1]이 있으며 가까운 공통 조상은 [3]이 된다. 가장 가까운 공통 조상노드를 기준으로 하였을 때, 서브트리의 크기는 아래와 같다. (기준 노드를 포함한 수치) ① 구조체로 트리(Tree) 구현 - 이진트리이므로 왼쪽/오른쪽 자식노드를 순차적으로 구성 - 공통 조상을 탐색하기 위해 부모노드 표시 ② 첫번째 대상 노드를 시작으로 부모 노드(들) 표시 ex) 정점 [8]에 대해서 [5] → [3] → [1] 노드들이 vistied[] 표시된다. ③ 두번째 대상 노드를 시작으로 조상 노드 추적 ex) [13]을 기준으로 조상 노드를 추적할 때, [11] → [6] →.. 2021. 5. 17.

이전 1 2 3 4 ··· 8 다음

티스토리툴바