이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.
[TOC]
- 클래스, 이너클래스에 대한 지식
- 제네릭에 대한 이해
- 생성자에 대한 이해
- 클래스 합성(reference를 이용하는 것)에 대한 아주 조금의 지식
- GC에 대한 아주 조금의 지식
- 재귀에 대한 아주 조금의 지식
- 그리고 이 스터디를 하는 분들에게 필요한 다른 언어를 파악하는 능력 한 방울
위의 사항들 중 부족한게 있다면, Java 기본서를 한 번 읽고 오시는 것을 권장드립니다.
아니면 부족하다고 느끼시는 분이 많을 경우, 한 번 간단하게 정리하는 시간을 가져보도록 할게요.
다른 언어는 제가 부족하기 때문에, 저도 틀리는 부분이 있을 수 있고, 서로 함께 헤쳐나갈 수 있었으면 좋겠습니다.
자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명합니다.
여기서 구조체라는 표현이 나오는데, 구조체는 C언어에서 나오는 개념이고 Java에서 동치되는 것은 없습니다. 왜냐하면 Java는 객체지향 언어인데, 이 객체지향 언어에서는 데이터와 로직이 한 클래스 안에 담겨있기 때문입니다. 구조체는 데이터만 저장하는 클래스라고 일단 생각해둡시다.
넓은 의미에서 int형 변수, Class도 자료구조에 속합니다. 왜냐하면 이들 역시 데이터를 표현하고, 저장하는 하나의 방법이기 때문이죠. 또 배열도 자료구조의 일종입니다.
자바의 배열은 하나의 오브젝트입니다. 내부 구현상으로 java.lang.Object를 상속합니다.
선형 자료구조: 리스트, 스택, 큐
비선형 자료구조: 트리, 그래프, 해시 테이블
선형 자료구조는 자료를 표현하고 저장하는 방식이 선형(linear)입니다. 말 그대로 선을 떠올리면 됩니다. 시작과 끝까지 항상 일렬로 저장되게 됩니다.
비선형 자료구조는 데이터를 나란히 저장하지 않습니다. 따라서 선형 자료구조에 비해서 학습이 어려울 겁니다. 하지만, 비선형 자료구조가 계속해서 코딩테스트에서 다뤄지기도 하거니와, 스터디가 끝난다고 하더라도 복습하면 되기 때문에, 너무 큰 부담을 느끼지는 않았으면 합니다.
- 자료구조의 모델 자체에 대한 이해
- 코드 레벨에서의 자료구조 구현
이전 스터디에서는 코드 레벨에서의 자료구조 구현을 통해 자료구조에 대한 프로그래밍적 이해를 돕고자 노력을 했습니다. 어찌되었든 구현을 한다는 것은 직접하는 것이기 때문에 작성하면서 자료구조에 대한 학습이 적더라도 자료구조에 대한 이해가 높아졌으리라 생각합니다. 그리고 제네릭이나 노드로 저장하는 방식에 대한 이해도 많이 되셨으리라 생각합니다. 덧붙여서 코드레벨로 구현해보지 못하신 분들은 이번 스터디에서 꼭 도전해보셨으면 좋겠습니다.
사족은 줄이고, 자료구조를 학습하는 이유는 간단합니다. 이 자료구조를 '언제 어느 상황에서 가져다 써야하는가?' 라는 선택의 기준을 우리 스스로 확립하는 것입니다. 이런 선택을 하기 위해서는 여러 자료구조에 대한 이해가 반드시 동반되어야 합니다.
코드스쿼드에서 Set 을 열심히 사용하는 분들을 실제로 몇 번 봤습니다. Set 자료구조의 핵심은 뭘까요? 이것은 언제 쓰면 적합한 자료구조일까요? 마찬가지로 언제는 Map 을 쓰고, 언제는 List 를 쓰고 이것을 선택할 때 우리는 근거가 있어야 합니다. 그 근거가 부실하면, 좋은 프로그램을 작성할 수 없다고 저는 생각합니다. 적절한 상황에 적합한 자료구조를 선택할 때, 프로그램은 읽기 쉬워지고, 읽기 쉬워지면 이해하기가 쉬워지고, 이해하기 쉬운 코드는 결국 유지보수하기 좋은 코드가 됩니다.
자료구조와 알고리즘은 항상 세트로 불립니다. 왜일까요? 사실 둘은 전혀 다른 얘기지만, 뗄래야 뗄 수 없는 관계이기도 합니다.
자료구조는 앞서 말했듯이 '데이터의 표현 및 저장방법'을 뜻합니다. 반면 알고리즘은 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'을 뜻합니다.
자료구조가 결정되어야만 알고리즘을 선택할 수 있습니다. 따라서 알고리즘 문제를 푼다고 했을 때, 자료구조에 대한 이해가 없다면 난이도가 조금이라도 높아졌을 때, 효율적인 풀이 방법을 선택하지 못할 수도 있습니다.
시간 복잡도와 공간 복잡도에 대해서 다룹니다.
시간복잡도는 알고리즘 문제를 풀 때 1억 건에 1초라고 생각하면 쉽습니다.
시간복잡도가 O(
$n^2$ )인 솔루션의 경우 100000건의 데이터는 1초정도에 처리할 수 있다라고 생각하시면 됩니다.
시대가 발전함에 따라 시간복잡도와 공간복잡도중 어떤것이 더 중요하냐라고 질문하면 지금은 시간복잡도가 중요하다고 말할 수 있을 것 같습니다. 따라서 알고리즘 문제도 시간복잡도를 개선하는 방향으로 생각하는 편이 좋습니다.
왜냐하면 시간 복잡도를 개선하는 방법중 가장 쉬운 방법은 공간복잡도를 희생하는 방법입니다. 대표적으로 해시 테이블이 있습니다.
사실 메모리도 적게먹고 시간도 적게걸리면 최고의 알고리즘이라고 할 수 있는데, 그걸 모두 만족하기는 매우 어렵습니다. 오히려 한 쪽을 선택한다면 한 쪽을 희생해야하는 트레이드 오프 관계에 가깝습니다.
이 부분은 제가 설명하기보다는 책을 통해 이해하고 여러번 봐야하는 부분이라고 생각합니다.
순차 탐색 Java 코드 LinearSearch.java
public class LinearSearch {
public static void main(String[] args) {
int[] arr = {3, 5, 2, 4, 9};
int idx = lSearch(arr, 4);
printSearchInfo(idx);
idx = lSearch(arr, 7);
printSearchInfo(idx);
}
public static int lSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
public static void printSearchInfo(int idx) {
String info = "탐색 실패";
if (idx != -1) {
info = "타겟 저장 인덱스: " + idx;
}
System.out.println(info);
}
}결과
타겟 저장 인덱스: 3
탐색 실패
시간복잡도를 분석할 때 중요한 점은 코드에서 어떠한 연산이 중요하게 다루어지는가 입니다. 따라서 핵심 연산을 통해 시간복잡도를 분석하면 됩니다. 예를 들어서 위의 코드에서는 탐색할 때 해당 숫자가 존재하는지 비교하는 연산이 핵심이 됩니다.
왜 BigO 표기법을 사용하는가? 에 대한 질문도 이해해두면 좋습니다. 최선의 경우는 말할 필요도 없고, 평균적인 경우가 문제가 되는데, 평균적인 경우를 어떻게 정할 것이며, 이를 어떻게 계산할 것인지가 굉장히 큰 난관이 됩니다. 따라서 논란의 소지가 가장 없고 신뢰도가 높은 BigO 표기법을 사용하게 됩니다.
- 전제 조건: 배열에 저장된 데이터는 정렬되어 있어야 합니다.
이진 탐색 알고리즘은 간단하게 말해서 절반을 쪼개고 그 중앙에 있는 값이 찾으려는 것보다 작은지 큰지 판단해서 작다면 큰 부분을 크다면 작은 부분을 버리는 알고리즘입니다. 왜 정렬이 되어있어야 하는지 여기서 파악할 수 있습니다. 최악의 경우에도
교재에서 그림을 잘 보세요. 탐색의 범위는 작을 경우 last의 위치가 변하고, 클경우 first의 위치가 변합니다.
여기서 이진탐색은 재귀로도 구현이 가능하고(같은 동작을 반복하므로), 반복문으로도 당연히 구현가능합니다.
이진탐색 Java코드 BinarySearch.java
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int idx = bSearch(arr, 7);
printSearchInfo(idx);
idx = bSearch(arr, 4);
printSearchInfo(idx);
}
public static int bSearch(int[] arr, int target) {
int first = 0; // 탐색 대상의 시작 인덱스 값
int last = arr.length - 1; // 탐색 대상의 마지막 인덱스 값
int mid;
while (first <= last) {
mid = (first + last) / 2; // 탐색 대상의 중앙을 찾는다.
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) { // 탐색 대상이 아니라면 반으로 줄입니다.
last = mid - 1; // 왜 mid에서 1을 뺄까요?
} else {
first = mid + 1; // 왜 mid에서 1을 더할까요?
}
}
return -1;
}
public static void printSearchInfo(int idx) {
String info = "탐색 실패";
if (idx != -1) {
info = "타겟 저장 인덱스: " + idx;
}
System.out.println(info);
}
}결과
타겟 저장 인덱스: 3
탐색 실패
중요한 부분은 책에서 나와있듯이 그림으로 이해하면 좀 더 쉽다는 점입니다.
왜 while loop를 first <= last로 지정해주었을까요? first와 last가 같을 때가 존재하는 경우는 어떤 때일까요? 한 번 그림으로 그려서 생각해보세요. 저는 쉽게 잘 안떠올랐는데 여러분은 어떤지 궁금합니다. n개의 원소가 있을 때 맨 앞에 있는 원소를 검색한다고 생각해보면 되겠습니다.
왜 mid에서 1을 빼고 1을 더하는지도 저는 그냥 탐색을 하지 않기 위해서라고 생각했는데, 설명이 잘 되어있어서 책의 설명을 읽는 것을 추천드려요.
BigO 표기법에서 가장 중요한 부분을 제외한 나머지 상수항같은 것들은 생략이 가능함도 알고 있어야 합니다.
$T(n)$ 이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다.
대표적인 빅 오 부분은 한 번 쭉 읽어보고 어떤것들이 있는지 알아보는 것도 좋을 듯 합니다.
수학적 판별법은 해야되는지 조금 고민이 되네요.
간추리자면 빅오 표기법은 연산횟수 증가율의 상한선을 표현한 것이라고 생각하면 좋을 듯 합니다.
재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소입니다. 재귀를 적용하는 방법에 대해서 알아봅시다.
재귀함수란 함수 내에서 자기 자신을 호출하는 함수입니다. 메소드가 메소드 콜 스택에 쌓이는 것은 다들 알고 있으시리라고 생각합니다.
설명을 보고 이해할 수 있으셨으리라 생각됩니다.
여기서 중요한 점은, 재귀함수에는 필수적으로 탈출조건이 있어야한다는 점임을 명심하세요.
RecursiveFunc.java
public class RecursiveFunc {
public static void main(String[] args) {
recursive(3);
}
public static void recursive(int num) {
if (num <= 0) { // 재귀의 탈출조건
return;
}
System.out.println("재귀 호출! " + num);
recursive(num - 1);
}
}결과
재귀 호출! 3
재귀 호출! 2
재귀 호출! 1
보통 재귀함수를 떠올리면 팩토리얼을 많이 떠올리게 됩니다. 한 번도 팩토리얼 재귀함수를 만들어 본 적이 없다면, 만들어 보시고, 더 도전과제가 필요하다면, 성능개선을 어떻게 할 수 있을지 생각해보세요.
그리고 이런 팩토리얼 말고도 재귀함수를 적용할 수 있는 사례가 많습니다. 저도 재귀함수에 대해선 아직 많이 부족하지만 퀵 소트, 머지 소트에서 쓰이는 방식이니 언젠간 공부하게 되실거에요.
RecursiveFactorial.java
public class RecursiveFactorial {
public static void main(String[] args) {
System.out.println("1! = " + factorial(1));
System.out.println("2! = " + factorial(2));
System.out.println("3! = " + factorial(3));
System.out.println("4! = " + factorial(4));
System.out.println("9! = " + factorial(9));
}
public static int factorial(int num) { // 숫자가 조금만 커져도 문제될 수 있음
if (num == 0) {
return 1;
}
return num * factorial(num - 1);
}
}결과
1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880
재귀 함수는 정의할 줄 알아야합니다. 근데, 어렵습니다. 보통 수학의 점화식을 많이 떠올리라고 하던데, 저는 수학을 못하고, 특히 증명문제를 싫어해서 잘 못해요. (일정한 패턴을 찾아서 재귀적으로 풀어야합니다.)
보통 0부터 n번째까지 순차적으로 더하는 것을 의미합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 를 보면서 아 증가하네가 아니라, 어떤 규칙으로 증가하네를 파악할 줄 알아야합니다. 어려워요.
즉, 수식을 메소드로 옮기는 과정을 거치는데 여기서 많이 헷갈립니다. 특히 정렬 코드 구현할 때 많이 헷갈리실거에요.
FibonacciFunc.java
public class FibonacciFunc {
public static void main(String[] args) {
for (int i = 1; i < 15; i++) {
System.out.printf("%d ", fibo(i));
}
}
public static int fibo(int num) {
if (num == 1) {
return 0;
}
if (num == 2) {
return 1;
}
return fibo(num - 1) + fibo(num - 2);
}
}결과
0 1 1 2 3 5 8 13 21 34 55 89 144 233
함수호출이 굉장히 많아지는데, 이는 어떻게 해결하면 좋을까요?
RecursiveBinarySearch.java
public class RecursiveBinarySearch {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int idx = bSearch(arr, 0, arr.length - 1, 7);
if (idx != -1) {
System.out.println("타겟 저장 인덱스: " + idx);
} else {
System.out.println("탐색 실패");
}
idx = bSearch(arr, 0, arr.length - 1, 4);
if (idx != -1) {
System.out.println("타겟 저장 인덱스: " + idx);
} else {
System.out.println("탐색 실패");
}
}
public static int bSearch(int[] arr, int first, int last, int target) {
if (first > last) {
return -1;
}
int mid = (first + last) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] > target) {
return bSearch(arr, first, mid - 1, target);
}
return bSearch(arr, mid + 1, last, target);
}
}결과
타겟 저장 인덱스: 3
탐색 실패
재귀 함수의 탈출조건이 총 두 가지 경우가 있음을 알 수 있습니다. 첫번째는 못찾는 경우, 두번쨰는 찾는 경우.
그마저도 아니라면 재귀에 빠지게 됩니다.
줄이는 방법은 찾는 값보다 작다면 last의 위치를, 크다면 first의 위치를 조정하는 방식을 재귀적으로 표현하면 됩니다.
재귀에 좀 익숙해지니 저는 큰 무리 없이 구현을 할 수 있었습니다.
재귀함수를 설명할 때, 대표적인 예가 하노이 타워입니다.
전에 한 번 풀어보려고 했는데, 전 어려웠네요. 지금은 어떨지 잘 모르겠습니다.
이 문제에 접근하는 방법은 반복되는 과정을 파악하는데에 있습니다.
원판이 계속 추가되더라도, 해야하는 행동은 똑같습니다.
A에 위치한 원반 4개를 C로 이동할 때 필요한 것은, 작은 원반 3개를 B위치에 옮기고, 제일 큰 원반을 C위치에 옮긴 다음 B에 위치한 원반 3개를 C위치로 옮기는 것입니다.
즉, 원반을 옮기는 과정 자체가 n - 1 문제가 되기 때문에, 재귀로 해결이 가능합니다.
- 작은 원반 n-1개를 A에서 B로 이동합니다.
- 큰 원반을 A에서 C로 이동합니다.
- 작은 원반 n-1개를 B에서 C로 이동합니다.
여기서 주의할 점은 A에서 B로 이동하고 A에서 C로 이동하는 것이 교차되어 일어난다는 것입니다.
HanoiTowerSolution.java
public class HanoiTowerSolution {
public static void main(String[] args) {
HanoiTowerMove(3, 'A', 'B', 'C');
}
public static void HanoiTowerMove(int num, char from, char by, char to) {
if (num == 1) {
System.out.printf("원반1을 %c에서 %c로 이동 %n", from, to); // 재귀의 탈출조건
} else {
HanoiTowerMove(num - 1, from, to, by); // 1단계: 작은 원반 n-1개를 from에서 by로 이동
System.out.printf("원반%d을(를) %c에서 %c로 이동 %n", num, from, to); // 2단계: 큰 원반 이동
HanoiTowerMove(num - 1, by, from, to); // 3단계: by에 있던 작은 원반 n-1개를 from을 거쳐 to로 이동
}
}
}결과
원반1을 A에서 C로 이동
원반2을(를) A에서 B로 이동
원반1을 C에서 B로 이동
원반3을(를) A에서 C로 이동
원반1을 B에서 A로 이동
원반2을(를) B에서 C로 이동
원반1을 A에서 C로 이동
디버깅 도구를 이용해서 확인을해도 좋을 것 같습니다!!