분류 전체보기166 [Baekjoon] 1717번: 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 해결 과정 착안 서로소 집합(분리 집합, disjoint set)을 사용하여, 유니온-파인드(union-find) 연산에 의해 포함 관계를 따지는 문제이므로 해당 자료 구조를 구현하여 문제를 해결하고자 하였다. 구현 이 문제에서는 데이터를 정수형의 기본 자료형이기 때문에 인덱스로 간주하여, 유니온-파인드 연산에서 사용할 부모를 나타내는 정보를 배열에 저장.. 2023. 5. 24. [Baekjoon] 2164번: 카드2 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 해결 과정 착안 문제의 의도는 큐(queue)나 덱(dequeue) 등의 자료구조를 활용하여 카드를 버리거나 뒤로 넣는 과정을 반복하는 것을 의도한 것 같았지만 문제 내의 규칙성을 찾아 더 효율적으로 해결을 해보고자 하였다. 문제를 처음 봤을 때, 문제를 간단히 해결할 수 있는 규칙성이 존재할 것이라고 추론할 수 있었던 부분은 작은 수의 $N$에 대하여 문제에서 주어진 과정을 수행하면서 대략.. 2023. 5. 23. [C++ 기초] 부동소수점 표기법(Floating-Point Arithmetic) 부동소수점 표기법(floating-point arithmetic) 부동소수점 표기법이란, 실수(real number)를 고정 정밀도(precision)를 가지는 유효숫자(significand)와 어떠한 밑(base)의 거듭제곱과 곱한 형태로 근사적으로 나타내는 표기법이다. 이때 밑은 일반적으로 진법(numeral system)에 따라 정한다. 고정소수점 표기법: \(12.345\) 부동소수점 표기법: \(12345 \times 10^{-3}\), \(1.2345 \times 10^{1}\) 등 여러 가지로 표현 가능 위의 예시에서와 같이 고정소수점 표기법으로 12.345로 나타내어지는 실수는 부동소수점 방식으로 표현할 때 이론상 무수히 많은 경우의 수로 나타내어질 수 있다. 이처럼 같은 수여도 지수의 값.. 2023. 5. 23. [Baekjoon] 11729번: 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 해결 과정 착안 첫 번째 장대에 쌓여있는 \(N\) 개의 원판을 최소 이동 횟수로 세 번째 장대로 옮기기 위해서는, \(N-1\) 개의 원판을 두 번째 장대로 옮긴 뒤 가장 아래의 원판을 세 번째 장대로 옮기고 다시 \(N-1\) 개의 원판을 세 번째 장대로 옮기는 과정을 수행하여야 한다(이 방법이 정말 최소 횟수로 이동하는 방법인지에 대한 의문이 들 수도 있는데, 이와 관련해서.. 2023. 5. 22. [Baekjoon] 4779번: 칸토어 집합 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 해결 과정 착안 주어진 문제에서의 배열을 3등분하여 왼쪽, 가운데, 오른쪽 부분 배열로 나누고 이때 왼쪽과 오른쪽의 부분 배열에 대해서 같은 과정을 반복적으로 수행하여 최종 답을 얻을 수 있다. 즉, 부분 문제들의 해를 합하여 최종 해를 구할 수 있는 문제이므로 분할 정복(divide and conquer) 알고리즘을 구현하여 문제를 해결하고자 하였다. 인수로 전달되는 배열의 길이가 1이 될.. 2023. 5. 21. [Baekjoon] 24260번: 알고리즘 수업 - 병합 정렬 1 https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 합병 정렬(병합 정렬, merge sort) 의사 코드를 그대로 구현하여 문제를 해결하였다. 구현 알고리즘의 의사 코드를 그대로 제공하여 편리하게 구현할 수 있었다. 처음에는 중간 결과를 합치는 merge 함수에서 사용되는 tmp 배열을 크기에 맞게 계속 할당/해제하는 방식으로 구현했는데, tmp 배열을 아예 최.. 2023. 5. 20. 이전 1 ··· 18 19 20 21 22 23 24 ··· 28 다음
