[JAVA] 자료구조와 알고리즘

컴퓨터 프로그래밍

컴퓨터가 작업을 수행하도록 하는 과정은 프로그램을 작성하는 것에서 시작됩니다. 이러한 프로그램을 만드는 과정을 프로그래밍 또는 코딩이라고 부릅니다.

---

프로그램의 구성 요소

프로그램은 크게 두 가지로 나뉩니다:

• 구조화된 데이터 → 자료구조
• 논리적 절차 → 알고리즘

이 둘을 조합하여 프로그램을 만든다고 볼 수 있으며, 이를 **"자료구조 + 알고리즘 = 프로그램"**으로 표현할 수 있습니다.

컴퓨터가 효율적으로 작업을 수행하기 위해서는 좋은 프로그램이 필요하며, 이를 위해 자료구조와 알고리즘을 깊이 이해하는 것이 중요합니다.

---

자료구조

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법입니다. 특히, 대량의 데이터를 어떻게 구성할 것인가에 초점이 맞춰져 있습니다.

데이터 구성 방식

1. 선형 자료구조: 데이터를 순서대로 나열
   예) 배열, 연결 리스트, 스택, 큐
2. 비선형 자료구조: 데이터를 연관성 있는 구조로 묶음
   예) 트리, 그래프

CRUD 작업

자료구조는 보통 데이터에 대해 다음과 같은 4가지 작업을 수행할 수 있어야 합니다:

• Create: 데이터를 새롭게 추가
• Read: 데이터를 읽어옴
• Update: 데이터를 수정
• Delete: 데이터를 삭제

---

알고리즘

알고리즘은 데이터를 다루는 절차적 방법입니다.
주요 알고리즘의 활용 분야:

• 데이터의 검색 (예: 이진 탐색)
• 데이터의 정렬 (예: 퀵 정렬, 병합 정렬)
• 데이터의 순서 바꾸기 (예: 버블 정렬)

알고리즘의 평가 기준

1. 정확성: 정확히 원하는 결과를 도출할 수 있는가?
2. 작업량 (시간복잡도): 얼마나 적은 연산으로 작업을 수행하는가?
3. 메모리 사용량 (공간복잡도): 얼마나 적은 메모리를 사용하는가?
4. 단순성: 얼마나 이해하기 쉬운가?
5. 최적성: 더 이상 개선할 여지가 없을 만큼 최적화되었는가?

시간복잡도

알고리즘의 작업량을 표현하는 방식으로, 입력 크기 nnn에 따른 실행 시간의 증가를 나타냅니다. 대표적인 Big-O 표현식:

• O(1)O(1)O(1): 상수 시간
• O(log⁡n)O(\log n)O(logn): 로그 시간
• O(n)O(n)O(n): 선형 시간
• O(n2)O(n^2)O(n2): 이차 시간

---

Mutable / Immutable

 

• Mutable: 값을 변경할 수 있음 (예: List, Map 등)
• Immutable: 값을 변경할 수 없음 (예: String, Integer 등)

 

final이 붙은 primitive 값은 변경될 수 없으니 immutable 값이 됩니다. 하지만 final이 붙은 참조(reference) 변수의 경우 변경되지 못하기는 하지만 변경되지 못하는 값은 변수가 담고 있는 참조 주소값이 됩니다. 즉, 참조 변수가 가리키는 인스턴스를 변경할 수는 없다는 뜻입 니다. 그렇다고 그것이 변수가 가리키는 인스턴스의 내용을 변경할 수 없다는 것을 의미하지 는 않습니다

Immutable Reference

string literal로 생성되는 String 객체의 경우 immutable값입니다. 따라서 String의 내용이 변경되는 경우 새로운 인스턴스가 생성되게 됩니다. 그리고 같은 내용의 문자열일 경우에는 기존에 생성되었던 인스턴스를 재사용합니다.

String str1 = "Hello";
String str2 = str1 + " World"; // 새로운 인스턴스가 만들어지고 str2가 참조하게 됨
System.out.println(str1 == str2); // false

String str3 = "Hello";
System.out.println(str1 == str3); // true

---

Integer 캐싱 메커니즘

Java는 성능 최적화를 위해 -128에서 127 사이의 Integer 값을 캐싱합니다.
이 범위 내의 값은 같은 객체를 재사용하지만, 범위를 벗어나는 값은 새로운 객체를 생성합니다.

Integer i1 = 42;
Integer i2 = 42;
System.out.println(i1 == i2); // true

Integer i3 = 100000;
Integer i4 = 100000;
System.out.println(i3 == i4); // false

Integer i3 = 100000;
Integer i4 = 100000;
System.out.println(i3.equals(i4)); // true

※ 자바에서 값을 비교하고 싶다면 .equls()를 사용하자!

참고

객체의 참조 주소를 확인하려면 System.identityHashCode()를 사용할 수 있습니다.