Algoritum

SCPC 삼성전자 프로그래밍 경진대회 문제 1번 "증강현실 배달 안경" 문제를 풀었습니다. 풀이과정이 틀렸을 수 도있고 대회에 직접적으로 참여한게 아니라서 코드 결과는 확인할 수 없지만 제가 풀었던 풀이과정을 공개하겠습니다. ※ SCPC 사이트에서 문제 공개는 하지않는것을 의무로 한다고해서 배포는 하지 않았습니다. 문제풀이 규칙 정리 1. 테스트케이스 출력 양식을 사용하여 4개의 케이스를 출력한다. 2. 정수형 변수 N, A, B 를 선언한다. N은 사과의 총 개수, A는 A바구니에 들어갈수 있는 총 사과개수, B는 B바구니에 들어갈 수 있는 총 사과 개수이다. 3. 최소값 생성 (변수 A와 B를 비교해서 최소값을 출력하는 코드) 4. switch 문으로 각각의 case1,2,3,4를 구현한다. 5. s..

- Queue의 개념 데이터 큐는 말 그대로 줄서기 자료구조다. 먼저 줄을 선 데이터가 먼저 처리된다. 이것을 선입 선출 (FIFO First in First Out) 이라 부른다. 첫번째와 마지막 위치를 알아야한다. Enqueue 데이터를 큐에 넣는 동작 Dequeue 큐에서 데이터를 거내는 동작 원형 Queue 원형 큐는 선형큐의 반복적 데이터 이동의 단점을 보완한 알고리즘이다. 그림과 같이 front와 rear가 큐 사이즈 내에서 회전한다. Front = (Front + 1) % SIZE; Rear = (Rear + 1) % SIZE; 숙제 = 원형큐를 만들어라 너비우선탐색 (BFS) 물결이 퍼지듯 가까운 경로 후보부터 탐색하는 방법 깊이우선탐색 (DFS) 숙제 = 예제를 만들어라 숙제 = 중위, ..

- 전위순회 트리의 루트 노드 먼저 방문하고 왼쪽 서브트리를 순회한 뒤에 오른쪽 서브트리를 순회하는 방식 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 - 중위순회 왼쪽 서브트리를 순회한 뒤 루트 노드를 방문하고 오른쪽 서브트리를 순회하는 방식 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 - 후위순회 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 전위 30 20 10 6 14 24 22 23 40 34 46 중위 6 10 14 20 22 23 24 30 34 40 46 후위 6 14 10 23 22 24 20 34 46 40 30 - 이진 탐색트리 최대 두개의 자식 노드를 가지는 이진 트리입니다. (왼쪽 서브트리, 오른쪽 서브트리) 정렬 조건 왼쪽 서브트리 < 현재노드 < 오른쪽 서브트리 중복된 값을 가진 노드는..

