전체 글

[선형자료구조] 배열과 ArrayList

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 Array 특징 - 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱스가 1 : 1로 매칭 - 많은 양의 데이터를 다룰때 - 특정 위치 자료를 빠르게 선택할때 장점 - 인덱스를 통해 빠르게 데이터에 접근할 수 있다. 단점 - 길이를 미리 설정해야 한다. ArrayList 특징 - 가변 길이 배열 - 삽입 & 삭제 시, 배열을 새로 생성하고 복사한다. 장점 - 크기가 고정되어 있지 않다 (유동적) 단점 - 처음 또는 중간에 데이터를 삽입하거나 삭제할 때마다 배열을 새로 생성&복사하거나, 데이터를 모두 앞으로 미뤄야 한다. | ArrayList은 어떻게 가변적으로 데이터를 관리하나 - ArrayList는 java.util..

자릿수 - 자릿수와 경우의 수

| 자릿수와 경우의 수 (1) X진수의 K자릿수에 대한 모든 경우의 수 어떤 연속된 10진수 수 3개에 대한 배열이 있다고 가정할 때, 각 자리에 올 수 있는 수의 범위는 0 ~ 9이다. 0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 ..... (생략) 10진수의 세 자릿수에 대한 모든 경우의 수는 아래와 같다 --> 10 x 10 x 10 = 1000 (곧, 000 ~ 999) 결국 x 진수의 k자릿수에 대한 모든 경우의 수는 --> x * x * x.... = x^k (자릿수 하나당 0 ~ x-1) (2) x진수의 각 자릿수 하나당 0 ~ x-1 범위를 가지며, x - 1를 넘어서면 올림이 이루어진다. - 10진수일 때 1 1 8 1 1 9..

소수판별법 - 에라토스테네스의 체

| 합성수와 소수 합성수 나누어떨어지는 수가 하나라도 존재하는 수 ex. 100 = 1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10... 소수 오직 1과 자기 자신만으로 나누어떨어지는 수 ex. 3 = 1 x 3 소수에 관한 알고리즘 문제는 보통 아래의 세가지가 있다고 하는데요. 1. 자연수 N이 소수인지 판별하거나, 2. 1~N까지 중 소수의 갯수를 구하거나 3. 1 ~ N 까지의 소수를 나열하는 이 중에서 먼저 1.자연수 N이 소수인지 판별하는 법을 이야기해 보려고 합니다. | N을 2부터 N - 1 까지 모두 나누기 [1] 소수는 1과 자기 자신을 제외한 다른 수로는 나누어떨어져서는 안됩니다. 그것을 판별하기 위한 코드는 아래와 같은데요. 2부터 N - 1가 N의 약수인지 ..

[백준 11660] 구간 합 구하기 5

| 시작하기 전에 지난번에는 일차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루었다면, 이번에는 이차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루어보았다. 🔖 일차원 구간합에 대한 포스팅은 아래에 [백준 11659] 구간합 🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N why-dev.tistory.com 🛎 11660 구간 합 구하기 5 | 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N ..

[백준 17609] 회문 (팰린드롬)

팰린드롬이란, 앞 뒤가 똑같은 전화번호 문자열을 말한다고 합니다. 단순히 "abba" 문자열이 팰린드롬인가를 확인한다면, [1] 문자열을 거꾸로 뒤집어서 확인하거나 [2] 양끝에 left, right로 커서를 두고 left < right 일때까지 양 끝을 비교해도 되는데요. 물론 우리의 알고리즘은 그렇게로만 끝나지 않기 때문에 더 향상된 버전의 팰린드롬을 만날 수 있었습니다. 제 수준에서 풀만한 것들을 먼저 뽑아보았어요.. 아래 중에서 하나씩 풀어보려 합니다. | 백준 팰린드롬 문제 모음 브론즈 1259 팰린드롬수 바로가기 실버 1213 팰린드롬 만들기 1254 팰린드롬 만들기 17609 회문 바로가기 바로가기 바로가기 골드 1053 팰린드롬 공장 바로가기 🛎 17609 회문 | 문제 회문(回文) 또는 ..

[백준 10434] 행복한 소수 - 소수 구하기 + 행복한 수

행복한 수에 대한 연습문제를 풀다가, 백준에 관련된 문제가 있나 싶어 찾아보았습니다. 행복한 수만 구하는 문제는 아니고, 행복한 소수를 구하는 문제가 있었어요. 그래서 한 번 개념 정리를 먼저 하고 문제를 풀어보고 정리를 하려 합니다. | 행복한 수란? 십진수의 수가 있을 때, 예를 들어 14가 있다고 할 때, 각 자릿수를 제곱한 합은 1^2 + 4^2 = 18 입니다. 다시 29의 각 자릿수를 제곱한 합을 구하면 1^2 + 8^2 = 65 이 과정을 계속하다보면, 64,37,58,89,145,42,20,4,16,37,58,89,145,42.... 이 나오게 되는데요. - 어떤 수는 14처럼 '1이 아닌 중복되는 수'를 지점으로 무한히 동일한 수열이 반복되는 반면, - 어떤 수는 제곱합의 끝이 1이 되면..

[백준 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