CS지식
-
자료구조 - 하노이 탑(Tower of Hanoi)재귀 호출 코드 구현CS지식/자료구조 2023. 12. 26. 11:44
하노이 탑 재귀 호출 코드 구현 각각의 기둥을 A, B, C라고 하고 원반의 갯수를 n이라고 하고 문제를 풀어 본다. 원반의 갯수가 1인 경우 A기둥에 있는 원반을 목표하는 B기둥으옮기기 위해서 (A → B) 이동 횟수 1회가 발생한다. 원반 갯수가 2개인 경우 원반1 (A → C) 원반2 (A → B) 원반1 (C → B) 1)A기둥에 원반1,2가 있다. → 2)일단 원반1을 C기둥으로 옮긴다.→ 3)원반2를 B기둥으로 옮긴다. → 4)원반1을 B기둥으로 옮긴다. 이렇게 하면 원반을 모두 목표하는 기둥으로 옮기게 되는데 이때는 3회의 이동 횟수가 발생한다. 원반 갯수가 3개인 경우 원반의 갯수가 3개여도 (A → C), (A → B), (C → B) 이동 과정을 거쳐 원반1,2가 임시 장소인 C에 가는..
-
JAVA 자료구조 (재귀와 귀납적 사고) - 재귀 구조 예CS지식/자료구조 2023. 12. 25. 14:04
2.재귀 구조의 예 3. 선택정렬 배열 A[0..n-1]에 n개의 원소가 주어지고 이를 크기순으로 정렬하려고 한다. 여러 정렬 알고리즘 중 가장 기초적인 알고리즘인 선택 정렬의 예를 살펴보자. [알고리즘 2-5]의 선택정렬 알고리즘에서 먼저 전체를 한 번 훑어 가장 큰 원소를 찾는다.(2️⃣) 이 원소를 제일 오른쪽 원소와 맞바꾼다.(3️⃣) 그러면 맨 오른쪽 제일 큰 원소가 자리하게 되고 이 원소는 더 이상 자리를 바꿀 필요가 없다. 즉, 제일 큰 원소에 관한 한 정렬이 끝난 것이다. 이제 맨 오른쪽 원소를 관심 대상에서 제외한다. 그러면 A[0...n-2]에 n-2개 짜리 정렬 문제가 남는다. 즉, 가장 큰 뭔소를 찾아 맨 오른ㅉ고 원소와 맞바꾸는 수고를 하고나면 자신과 성격이 똑같지만 크기가 하나만..
-
자료구조(그래프 탐색) - 깊이 우선 탐색(Depth-First Seach, DFS)CS지식/자료구조 2023. 12. 25. 13:00
깊이 우선 탐색(Depth-First Seach, DFS) 1단계) A를 시작점, G를 목표로 해서 탐색을 시작한다. 2단계) A에서 도달할 수 있는 정점은 B,C,D이므로 다음 후보로 표시한다. 후보 중에서 하나의 정점을 선택한다. 선택기준은 후보중 가장 최근에(가장 늦게) 추가된 것입니다. 3단계) 동일 시점에 후보가 된 정점은 어느 것을 선택하든 상관 없다. 여기선 왼쪽에 있는 정점을 선택한다. 모두 동일한 시점에 후보가 됐으므로 B를 선택한다. 선택한 정점으로 이동한다. 현재 있는 B로 부터 도달 할 수 있는 E와 F를 새로운 후보로 추가한다. 4단계) 후보인 정점은 '후입선출(LIFO)'구조로 관리하므로 '스택'데이터 구조를 이용할 수 있다. 후보중에 가장 최근에 추가된 것은 E와 F이다. 이중..
-
JAVA 자료구조(재귀와 귀납적 사고) - 자료구조와 재귀, 재귀 구조 예CS지식/자료구조 2023. 12. 25. 11:20
1.자료구조와 재귀 재귀는 '내 안의 나를 찾는 것'이다. 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것이다. 단순한 예로 시작해보자. 1부터 n까지 곱하는 n!(n 팩토리얼)은 n! = 1 x 2 x 3 x ... x(n - 1) x n 이다. 여기서 맨 끝에 있는 n만 제외하면 1 x 2 x 3 x ... x (n -1)인데 이것은 (n - 1)!이다. n!은 여기에 n만 더 곱하면 된다. 즉, n! = n x (n - 1)이다. 크기가 n인 팩토리얼은 크기가 n -1인 팩토리얼을 포함하고 있다. 이 처럼 어떤 문제나 함수 등이 자신과 선격이 똑같지만 크기가 더 작은 문제를 하나이상 포함하고 있을 때 재귀적 구조를 작고 있다고 말한다. 대부분의 프로그래밍 언어..
-
JAVA 자료구조 - 자료구조의 추상 데이터 타입CS지식/자료구조 2023. 12. 24. 13:10
자료구조의 추상 데이터 타입 1. 추상 의미의 단위를 흔히 모듈(Module)한다. 통상적으로 모듈은 먼저 추상적인 레벨에서 설계되고, 구체화 된다. 모듈을 추상화 Abstraction하나든 것은 세부 사항을 생략하고 가장 중요한 기능만 드러내는 것을 말한다. 추상화는 '위에서 - 아래로' 이루어질 수도 있고, '아래에서-위로' 이루어질 수도 있다. 큰 그림을 먼저 그리고 점차 작은 모듈로 나우어가는 과정은 '위에서 - 아래로 ' 방식이다. 반면 최하단 부 단위들을 준비하고 거기서부터 선택과 조합, 새로움을 가미하여 상위 레벨의 그림을 만들어 내는 과정은 '아래에서-위로' 방식이다. 일상에서 접하는 추상은 이 두 방식이 혼재한다. 2. 추상 데이터 타입 : ADT 추상 데이터 타입(ADT: Abstrac..
-
JAVA 자료구조 - 자료구조란?CS지식/자료구조 2023. 12. 22. 15:36
자료구조란? 1. 자료구조는 데이터를 저장, 조직, 관리하는 방법 자료구조는 자료(데이터)에 효율적으로 접근하고 수정할 수 있도록 저장 · 조직 · 관리하는 방법에 관한 이론이다. 2. 자료구조는 문제 해결에 사용할 부품 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것을 알고리즘이라고 하는데 자료구조는 이 과정에서 부품 같은 역할을 한다. 건축물을 만들려면 건축 재료와 구조물에 대한 이해가 필요하다. 재료에 대해 잘 알고 있어야 필요한 곳에 알맞은 재로를 사용하고 조합할 수 있다. 자료구조를 잘 몰라도 프로그램을 작성할 수 있지만 이는 재료의 속성이나 구조물을 구성 방법을 모르고 건축물을 만드는 것과 같다. 자료구조는 프로그램으로 구현되고 사용되므로 자료구조를 학습..
-
JAVA 자료구조 - 연결 리스트(LinkedList)개념정리CS지식/자료구조 2023. 12. 22. 13:49
연결 리스트(Linked List) 개념정리 결국에 컴퓨터 프로그램이 활용하는 메모리 공간에는 용량 제한이 있다. 메모리는 위 바둑판과 같이 생긴 저장 공간으로 2차원 배열이라고 생각하면 쉽다. 실제로 그렇지는 않겠지만 엑셀처럼 행은 오름차순의 숫자의 주소를 가지고 열은 오름차순의 알파벳 주소를 가진다고 가정하자 그렇다면 array자체의 주소는 A1이고 각각 1 - B1, 2 - C1, 3 - D1, 4 - E1, 5 - F1, 6 - G1의 각각 주소를 가진다. 다른 말로 하면 각 간을 메모리도 다 별개의 주소가 있다. 이렇게 이상적으로 배열을 메모리 위치가 서로 인접해 있다. 다음에 요소를 추가 할때는 A2에 추가 하는 것이 가장 이상 적일 것이다. 하지만 이미 A2에는 객체가 메모리를 차지하고 있을..
-
JAVA 자료구조 (배열) - 배열 파티션 ⅰCS지식/자료구조 2023. 12. 21. 15:25
배열 파티션 ⅰ 오름차순 풀이 페어의 min()을 합산했을 때 최대가 되려면 결국 각각의 min() 조합이 가급적 머야 한다는 뜻이다. 실제로 그림 7-10에서 하나씩 조합해보면 동일한 결과를 얻을 수 있다. 오름 차순으로 정렬된 상태에서 인접 엘리먼트 페어(Adjacent Elements Pair)를 만들면 가장 큰 a₁과 a₂ 페어들을 만들 수 있고 이 페어들의 min()의 합이 곧 만들 수 있는 최대 합이 된다. Pair의 min을 합하는 코드 public int solution(int [] nums) { Arrays.sort(nums); List pair = new ArrayList(); int sum =0; for(int n: nums){ pair.add(n); //페어 변수에 값이 2개 채워지..