mei 기술 블로그

1. 연결 리스트 (Linked List)데이터를 링크로 연결해서 관리하는 자료구조자료의 순서는 정해져 있지만, 메모리상의 연속성은 보장되지 않음장점데이터 공간을 미리 할당할 필요 없음즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이단점연결구조를 위한 별도 데이터 공간 필요연결 정보를 찾는 시간 필요 (접근 속도가 상대적으로 느림)데이터 추가/삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요2. 연결 리스트 기본 구조노드(Node)데이터 저장 단위로 값과 포인터로 구성포인터(Pointer) : 다음 노드나 이전 노드의 연결 정보3. 연결 리스트 기본 연산데이터 추가데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요head에 데이터 추가추가할 데이터를 담을 노드 생성링크 연결 작업..

1. 배열 (Array)많은 수의 데이터를 다룰 때 사용하는 자료구조각 데이터를 인덱스와 1:1 대응하도록 구성데이터가 메모리 상에 연속적으로 저장2. 배열의 장점인덱스를 이용하여 데이터에 빠르게 접근 가능3. 배열의 단점데이터의 추가/삭제가 번거로움미리 최대 길이를 정해서 생성해야 함가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열 생성데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간 유지

1. 자료구조자료를 효율적으로 관리하기 위한 구조관리 -> 저장, 삭제, 탐색, ...목적에 맞게 사용한 좋은 자료구조는 실행시간 단축이나 메모리 용량 절감 효과가 있음나중에 배울 알고리즘과 밀접한 관계2. 자료구조의 분류선형 자료구조배열연결리스트스택 / 큐 / 데크해시 테이블비선형 자료구조트리그래프힙 / 우선순위 큐트라이3. 자료구조의 구현추상 자료형 (ADT, Abstract Data Type)자료 형태와 자료에 대한 연산을 정의한 것구체적인 구현 방법은 명시하지 않음추상 클래스, 인터페이스 참고대부분의 자료구조는 자바에서 클래스로 제공이해를 한 후 알맞은 함수를 사용

1. 파스칼 삼각형이항계수를 삼각형 모양의 기하학적인 형태로 배열한 것첫 번째 줄에는 숫자 1을 쓴다.그 다음 줄부터는 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다.삼각형의 행의 수가 주어지면 파스칼의 삼각형 출력풀이행의 수에 대해 이중 반복문을 돌아 만일 j가 0이거나 i와 j가 같은 경우에는 외각 지역인 숫자가 1인 곳을 의미한다.아니면 위의 왼쪽 값과 오른쪽 값을 더하면 된다.왼쪽 값은 위의 배열인 i - 1에서 j - 1의 값 / 오른쪽 값은 위의 배열인 i - 1에서 j의 값 public static ArrayList> solution(int numRows) { ArrayList> result = new ArrayList(); for (int i = 0; i list = new A..

1. 복잡도 (Complexity)알고리즘 성능을 나타내는 척도시간 복잡도 (Time Complexity)알고리즘의 필요 연산 횟수공간 복잡도 (Space Complexity)알고리즘의 필요 메모리시간 복잡도와 공간 복잡도는 Trade-off 관계일반적으로 메모리를 많이 사용하면 시간을 줄일 수 있다.2. 시간 복잡도 (Time Complexity)어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수빅오(Big-O) 표기법을 통해 나타냄빅오(Big-O) 표기법: 최악의 경우빅오메가 표기법: 최선의 경우빅세타 표기법: 중간의 경우3. 공간 복잡도 (Space Complexity)어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량빅오 표기법을 통해 나타냄일반적으로 메모리 사용량 기준은 MB 단위int[..

1. 제곱, 제곱근, 지수제곱같은 수를 두 번 곱합거듭 제곱: 같은 수를 거듭하여 곱함2^3 = 2 x 2 x 2제곱근 (=root, √ )a를 제곱하여 b가 될 때 a를 b의 제곱근이라고 함√ 4 = √ 2^2 = 22. 로그log a ba가 b가 되기 위해 제곱해야 하는 수log 2 4 = 23. 코드// Math 함수 사용// 제곱Math.pow(2, 3); // 8Math.pow(2, -3); // 1/8// 제곱근Math.sqrt(16); // 4Math.pow(16, 1.0/2); // 4// 절대 값Math.abs(5); // 5Math.abs(-5); // 5// 로그Math.E; // 2.718281828459045Math.log(2.718281828459045) // 1Math.log1..

1. 점화식어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식ex) 피보나치 수열1, 1, 2, 3, 5, 8, 13, ...F1 = F2 = 1, Fn+2 = Fn+1 + Fn2. 재귀함수어떤 함수가 자기 자신을 다시 호출하여 작업을 수행하는 방식반환타입 함수이름 (매개변수) { 종료 조건 ... 함수이름(매개변수) }종료 조건 필수,  없으면 무한 루프에 빠짐3. 코드// 1, 3, 9, 27, ..., n번째 수// 1. 점화식 -> 반복문int n = 4;int result = 1;for (int i = 0; i

1. 조합서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)nCr = n! / (n - r)!r! = nPr / r! (단, 0 2. 중복 조합서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 O)nHr = (n+r-1)Cr3. 코드private static int getComb(int n, int r) { int pResult = 1; int rResult = 1; // nPr for (int i = n; i >= n-r+1; i--) { pResult *= i; } // r! for (int i = 1; i // 조합 구현private static void combination(int[] arr, boolean[..

1. 팩토리얼1에서 n까지 모든 자연수의 곱 (n!)n! = n(n - 1)(n - 2) ... 12. 순열순서를 정해서 나열서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 X)nPr = n! / (n-r)! = n(n - 1)(n - 2) ... (n - r + 1) (단, 0 3. 중복 순열서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 O)nΠr = n^r4. 원 순열원 모양의 테이블에 n개의 원소를 나열하는 경우의 수n! / n = (n - 1)!5. 코드// 1. 팩토리얼// 기본 풀이int n = 5;int result = 1;for (int i = 1; i (x * y)); // 120// 2. 순열/ 5명을 3줄로 세우는 경우의 수n = 5;int r ..

1. 경우의 수어떤 사건에서 일어날 수 있는 경우의 가짓수ex) 동전을 던지는 사건: 경우의 수 - 2ex) 주사위를 던지는 사건: 경우의 수 - 6사건 A가 일어날 경우의 수: n(A)2. 합의 법칙사건 A 또는 사건 B가 일어날 경우의 수사건 A와 사건 B의 합의 법칙: n(A ∪ B)n(A ∪ B) = n(A) + n(B) - n(A ∩ B)3. 곱의 법칙사건 A와 사건 B가 동시에 일어날 경우의 수사건 A와 사건 B의 곱의 법칙: n(A x B)n(A x B) = n(A) x n(B)4. 코드int[] dice1 = {1, 2, 3, 4, 5, 6};int[] dice2 = {1, 2, 3, 4, 5, 6};int nA = 0, nB = 0, nAandB = 0;// 1. 합의 법칙// 두 개의 ..