Computer Science

[기초 수학] 조합

| 조합 (Combination) ✏️ 개념 정리 (1) 조합 : 서로 다른 N개의 수에서 R개를 뽑아 나열하는 경우의 수 - 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X) - nCr = n! / (n-r)!r! = nPr / r! (단, 0 < r

[백준 2231] 분해합

🛎 2231 분해합 | 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. | 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. | 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. | 예제 입력 216 | 예제 출력 198 🔎 문제분석 어떤 ..

[기초 수학] 순열

| 순열 (permutation) HTML 삽입 미리보기할 수 없는 소스 ✏️ 개념 정리 (1) 팩토리얼 : 서로다른 N개의 수를 일열로 나열하는 전체 경우의 수 - 1~n까지 모든 자연수의 곱 (n!) --- 단, 0!은 1이다. - n! = n*(n-1)...*1 (2) 순열 : 서로 다른 N개의 수에서 R개를 뽑아 나열하되, 순서대로 나열하는 경우의 수 - 서로 다른 n개 중 r개를 선택하는 경우의 수 (순서 O, 중복 X) - nPr = n! / (n-r)! = n(n-1)(n-2)....(n-r+1) (단, 0

[기초 수학] 집합과 경우의 수

| 집합(Set) ✏️ 개념 정리 특정 조건에 맞는 원소들의 모임 - 특징 중복되지 않은 수들을 한 곳에 모아놓는 것으로, 자바에서는 Set을 사용해 중복데이터를 거를 수 있다. - 종류 종류 기호 HashSet 메소드 교집합 A ∩ B a.retainAll(b); 합집합 A ∪ B a.addAll(b); 차집합 A - B a.removeAll(b); 여집합 Ac - 💻 구현하기 [ HashSet 구현해보기 ] HTML 삽입 미리보기할 수 없는 소스 | 경우의 수 HTML 삽입 미리보기할 수 없는 소스 ✏️ 개념 정리 어떤 사건에서 일어날 수 있는 경우의 가짓수 : n(A) 종류 내용 기호 예시 합의 법칙 A와 B의 분리된 집단에 관한 어떤 사건의 경우의 수를 구할 때 * 단 두 집단의 합은 전체 집단이..

기초수학 총정리

보호되어 있는 글입니다.

[기본 알고리즘/자료구조] 소수 나열하기

보호되어 있는 글입니다.

[기본 알고리즘/자료구조] 기수 변환하기 (N진수로 변환)

| 개념 기수란? 수를 나타내는 데 기초가 되는 수. - 10진법에서는 0~9까지의 정수를 말하며, 2진법에서는 0~1까지 정수를 말한다. | 기수 변환을 수행하는 프로그램 package _00_두잇; import java.io.BufferedReader; import java.io.InputStreamReader; public class _01_기수변환 { //정수값 x를 r로 변환하여 배열 d에 아랫자리부터 넣어두고 자릿수를 반환한다. static int convert(int x, int r, char[] d) { int digits = 0; String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //배열 안에 나눈 나머지를 하나씩 넣는다 while (x !..

[정렬] 정렬 문제 풀이 및 속도 비교

■ 정렬의 속도 / 메모리 사용 비교 - 미니멈이 1이고, 맥시멈이 백만인 숫자를 입력받아 정렬한다고 할 때, 어떤 정렬을 쓰는게 좋을까....? - 문제를 풀어본 결과, Merge sort가 가장 빨랐고, 그 다음에 Arrays.sort, 그 다임이 Quck Sort 였다. - 그럼 Arrays.sort는 무슨 정렬을 사용하는 걸까... https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net ■ Collections와 Arrays의 Sor..

[정렬] 병합정렬(Merge Sort)

☆ 공부한 내용을 정리한 내용입니다. 잘못된 부분이 있으면 고정 위해 댓글 부탁드립니다. https://www.youtube.com/watch?v=QAyl79dCO_k&list=PLjSkJdbr_gFZMNhIMl2AJ9n5c2hNK-qJk&index=2 ■ 병합 정렬 - 병합 정렬이란? 요소가 하나만 남을 때까지 리스트를 나눠준 후[분할], 나눴던 리스트를 대소 관계에 맞게 다시 합치는 방법[병합] - 분할 분할 분할 분할.... 병합 병합 병합 병합... 을 반복한 결과 - 안정적이지만, 자료구조를 하나 더 만들 필요가 있다. *자료구조를 더 만들 수 없을 땐 퀵 소트를 쓴다. - 시간 복잡도 O(n log n) , 최악(n log n) ■ 자바로 구현한 병합 정렬 //[[부스트 코스 방식]] stat..

[정렬] 퀵 정렬(Quick Sort)

☆ 공부한 내용을 정리한 내용입니다. 잘못된 부분이 있으면 고정 위해 댓글 부탁드립니다. ■ 퀵 정렬 원리 ) 중심점(Pivot Point)을 임의로 고른 후 이 중심점보다 작은 수를 한 쪽으로 분류하고, 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법 * 분할과 정복 - 중앙값 정렬 방식을 확장하여 개발한 방식. - 평균 정렬 결과가 필요할 때 사용하는 것이 좋다. - 퀵 정렬은 멀리 있는 값을 서로 비교하고 교환하기 때문에 안정성은 떨어진다. - 시간 복잡도 O(n log n) ※ 피벗을 중간 또는 마지막을 잡는 이유 : - 피벗은 첫번째, 중간, 마지막 인덱스나 랜덤으로 선정 가능하다. - 무엇을 피벗으로 잡느냐에 따라 처리 시간이 달라진다. - 피벗 값이 중간 크기일 수록 더 균등하게 리스트를 분할..