자료구조, 알고리즘

[백준 11659] 구간합

🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. | 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. | 예제 입력 5 3 5 4 3 2 1 1 3 2 4 5 5 | 예제 출력 12 9 1 🔎 문제분석 이 문제를 반복문으로 풀려고 했을 때, 계속적으로 시간초과가 나타났다. 입출력을 내가 아는 모든 방법을 총동원해서 변경해보았지만 역부족. '뭐지, 풀 수 없는 문제인가' 했었는데,..

선형자료구조 총정리

| 자료구조란? - 자료를 목적에 따라 효율적으로 관리하기 위한 구조이다. - 데이터를 CRUD할 때 유용하다. - 적절히 사용하면 속도를 높히고, 메모리 사용도 줄일 수 있다. | 자료구조의 분류 분류 특징 종류 선형 자료구조 데이터가 1:1관계로 들어가있다. 배열, 연결리스트, 스택/큐/데크, 해시테이블 비선형 자료구조 데이터가 1:N, N:N 관계로 들어가 있다. 트리, 그래프, 힙/우선순위 큐, 트라이 * 선형 자료구조는 기차처럼 길쭉하게 하나의 몸으로 구성되어 있다. * 자료구조를 직접 구현하여(=추상 자료형) 사용할 수도 있다. | 선형 자료 구조 종류 구분 내용 언제 쓰는 게 좋을까 Array 특징 - 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱..

[기초수학] 점화식과 재귀함수

| 점화식과 재귀함수 ✏️ 개념 정리 (1) 점화식 (Recurrence) : 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식 - ex. 피보나치 수열 - 1, 1, 2, 3, 5, 8, 13.... - F1 = F2 = 1, Fn+2 = Fn+1 + Fn (2) 재귀함수 (Recursion) - 종료조건 + 자기 자신을 호출 🛎재귀함수 문제풀기_백준 17478 재귀함수가 뭔가요? | 문제 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다. 중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를..

[기초 수학] 조합

| 조합 (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 !..