배열/문자열의 기본 구조와 인덱스 접근 방식 이해
배열의 기본 구조
정의
배열은 같은 자료형의 데이터 여러 개를 하나의 변수 이름으로 관리할 수 있는 구조이다. 메모리 상에 연속된 공간으로 저장되며, 각 요소는 인덱스(index)로 구분된다.
선언과 초기화
int[] numbers = new int[5];
// 크기가 5인 int 배열
int[] scores = {90, 85, 100, 70};
// 선언과 동시에 초기화를 하는 배열인덱스 접근
배열의 인덱스는 0부터 시작해서 최대 길이 -1 까지 접근이 가능하다. 배열의 최대 길이는 .length로 확인할 수 있다.
System.out.println(scores[0]);
// 90
System.out.println(scores[2]);
// 100
System.out.println(scores.lenght);
// 4
문자열(String)의 기본 구조
정의
문자열은 문자(char)들의 배열처럼 동작하는 객체형 데이터이다. 한번 생성된 문자열은 불변(immutable)하다.
String text = "Hello!";인덱스 접근
문자열의 각 문자는 charAt()으로 접근한다.
System.out.println(text.charAt(0));
// 'H'
System.out.println(text.charAt(4));
// 'o'
System.out.println(text.length());
// 5문자열도 인덱스는 0부터 시작하며, charAt(문자열길이)를 초과하면 StringIndexOutOfBoundsException이 발생한다.
배열과 문자열의 공통점과 차이점
| 구분 | 배열(array) | 문자열(String) |
| 자료형 | 기본형 또는 참조형 가능 | char의 연속(문자열 객체) |
| 길이 확인 | .length | .length() |
| 인덱스 시작 | 0 | 0 |
| 변경 가능 여부 | 변경 가능(값 수정 가능) | 불변(새 문자열로 교체) |
시간 복잡도 기반의 탐색 및 정렬
시간 복잡도(Time Complexity)
시간 복잡도는 "알고리즘이 실행되는데 걸리는 시간"을 입력 크기(n)에 따라 수학적으로 표현한 것을 의미한다.
예를 들어 입력이 10개일 때 1초 걸리는 알고리즘이 입력이 100개면 10초, 1000개면 100초가 걸린다면 이는 O(n) 이라고 표현한다.
자주 나오는 시간 복잡도 종류
| 표기 | 이름 | 설명 | 예시 |
| O(1) | 상수 시간 | 입력 크기와 상관 없이 즉시 수행 | 배열의 인덱스로 접근 |
| O(log n) | 로그 시간 | 입력이 2배로 늘어도 몇 번만 증가 | 이진 탐색 |
| O(n) | 선형 시간 | 입력 수에 비례 | 순차 탐색 |
| O(n log n) | 로그 선형 시간 | 정렬 알고리즘의 대표적 형태 | 병합 정렬, 퀵 정렬 |
| O(n²) | 제곱 시간 | 중첩 반복문 | 버블 정렬, 선택 정렬 |
| O(2ⁿ) | 지수 시간 | 입력이 조금만 늘어도 폭발적 증가 | 재귀적 조합 탐색(예: 모든 부분집합 탐색) |
탐색(Search) 알고리즘과 시간 복잡도
| 탐색 방법 | 설명 | 시간 복잡도 |
| 순차 탐색(Linear Search) | 배열의 처음부터 끝까지 하나씩 비교 | O(n) |
| 이진 탐색(Binary Search) | 정렬된 배열에서 중간값을 기준으로 절반씩 탐색 | O(log n) |
순차 탐색(Linear Search)
int[] arr = {5, 2, 9, 1, 7};
int target = 9;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
System.out.println("찾았다! 인덱스: " + i);
}
}시간 복잡도 -> O(n)
최악의 경우 배열 끝까지 탐색해야 한다는 단점이 존재한다.
이진 탐색(Binary Search)
이진 탐색을 하는 경우 무조건 배열은 정렬된 상태에서 진행해야 한다.
int[] arr = {1, 3, 5, 7, 9, 11, 13};
int target = 9;
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
System.out.println("찾았다! 인덱스: " + mid);
break;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}시간 복잡도 -> O(log n)
탐색을 진행할 때마다 범위가 절반으로 줄어들어가는 모습을 확인할 수 있다.
정렬(Sorting) 알고리즘과 시간 복잡도
| 정렬 알고리즘 | 평균 시간 복잡도 | 특징 |
| 버블 정렬(Bubble Sort) | O(n²) | 인접한 두 원소를 비교, 교환 |
| 선택 정렬(Selection Sort) | O(n²) | 가장 작은 값을 선택해서 앞으로 이동 |
| 삽입 정렬(Insertion Sort) | O(n²) | 이미 정렬된 부분에 삽입 |
| 퀵 정렬(Quick Sort) | O(n log n) | 분할 정복 방식, 평균적으로 가장 빠름 |
| 병합 정렬(Merge Sort) | O(n log n) | 반씩 나누고 합치면서 정렬 |
| 힙 정렬(Heap Sort) | O(n log n) | 완전 이진트리(힙) 구조 이용 |
| 계수 정렬(Counting Sort) | O(n + k) | 데이터 범위가 좁을 때 매우 빠름 |
버블 정렬(Bubble Sort) - 가장 기본적인 정렬 방식
int[] arr = {5, 2, 9, 1, 7};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j+) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
// [1, 2, 5, 7, 9]시간 복잡도 -> O(n²)
퀵 정렬(Quick Sort)
void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[(left + right) / 2];
int index = partition(arr, left, right, pivot);
quickSort(arr, left, index - 1);
quickSort(arr, index, right);
}
int partition(int[] arr, int left, int right, int pivot) {
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
return left;
}시간 복잡도 -> 평균 O(n log n), 최악 O(n²) - 피벗 선택이 나쁠 때
정렬 정리
| 구분 | 알고리즘 | 시간 복잡도 | 비고 |
| 탐색 | 순차 탐색 | O(n) | 정렬 불필요 |
| 탐색 | 이진 탐색 | O(log n) | 정렬 필요 |
| 정렬 | 버블/선택/삽입 | O(n²) | 단순하지만 느림 |
| 정렬 | 퀵/병합/힙 | O(n log n) | 효율적, 대규모 데이터에 적합 |
-----------------------추가-----------------------
https://school.programmers.co.kr/learn/courses/30/lessons/42748?language=java
프로그래머스 정렬 관련 알고리즘을 풀던 중 위에 작성한 정렬 알고리즘을 여러가지 사용하여 돌리던 중 가장 빠른 알고리즘을 찾기 위해 위에 작성한 모든 정렬 알고리즘과 자바에서 기본으로 제공하는 Arrays.sort()를 비교해보았다.
정렬 알고리즘은 총 7개(버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 계수 정렬)를 사용하였고, 자바의 기본 제공 sort도 사용하였다. 랜덤으로 문제에 맞는 데이터를 만들어주는 함수를 만들어서 500만번 정도의 테스트를 돌려보았을 때 순위는 다음과 같았다.
내가 직접 작성한 알고리즘 중에서는 삽입 정렬이 가장 빨랐고, 가장 빨랐던 알고리즘은 크게 차이나지는 않았지만 역시 기본 sort() 메서드였다. 나중에 찾아보니 java 에서도 sort() 메서드는 윈시타입일 경우 DualPivotQuickSort와 삽입정렬을 사용하고 있었고, 객체 타입의 경우 TimSort를 사용하고 있었다. 처음에는 DualPivotQuickSort가 가장 빠른줄 알았는데 자바에서는 단일 알고리즘을 사용하는 것이 아니라 상황에 따른 알고리즘을 사용하는 하이브리드 구조이었다.
상황마다 사용하는 알고리즘은 다르겠지만 이번 문제에서의 정렬은 삽입 정렬이 가장 빠른 알고리즘이었다는 것을 확인할 수 있었다. 그러니 무조건 시간복잡도가 빠른 알고리즘을 사용하는 것이 아닌 상황에 따라 가장 빠른 알고리즘을 선택해야 한다는 것을 알 수 있었다.(근데 자바의 기본 메서드를 쓰는게 가장 효율적일거 같다는 생각은 하고있다..)
투 포인터, 슬라이딩 윈도우 개념 학습
투포인터(Two Pointers)
두 개의 인덱스(Pointer)를 사용해서 배열이나 리스트를 효율적으로 탐색하는 방법이다. 보통 정렬된 배열에서 특정 조건 (예: 합이 일정한 두 수 찾기)을 빠르게 찾을 때 사용한다.
기본 개념
하나의 배열에서 왼쪽 포인터(left)는 시작 인덱스, 오른쪽 포인터(right)는 끝 인덱스로 두고 조건에 따라 두 포인터를 이동시키면서 원하는 값을 찾는다.
예시: 정렬된 배열에서 "합이 target인 두 수" 찾기
int[] arr = {1, 2, 3, 5, 7, 10};
int target = 9;
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
System.out.println(arr[left] + " + " + arr[right] + " = " + target);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}동작 과정
| left | right | arr[left] | arr[right] | sum | 동작 |
| 0 | 5 | 1 | 10 | 11 | sum > target -> right-- |
| 0 | 4 | 1 | 7 | 8 | sum < target -> left++ |
| 1 | 4 | 2 | 7 | 9 | 찾음 |
시간 복잡도 -> O(n)
모든 조합을 비교하면 O(n²)이지만, 포인터 2개를 사용해 효율적으로 줄임
슬라이딩 윈도우(Sliding Window)
연속된 구간(subarray)을 효율적으로 탐색하는 방법이다. 일정 크기의 창(window)을 옮겨가며 검사한다.
보통 부분합, 최대/최소 구간 값, 고정 길이의 부분 배열 등을 찾을 때 사용한다.
핵심 로직
1. 배열의 일부 구간을 윈도우(window)로 본다.
2. 윈도우를 한 칸씩 오른쪽으로 미끄러지듯(slide)이동시킨다.
3. 이전 결과를 재활용하여 불필요한 연산을 줄인다.
예시: 배열에서 길이 k인 구간의 최대 합 찾기
int[] arr = {2, 1, 5, 1, 3, 2};
int k = 3;
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
for (int i = k; i < arr.lenght; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
System.out.println(maxSum);동작 과정
| 윈도우 구간 | 합 | 비교 |
| [2, 1, 5] | 8 | 초기값 |
| [1, 5, 1] | 7 | ↓ |
| [5, 1, 3] | 9 | 최대값 |
| [1, 3, 2] | 6 | ↓ |
시간 복잡도 -> O(n)
모든 윈도우 합을 처음부터 다시 계산했다면 O(n × k)
문자열 처리 관련 주요 메서드(Java)
문자열 기본 정보
String str = "Hello World";| 메서드 | 설명 | 예시 결과 |
| length() | 문자열 길이 반환 | str.lenght() -> 11 |
| charAt(int index) | 특정 인덱스 문자 반환 | str.charAt(0) -> 'H' |
| indexOf(String s) | 문자열 s가 처음으로 등장하는 위치 | str.indexOf("o") -> 4 |
| lastIndexOf(String s) | 문자열 s가 마지막으로 등장하는 위치 | str.lastIndexOf("o") -> 7 |
| isEmpty() | 문자열이 비어있는지 확인 | "".isEmpty() -> true |
문자열 비교 관련
| 메서드 | 설명 | 예시 결과 |
| equals(String s) | 내용이 같은지 비교(대소문자 구분) | "Java".equals("java") -> false |
| equalsIgnoreCase(String s) | 대소문자 구분 없이 비교 | "Java".equalsIgnoreCase("java") -> true |
| compareTo(String s) | 사전 순 비교(양수/0/음수 반환) | "abc".compareTo("abd) -> -1 |
문자열 조작(변경) 관련
| 메서드 | 설명 | 예시 결과 |
| toUpperCase() | 모두 대문자로 | "hello".toUpperCase() -> "HELLO" |
| toLowerCase() | 모두 소문자로 | "HELLO".toLowerCase() -> "hello" |
| trim() | 앞뒤 공백 제거 | " hi ".trim() -> "hi" |
| replace(String a, String b) | a를 b로 모두 변경 | "java".replace("a", "@") -> "j@v@" |
| subString(int begin, int end) | begin ~ end-1 범위의 문자열 추출 | "abcdef".substring(2, 5) -> "cde" |
문자열 검색 및 확인
| 메서드 | 설명 | 예시 결과 |
| contains(CharSequence s) | 포함 여부 확인 | "hello".contains("ell") -> true |
| startsWith(String s) | 특정 문자열로 시작하는지 | "hello".startsWith("he") -> true |
| endsWith(String s) | 특정 문자열로 끝나는지 | "hello".endsWith("lo") -> true |
| matches(String regex) | 정규식(regex)으로 일치 여부 확인 | "abc123".matches("[a-z]+\\b+") -> true |
문자열 분리 및 결합
| 메서드 | 설명 | 예시 결과 |
| split(String regex) | 구분자 기준으로 나누기 | "a,b,c".split(",") -> ["a", "b", "c"] |
| join(CharSequence delimiter, CharSequence... elements) | 구분자로 합치기 | String.join("-". "a", "b", "c") -> "a-b-c" |
| concat(String s) | 문자열 뒤에 추가 | "Hello".concat("World") -> "HelloWord" |
문자열 -> 숫자 / 문자 변환
| 메서드 | 설명 | 예시 |
| Integer.parseInt(String s) | 문자열을 정수로 변환 | Integer.parsInt("123") -> 123 |
| Double.parseDouble(String s) | 문자열을 실수로 변환 | Double.parseDouble("3.14") -> 3.14 |
| String.valueOf(int number) | 정수를 문자열로 변환 | String.valueOf(123) -> "123" |
| new String(charArray) | 문자 배열을 문자열로 변환 | new String(['a', 'b', 'c']) -> "abc" |
문자열 빌더(StringBuilder / StringBuffer)
문자열을 반복 연결할 때, '+' 연산 대신 StringBuilder를 사용하면 효율적이다. (String은 불변 객체라 매번 새로운 객체가 만들어진다.)
StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(" ");
sb.append("World");
System.out.println(sb.toString());
// "Hello World"| 클래스 | 특징 |
| StringBuilder | 단일 스레드용, 빠름 |
| StringBuffer | 멀티 스레드용, 동기화(synchronized) 지원 |