package LinkedListTest; public class LinkedList { private Node head; private Node tail; private int size = 0; private class Node { private Object data; private Node next; public Node(Object input) { // 값이 input에 매개변수로 전달됨. this.data = input; this.next = null; } public String toString() { // 객체를 보기 편하게 (노드의 데이터값을 보기편하게) return String.valueOf(this.data); } } // 노드를 앞에 넣기 public void addFirst(Objec..

-리스트의 개념 리스트(Linked List)는 자료를 순서대로 연결하여 저장하는 자료구조이며, 주로 포인터를 이용하여 리스트를 연결한다. 단순 연결리스트 단순 연결 리스트는 data와 Link를 갖는 Node로 구성한다. - 강사님 중간 삽입,삭제 할때 배열보다는 linked list가 유리하다. 1. 단일 링크드 리스트 2. 환형 단일 링크드 리스트 3. 더블 링크드 리스트 4. 환형 더블 링크드 리스트 연결리스트 예제 // 연결 리스트의 노드 클래스 정의 class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } // 연결 리스트 클래스 정의 class LinkedList { Node..

package sort; import java.util.Scanner; public class Main { // 난수 설정 public static void prepare(int []arr) { for (int i = 0; i < arr.length; i++) { arr[i] = (int)(Math.random() * 1000); } } // 배열 print public void printSort(int []arr) { for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = new int[1000..

- Bubble Sort /* * 버블 정렬의 시간복잡도는 o(n^2) 입니다. * 배열의 길이를 n이라고 했을대 두개의 중첩된 for문을 사용했기 때문에 o(n^2)이 되었으며 * 첫번째 for 루프는 n-1번 반복하고 두번째 for 루프는 최대 n-1번 반복하기 때문에 * 전체 루프의 실행 횟수는 대락 (n-1) * (n-1)이 됩니다. * */ package sort; public class BubbleSort { public static void bubbleSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); for (int i = 0; i < arr.length - 1; i++) { // 0~배열의 인덱스 -1 만큼 ..

- 정렬 일정한 기준으로 자료의 순서를 변경하는 알고리즘을 정렬(sort)이라 한다. 오름차순 = 1234589 내림차순 = 985421 O(1) - 상수 시간: 입력 크기에 관계없이 일정한 실행 시간을 갖는 알고리즘입니다. 예를 들어, 배열에서 첫 번째 요소를 반환하는 것과 같은 간단한 연산이 이에 해당합니다. O(log n) - 로그 시간: 입력 크기의 로그에 비례하는 실행 시간을 갖는 알고리즘입니다. 이진 검색(Binary Search)과 같은 분할 정복 알고리즘이 이에 해당합니다. O(n) - 선형 시간: 입력 크기에 비례하여 선형적으로 실행 시간이 증가하는 알고리즘입니다. 배열의 모든 요소를 한 번씩 처리하는 경우가 이에 해당합니다. O(n log n) - 선형 로그 시간: 입력 크기에 비례하여..

B 트리 (B-tree) B트리의 정의 ★ 각 노드의 최대 키의 수는 m - 1 최소 키의 수 → (m/2) - 1 각 노드에 포함된 키 순서가 항상 정렬 상태 좌측 서브트리 < 부모 < 우측 서브트리 삽입은 항상 단말 노드에서 발생 삽입되는 키로 인해 최대 키수가 초과되면 노드가 분할되며 중간키가 부모 노드로 이동 트리 구축은 밑에서 위로 진행 트리의 형태 → m-ary 트리 (m개 이하 아들. 각 node의 data수는 m-1) root → 최소 2개의 아들 leaf → 모든 leaf의 레벨은 동일 → 모든 leaf 노드는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다. → 한노드 안에 있는 키 값은 오름차순을 유지한다. → 탐색, 추가, 삭제는 루트로부터 시작한다. node상의 데이터 각 no..

버블정렬(bubble sort) 인접한 두 데이터 A[ i ]와 A[ i+1 ] 비교 A[ i + 1 ] < A [ i ] → 두 데이터 교환 → 가장 큰 데이터가 배열의 끝에 위치 데이터 양이 많을 때 비효율적 시간복잡도(time complexity) 최악+ 최선 + 평균 → O(n^2) 선택정렬알고리즘 (Selection sort algorithm) 각 반복에서 제일 큰 값(또는 제일 작은 값) 을 '선택' 해서, 그 값을 차례로 교환하여 정렬을 이뤄나가는 방식 선택정렬의 종류 → 최소 선택정렬(min selection sort) 최소 데이터부터 차례러 정렬 (오름차순 정렬) → 최대 선택정렬(max selection sort) 최대 데이터부터 차례로 정렬 (내림차순 정렬) 시간복잡도(time com..

충돌(Collision) 두 개의 키가 동일한 버킷으로 해싱되는 경우 동의어(SYNONYMS) 같은 주소로 해싱되어 충돌을 일으킨 키 해싱의 탐색 시간은 O(1) 오버플로우(Overflow) 해시 충돌이 버킷(bucket)에 할당된 슬롯(Slot) 수보다 많이 발생해서 더이상 버킷에 값을 넣을 수 없는 현상 해싱 특징 검색 속도가 빠르며 삽입, 삭제의 빈도가 높음 해싱 기법에는 숫자분석법, 제산법, 제곱법, 접지법이 있다. 오버플로가 발생했을 때 해결기법으로 개방주소법(open addressing) 과 폐쇄주소법(close addressing)이 있다. 해싱 장점 레코드를 찾기 위해 키 값을 모두 비교할 필요 없다. 순차파일에서 데이터 탐색 시간 O(n) 키 값을 직접 주소로 사용하는 경우보다 기억장소 ..

장점 : 고속 탐색 가능 단점 : 정렬 데이터에만 적용 가능 time complexity(시간복잡도) : O(log n) 이진탐색트리 (Binary sarch tree) 정의 : 탐색작업을 효율적으로 하기 위한 자료구조 왼쪽 서브트리 노드의 키값 < 루트 노드의 값 < 오른쪽 서브트리 노드의 키값 AVL 트리 최악의 경우 = O(n) 트리 균형이 나쁘면 = O(log n) 트리구조가 complete binary tree인 경우 바람직. 정의 : 모든 노드에 있어 왼쪽 서브트리와 오른쪽 서브트리 높이 차가 1이내인 binary search tree ★ 왼쪽 높이 - 오른쪽 높이 = 1이내 AVL 트리 삽입 Binary Search Tree 삽입과 동일 균형 조정 leaf에서 root를 향해 차례로 진행 필..