IT&컴퓨터공학/자료구조&알고리즘
-
[13] 심화 정렬 ( SORT ) - Heap SortIT&컴퓨터공학/자료구조&알고리즘 2020. 7. 5. 13:06
Heap Sort - 최악의 경우에도 시간 복잡도 O(nlog2n) - 추가 배열도 필요하지 않음 - 이진 힙 ( binary heap ) 자료구조를 사용 힙을 알려면 Tree 와 Binary Tree 를 알아야함. Tree 트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것 이 속성 때문에 트리는 다음 성질을 만족함. 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다. 회로(cycle)가 존재하지 않는다. 모든 노드는 서로 연결되어 있다. 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다. 엣지(edge)의 수 |EE| 는 노드의 수 |VV|에서 1을 뺀 것과 같다. 참조 ↓ https://ratsgo.github.io/data%20s..
-
[12] 심화 정렬 ( SORT ) - Quick SortIT&컴퓨터공학/자료구조&알고리즘 2020. 6. 28. 17:25
분할 정복법(divide and conquer) : Merge Sort, Quick Sort 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제를 순환적으로해결 Merge Sort 는 그냥 배열을 반씩 쪼개는데 반해, Quick Sort 는 Pivot 을 기준으로 사용해서 분할함. 아래의 코드는 Pivot 을 배열의 가운데 수로 정했을 때 퀵소트 예시 import java.util.Scanner; // Quick Sort public class sort_2 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[]..
-
[11] 심화 정렬 ( SORT )IT&컴퓨터공학/자료구조&알고리즘 2020. 6. 25. 23:42
분할 정복법(divide and conquer) : Merge Sort, Quick Sort 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제를 순환적으로해결 Merge Sort Merge ( 합병 ) : 작은 문제의 해를 합해서 원래 문제에 대한 해를 구함 // 합병정렬 public class sort_1 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 배열 크기 int[] arr = new int[n]; for(int i =0; i
-
[9] 순환함수 ( 재귀함수 ) - JAVA 를 이용한 이미지 블럭의 사이즈 구하기IT&컴퓨터공학/자료구조&알고리즘 2020. 6. 22. 18:26
public class counting { static int alreadyCount =2; // alreadyCount : 이미 count 한 이미지 픽셀 static int size =8; // image 의 크기는 size X size static int cnt =0; // 카운트 수 ( 정답 ) public static void main(String[] args) { int[][] image = { // 0 은 빈칸, 1은 pixel {1,0,0,0,0,0,1,0}, {0,1,1,0,0,0,0,0}, {1,1,0,0,0,1,0,0}, {0,0,0,0,1,0,1,0}, {0,0,0,0,0,1,0,0}, {0,1,0,0,0,1,0,1}, {0,1,0,0,0,1,0,1}, {1,1,1,0,1,0,1,1..
-
[08] 순환함수 ( 재귀함수 ) - JAVA로 미로찾기 문제 구현IT&컴퓨터공학/자료구조&알고리즘 2020. 6. 22. 17:13
public class maze { static int size = 8; // 미로는 size X size 크기 static int visited =2; // visited : 방문한 길 표시 static int cannot =3; // cannot : 막혀있는 길 표시 -> 동서남북 다 보더라도 벽이거나 왔던 길밖에 없어서 새로운 길로 가지 못하는 경우 public static void main(String[] args) { int[][] maze= { // 0은 길, 1은 벽 {0,0,0,0,1,0,0,1}, {0,1,1,0,1,1,0,1}, {0,0,0,1,0,0,0,1}, {0,1,0,0,1,1,0,0}, {0,1,1,1,0,0,1,1}, {0,1,0,0,0,1,0,1}, {0,0,0,1,0,0,..
-
[07] 순환 ( Recursion ) 이란?IT&컴퓨터공학/자료구조&알고리즘 2020. 6. 19. 22:47
Recursion ( 순환 ) 함수 : 자기 자신을 호출하는 함수. 재귀함수라고도 한다. void function(){ ..... function(); // 이런식으로 ! ...... } public static void main(String [] args){ function(); // 결과 : Hello ! 무한 반복 루프 } void function(){ System.out.println("Hello !"); function(); } 재귀함수를 위처럼 아무 조건없이 짜면, 무한루프에 빠진다. 따라서 우리는 재귀함수가 무한 루프에 빠지지 않도록 조건을 지정해줘야함. public static void main(String [] args){ function(4); // 결과 : Hello ! 4번 } vo..
-
[06]C언어 연결리스트 :: 이중연결리스트/이중연결리스트설명/이중연결리스트 초기화/삽입IT&컴퓨터공학/자료구조&알고리즘 2019. 2. 20. 16:47
요 앞전에는 단일연결리스트를 알아봤는데요 ↓↓ 2019/02/08 - [IT&컴퓨터공학/자료구조&알고리즘] - [04]C언어 연결리스트 :: 단일리스트 초기화/삽입 2019/02/12 - [IT&컴퓨터공학/자료구조&알고리즘] - [05]C언어 연결리스트 :: 단일연결리스트 데이터 탐색/삭제/출력 이번에 알아볼 리스트는 바로 " 이중연결 리스트 " 입니다. 양방향연결리스트 라고 불리기도 해요 !! 앞에서 봤던 단일연결리스트에서는, 왼쪽노드가 오른쪽 노드만을 가르키기 때문에, 20에서 30으로 가는 방법이 없어요 ! 그래서 예를들어 20 왼쪽에 있는 노드를 삭제해라 ! 라고 하면20을 찾는 노드 cur 만으로 해결할 수 없고20의 왼쪽에 있는 노드를 가르킬 before 노드가 하나 더 필요했습니다. 이 단점..
-
[05]C언어 연결리스트 :: 단일연결리스트 데이터 탐색/삭제/출력IT&컴퓨터공학/자료구조&알고리즘 2019. 2. 12. 16:42
데이터 탐색 이러한 단일연결리스트가 있을때 데이터 탐색을 해볼까요 ? 탐색은 아주 쉬워요 ! 데이터 탐색의 과정은 위 그림처럼Cur 이라는 노드 포인터로 Head 다음부터 마지막 NULL 까지 차례대로 넘어가면서 찾는 데이터가 있으면 출력하고, 없으면 원하는 데이터가 없다고 출력합니다. 이 과정을 코드로 나타내보면 12345678910111213141516171819202122void Search(List *L, int number){ Node *cur = L->head; // cur 이 리스트의 head를 가르킨다. if (L->head->next == NULL) { printf("저장된 데이터가 없습니다 !\n"); } else // 그 외에 ( head 와 NULL 사이에 하나라도 데이터가 있다면 ..