Coding test/Algorithm
: 큰 문제를 나누어서 풀고, 그 결과를 조합해서 문제를 해결하는 알고리즘 기법. - 분할 (Divide) : 해결할 문제를 여러개의 작은 문제로 나눈다. - 정복 (Conquer) : 작은 단위의 문제를 해결한다. - 조합 (Merge or Combine) : 해결한 작은 단위 문제들을 합해 원래 문제의 답을 구한다. 1. 하노이의 탑 : 세 개의 기둥과 기둥에 꽂을 수 있는 서로 다른 크기의 원반이 있다. 전부 하나의 기둥에 큰 것이 아래에 있도록 꽂혀있다. - 한 번에 하나의 원반만 옮길 수 있다. - 가장 위의 원반만 옮길 수 있다. - 큰 원반이 작은 원반 위에 놓여서는 안된다. - 위의 규칙을 지키면서 하나의 기둥에서 다른 기둥으로 모든 원반을 옮긴다면? 1) 원반이 두 개인 경우 : 3회 2..
- 특수한 형태의 완전 이진 트리 1. Heap - 완전 이진 트리의 어떤 노드 C와 부모 노드 P가 있을 때 C의 값보다 P의 값이 항상 크거나 / C의 값보다 P의 값이 항상 작을 때. - 다양한 요소를 가지고 있는 집합에 대하여 가장 큰 값이나 가장 작은 값을 찾기 용이함. - 우선순위 큐를 만드는데 유용하게 사용됨. 1) 힙 삽입 연산 - 제일 오른쪽 아래에 원소를 삽입 - 새로 삽입한 원소를 부모 노드와 비교 (힙의 조건을 만족시키지 못하게 배치된 경우 서로 교환) - 새로 추가한 원소가 루트 원소가 되거나, 힙의 조건을 만족시킬 때까지 반복 2) 힙 삭제 연산 - 힙의 루트 원소를 제거 - 루트 원소의 위치에 힙의 마지막 원소를 배치 (완전 이진트리 조건) 2. Heap Sort : Heap의..
- 원소들 간에 1:N 관계를 가지는 비선형 자료구조 - 상위 원소와 하위 원소의 관계가 있는 계층적 자료구조 1. 정의 : 한 개 이상의 노드로 이루어진 유한 집합. - 노드/정점 : 각각 데이터를 담고 있는 원소 - 루트 노드 : 노드 중 최상위 노드 - 각 노드는 0개 이상의 자식 노드를 가질 수 있음. - 하나의 부모에 여러 자식이 연결 - 하나의 자식은 둘 이상의 부모 X - 노드의 갯수가 N개일 때, N-1개의 간선을 가지고 있음. -> 그래서 순환 구조가 생기지 않음. (cf. Graph는 순환 구조가 있음.) - 형제 노드 : 같은 부모 노드를 가진 자식 노드들 - 조상 노드 : 간선을 따라 루트 노드까지 가는 경로의 모든 노드들 - 차수 (Degree) : 노드에 연결된 자식 노드의 수 ..
다이나믹 프로그래밍이란? : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 > 여러 개의 하위 문제로 나누어 풀고 저장한다. 그것을 결합하여 최종적인 목적에 도달한다. > 나중에 같은 하위 문제가 나왔을 경우 간단히 해결 가능하고, 계산 횟수를 줄일 수 있다. 1) 최적 부분 구조 : 큰 문제의 최적해가 작은 문제의 최적해를 포함해야 한다. 그래야 작은 문제의 최적해를 구한다음 그것을 활용하여 큰 문제의 최적해를 구할 수 있으니까~~ 2) 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다. ex. 피보나치 수열 ~> 0과 1로 시작하고 이전의 두수 합을 다음 항으로 하는 수열. (n은 자연수) fib(0) = 0, fib(1) = 1 ver 1. 재귀함수 public static..
1. Brute Force : 무작정 가능한 모든 경우를 다 검사하는 알고리즘. ex. 4자리의 숫자로 이뤄진 비밀번호를 구해야 한다.... > 0000~9999까지 모두 해본다...? 방법은 간단하다. 모든 경우의 수를 확인해 보는 것...! 그러나, 경우의 수가 늘어나기 시작하면 수행속도가 느려지기 시작한다... 그렇지만 해답을 못 찾은 가능성이 적으므로 절! 대! 모르겠으면 일단 접근해볼 수 있는 방법이다. 2. 순열 : 서로 다른 것들 중 몇 개를 뽑아서 한줄로 나열하는 것. 서로 다른 n개 중 r개를 꺼낼 때 만들 수 있는 순열의 갯수는.......? (n개 중에서 r개 고르기) - r = n인 경우 (n개 중에서 n개 고르기) > n 팩토리얼 (n!) - nPr을 팩토리얼을 이용해 표현 ~> ..
1. Queue 개요 Queue이란? : 대기열처럼 작동하는 자료구조. -자료가 일렬로 놓인 선형 자료구조 - 제일 먼저 추가된 자료가 먼저 나오는 선입선출 자료구조. (First In First Out) ** front & rear : 큐의 양쪽 지점을 위한 변수 (초기값 -1) Queue에 데이터 추가 : enQueue > rear의 크기 증가 후 arr[rear]에 할당 Queue에서 데이터를 회수 : deQueue > front의 크기 증가 후 arr[front]에 할당 Queue가 비었는지 확인 : isEmpty > front == rear Queue의 제일 앞에 있는 데이터를 확인 : peek() Queue가 가득 차있는지 확인 (고정된 배열을 사용하는 경우) : isFull() - 구현해본 ..
~ 정렬 ~ : 2개 이상의 자료가 모여있을 때 특정 기준으로 작은 값부터 큰 값으로 재배열하는 행위. 1. Bubble Sort 버블정렬 : 인접한 두 자료를 비교하며 자리를 교환하는 방식 (마치 한번의 단게가 반복될때마다 큰 숫자가 위쪽 인덱스로 넘어가는 모습에서 거품이 일어나는 것 같다는 의미) 1) 첫번째 원소와 두번째 원소를 비교한다. 만약 첫번째 원소가 두번째 원소보다 더 크다면 둘의 자리 교환. 2) 두번째 원소와 세번째 원소도 동일하게 비교하고 교환. 이를 마지막 두 원소까지 반복. >> 이렇게 한바퀴 돌면 ? 제일 큰 원소가 제일 오른쪽으로 간다. 다음에는 제일 큰 원소 제외하고 반복. - 버블 정렬 코드 더보기 public class BubbleSort { public static vo..
- 문제를 해결하기 위한 절차. (절차가 없다면 알고리즘이 아니다..!) * 의사 코드와 순서도를 이용해 많이 표현된다. 1. 알고리즘 평가 기준 정확도 - 답을 정확하게 찾아내는지 작업량 - 얼마나 적은 작업(할당, 연산 등)으로 정답을 찾아내는지 (속도) 메모리 사용량 - 얼마나 적은 메모리를 사용하는지 1) 시간 복잡도 if ) 1부터 n까지 모든 자연수의 합을 구한다. // 총 수행되는 할당 및 연산 : 2*n + 1 public static int sumUntilN(int n) { // 할당 1번 int sum = 0; for (int i=1; i> StringBuilder를 사용하면 문자열 뒤쪽에 append 메서드를 통해 데이터를 추가할 수 있다. // +연산자 사용 public class ..
