자료구조란
자료구조란, 자료를 효율적으로 관리하는 방법이다. 즉, 자료에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 관한 이론이 자료구조이다.
자료구조를 구현, 사용, 활용하는 과정에서 수학적 사고도 크게 도움이 된다. 수열, 수학적 귀납법 등을 포함하는 이산 수학이 자료구조에 사용된다.
대표적인 자료구조는 다음과 같다.
그리고 자바의 컬랙션 패키지는 다음과 같다.
이 패키지에서 다양한 자료구조를 손쉽게 가져다 쓸 수 있기 때문에 보다 쉽게 작업을 수행할 수 있다.
자료구조와 알고리즘
알고리즘이란, 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것을 알고리즘이라고 한다. 자동차를 만들어내는 과정을 자료구조와 알고리즘을 비유해 설명한다면, 자동차 부품을 자료구조, 자동차 부품을 가지고 자동차를 조립해내는 과정에는 자료구조와 알고리즘이 활용되고, 조립된 자동차를 프로그램이라고 할 수 있다.
자료구조의 추상 데이터 타입
'추상'이란 단어는 예술 계통에서는 주로 '애매한', '난해한'이라는 의미로 사용되지만, 프로그래밍에서 추상이란 조금 다른 의미로 받아들여진다. 프로그래밍에서 추상이란 하위의 개념들을 결합하여 상위의 고급 개념을 만들어나가는 지적 발전의 단계이다. 객체 지향 언어의 클래스가 대표적인 예시라고 할 수 있다.
추상 데이터 타입을 ADT, Abstract Data Type이라고 하는데, ADT를 활용하면 프로그래밍 작업을 보다 효율적이고 고급스럽게 할 수 있다. 자료구조 내부의 너무 세세한 사항까지 신경을 쓰지 않아도 되고, 여러 가지 협업도 원활해진다. 즉, 내부 상황이 '어떻게' 진행되는지보다는 '무엇을' 어떻게 할 수 있는지에만 신경 쓰게 할 수 있다.
이 그림은 자바에서 ADT에 가까운 기능인 Interface를 사용하는 방법을 보여준다. ListInterface란 이름의 인터페이스를 따르는 클래스는 (b)에 나열된 3개의 작업을 수행하게 되는데, (c)에서와 같이 implements를 활용해 이 인터페이스를 따르는 클래스를 정의할 수 있다. 그럼 사용자 프로그램에서는 (d)와 같이 객체만 할당받아서 타입에만 맞게 함수를 사용하게 되는데, 이 과정은 '추상적 수준'에서 자료를 취급할 수 있게 해주는걸 보여준다.
알고리즘의 수행시간
알고리즘의 효율성은 '자원을 얼마나 효율적으로 사용하는가'에서 판단한다. 프로그래밍에서 대표적인 자원은 '시간'이다. 보통의 알고리즘에서 효율성을 말할 때, 대부분은 시간에 관한 것이다.
알고리즘의 수행 시간은 입력의 크기에 대해 시간이 얼마나 걸리는지로 표현한다. 입력의 크기란, 정렬의 경우에는 정렬하고자 하는 원소의 수, 최단 거리라고 한다면 노드의 수와 간선의 수, 팩토리얼을 구하자고 한다면 자연수의 크기가 입력의 크기가 된다.
예를 들면 다음과 같다.
Sample2(A[], n):
sum <- 0
for i <- 0 to n-1
sum <- sum + A[i]
return sum이 코드에서는 for 루프가 이 알고리즘의 수행시간을 결정한다. for 루프가 n번 반복되므로 수행 시간은 n에 비례한다. 만약 for문이 중첩되있는 경우에는 알고리즘의 수행시간은 n^2에 비례한다.
알고리즘의 시간 복잡도를 분석할 때는 다음과 같이 수행 시간을 지배하는 부분이 어디인지 파악하는 것이 중요하다. for루프의 회전 횟수, 특정 라인의 수행 횟수, 함수의 호출 횟수 등이 이에 해당한다.
알고리즘 복잡도의 표기
알고리즘의 복잡도는 '점근적 표기'를 활용하여 나타낸다. 이러한 점근적 복잡도 분석에서는 '최고차항의 차수'만 중요하고, 계수와 같은 나머지 것들은 다 무시한다. n이 충분히 크다면 그 앞에 곱해지는 상수는 차수의 차이에 비하면 굉장히 미미하기 때문이다. 그래서 보통 시간복잡도는 n, n^2, nlogn 등으로 표현한다.
점근적 복잡도에는 다음과 같이 다음 세 개의 표기가 대표적이다.
- O- 표기 : 점근적 상한 ; 최악일 때(worst case)의 연산횟수
O(n^2)은 최고차항의 차수가 n^2을 넘지 않는 모든 함수의 집합을 뜻한다. 즉, 이 프로그램이 실행될 때 최악의 경우를 'O-'로 표기한다. - Ω- 표기 : 점근적 하한 ; 최선알 때(best case)의 연산횟수
Ω-은 앞의 O-와 정반대이다. 프로그램이 실행될 때 최선의 경우, 예를 들면 첫 번째 루프에서 원하는 수를 뽑아내는 것과 같은, 가장 좋은 경우를 이와 같이 표기한다. - θ- 표기 : 점근적 동일 ; 보통일 때(average case)의 연산횟수
이 표기는 앞서 말한 두 표기의 교집합이다. 보통일 때, 즉 프로그램이 실행될 때 평균적인 연산 횟수를 나타내는 표기법이다.
이 세 가지 표기를 차수를 n^2으로 예시를 들어 시각적으로 정리하면 다음과 같다.
클래스
클래스는 자바에서 굉장히 중요한 용어 중 하나이다. 클래스는 보통 필드, 생성자, 메소드로 구성되며, 메소드는 클래스 안에서 정의되는 함수를 말한다. 생성자는 클래스 이름과 동일한 메소드를 뜻하며, 객체가 만들어질 때 자동으로 수행되어 객체를 초기화해주는 역할을 수행한다. 또한, public이나 private과 같은 접근 제어자로 메소드의 공개 범위 또한 조절할 수 있다.
JAVA 기초 문법
자바에서 기본적으로 제공하는 8개의 기초타입(primitive type)에는 byte, short, int, long, float, double, char, boolean 등이 있다.
이 8가지 기초 타입은 클래스가 아니어서 이 기초 타입들을 객체로 만들어주는 클래스가 있는데, 이를 래퍼 클래스(Wrapper Class)라고 한다. 이름은 각 타입의 첫 글자를 대문자로 바꾸어 표기한다.
- 상속
자바에는 부모의 특성을 상속 받는 기능이 있다. 상속은 상위 개념의 특성을 '덮어 쓴다'는 의미에서 'Overriding'이라고 표현하기도 한다. 예약어로는 'extends'를 쓰고, 주로 한 클래스에서 다른 부모 클래스를 상속받는다.
Public class InheritedStack extends LinkedList {
public InheritedStack() {
super();
}이 과정에서 'super'로 상위 클래스를 지칭할 수 있다.
- 인터페이스(Interface)
자바에서 클래스를 추상적으로 묘사하는 대표적인 수단 두 가지에 'interface'와 'abstract'가 있다. abstract는 주로 클래스와 메소드를 선언할 때 접두어로 쓰여서 뼈대만 완성해놓고 다른 클래스가 해당 클래스를 상속받아 완성되어 쓰일 때 주로 활용된다. 반면에 interface는 전체를 추상적으로 묘사하는 방식이다. 인터페이스의 경우 둘 이상의 인터페이스를 따를 수 있다.
예를 들면 다음과 같다.public interface A { " " " }public class BST implements A, B { }
-
객체끼리 비교하는 필드, Comparable 인터페이스 타입
예를 들어, a와 b라는 클래스의 객체가 있고, 클래스 내부에 메소드 compareTo()가 정의되어 있다면, if (a.compareTo(b) < 0 ) 라는 코드는 if(a<b)를 수행하는 효과를 낸다.
제네릭
제네릭, generic을 직역하면 '일반적인' 이라는 뜻이다. 제네릭이란, 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있게 하는 방법이다.
즉, 어떤 자료구조를 만들어 배포하고자 할 때, String, Integer 등 여러 타입을 지원하는 자료구조를 만들고자 할 때, 제네릭을 활용하면 굳이 각 타입별로 하나하나 자료구조를 만들 필요 없이 타입을 필요에 의해 지정해 줄 수 있게 해준다.
다음과 같은 타입이 제네릭에 주로 많이 쓰인다.
제네릭 클래스의 활용 예시는 다음과 같다.
여기서 a 객체의 E 제네릭 타입은 String으로 다 변환되고, b 객체의 E 제네릭 타입은 다 Integer으로 다 변환된다.
패키지
클래스와 인터페이스들을 모아놓은 것을 패키지라고 한다. 이러한 패키지들을 모아놓은 것이 프로젝트이다. 자바가 제공하는 대표적인 패키지인 java.lang에는 다음과 같은 클래스들이 포함되어 있다.
- Object 클래스
- String 클래스
- Wrapper 클래스
- Stream 클래스
자바 개발 환경과 디버거
IDE(Integrated Development Enviroment)는 통합 개발 환경이라는 뜻으로, GUI를 갖춘 자바의 작업장 또는 작업대이다. 대표적인 환경에는 Eclipse와 IntelliJ가 있다.
디버거는 디버깅을 굉장히 편리하게 해준다. 보통의 개발 환경에는 편리한 프로그래밍을 위한 디버거가 장착되어 있으며, 이는 에러를 빠르게 해결할 수 있도록 해준다.
이미지 출처: https://st-lab.tistory.com/153
& [쉽게 배우는 자료구조 with 자바] - 문병로
