Baekjoon
2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 📌 접근 방법 😱 쉬워보였지만 매우매우 어려웠다 😅 N = 3일 경우 공백 (1, 1) N=9일 경우 공백 (1,1), (1,4), (1,7) (3,3), (3,4), (3,5) (4,1), (4,3), (4,4), (4,5), (4,7) (5,3), (5,4), (5,5) ➡️ 규칙 작은 공백은 (x%3==1)&&(y%3==1)의 조건을 만족할 때 공백이 생긴다는 것을 알 수 있었다. 큰 공백은 ((x/N)%3==1)&&((y/N)%..
17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 📌 접근 방법 ✔ 에라토스테네스의 체(Sieve of Eratosthenes) 소수를 효율적으로 찾아내는 알고리즘 큰 범위의 소수를 빠르게 구할 수 있음 시간 복잡도 : O(n log log n) 참고 링크 동작과정 2부터 시작하여 소수인 숫자를 찾음 현재 소수인 숫자를 제외한 그의 배수들을 모두 제거함 다음으로 넘어가서 아직 제거되지 않은 가장 작은 숫자를 찾고, 해당 숫자를 소수로 간주함 위의 과정을 반복하여 소수를 찾아냄 ✅ Pass Code #include ..
4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 📌 접근 방법 '-'를 3ⁿ 개 나열한 후 3등분하여 가운데를 공백으로 해야 함! 재귀호출을 이용해서 3등분 중 첫 번째, 세 번째만 출력되고 두 번째는 " "(공백)이 출력되게 구현 ✔ 칸토어 집합 0과 1 사이의 실수로 이루어진 집합 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만드는 집합 ✅ Pass Code #include #include #include #include #include #include #..
24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 📌 접근 방법 합병정렬을 이용하여 풀었다. ✔ 합병정렬(Merge Sort) 배열이 2 개의 배열로 분할되고 크기가 1/2로 감소하는 분할 정복 알고리즘 크기가 n인 배열을 n/2 크기의 2개의 배열로 분할하는 것을 반복 더이상 분할할 수 없을 때 오름차순으로 다시 정렬하며 합병하는 것 ! 성능 : nlogn ✅ Pass Code #include #include #include #include #include #in..