안녕하세요 jju_developer입니다.
2024년 8월부터 알고리즘 관련 포스팅을 시작하려고 합니다!
백엔드 개발의 꽃, 바로 알고리즘입니다!🌷🌼🌻
이제부터 꾸준히 알고리즘 관련 공부 내용을 포스팅하고자 합니다.
그렇다면 제가 알고리즘을 배우려는 이유는 무엇일까요?
1년차 백엔드 개발자로서, 지난 경험을 돌아보면,
- 기초적인 Spring MVC 패턴으로 개발하는 부분에 중점
- 모델에 데이터를 담아 프론트로 넘겨주는 작업
- 간단한 페이지 UI 제작 등의 업무
1년 동안 반복하다 보니, 이제는 페이지 로딩 시간을 줄일 수 있는 방법이나, 비동기적으로 개발하는 방법, 스레드 관련 여러 궁금증이 생기기 시작했습니다.
그래서 이제부터 알고리즘을 공부하여, 개발할 때 더욱 효율적이고 도움이 되는 방향으로 성장하고자 합니다.
❔ 정렬? 자료구조? 시간 복잡도란?
✅정렬: 정렬은 어떠한 데이터를 순서대로 정리하는 것과 비슷합니다. 예를 들어, 도서관에서 책을 정해진 순서대로 정리하는 것처럼요. 자바 백엔드에서는 숫자나 문자열 리스트를 오름차순 또는 내림차순으로 정렬할 수 있습니다. 예를 들어, 데이터베이스에서 사용자 목록을 이름 순서대로 정렬해서 가져오는 작업을 할 때 정렬을 사용합니다.
List<String> latters = Arrays.asList("jju", "blog", "welcome");
Collections.sort(latters);
System.out.println(latters); // [blog, jju, welcome]
✅ 자료구조: 자료구조는 데이터를 효과적으로 저장하고 관리하는 방법입니다. 예를 들어, 자바 백엔드에서는 데이터를 연필꽂이, 책장, 옷장처럼 특정한 자료구조에 넣어서 관리합니다.
배열, 리스트, 해시맵 등이 있으며, 각 자료구조는 특정 상황에서 데이터를 빠르게 검색하거나 저장하는 데 도움을 줍니다.
// 해시맵을 사용하여 데이터 저장
Map<String, String> bookMap = new HashMap<>();
bookMap.put("jjuBook1", "Java Programming");
bookMap.put("jjuBook2", "Spring Boot");
bookMap.put("jjuBook3", "Algorithms");
// 저장된 데이터 출력
for (Map.Entry<String, String> entry : bookMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}이 코드는 자바에서 해시맵(HashMap)이라는 자료구조를 사용하여 책 정보를 저장하는 예시입니다.
키와 값:
키(Key): 책을 찾기 위한 고유한 번호입니다. 여기서 jjuBook1, jjuBook2, jjuBook3이 키입니다.
값(Value): 각 키에 연결된 데이터입니다. Java Programming, Spring Boot, Algorithms이 값입니다.
✅ 시간 복잡도: 시간 복잡도는 특정 작업을 수행할 때 얼마나 시간이 걸리는지를 나타냅니다.
자바 백엔드에서는 데이터베이스에서 데이터를 검색하거나,
리스트에서 특정 요소를 찾을 때 걸리는 시간을 고려합니다.
예를 들어, 배열에서 특정 요소를 찾는 것은 순차 검색이므로 시간 복잡도가 O(n)입니다.
반면, 해시맵에서 요소를 찾는 것은 평균적으로 O(1)의 시간 복잡도를 갖습니다.
정렬 알고리즘의 시간 복잡도
| 정렬 알고리즘 | 최선의 경우 | 평균 경우 | 최악의 경우 |
| 버블 정렬 | O(n) | O(n^2) | O(n^2) |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n^2) |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) |
자료구조의 시간 복잡도
| 자료구조 | 삽입 | 삭제 | 탐색 | 접근 |
| 배열 | O(n) | O(n) | O(n) | O(1) |
| 연결 리스트 | O(1) | O(1) | O(n) | O(n) |
| 스택 | O(1) | O(1) | O(n) | O(n) |
| 큐 | O(1) | O(1) | O(n) | O(n) |
| 해시 테이블 | O(1) | O(1) | O(1) | N/A |
| 이진 탐색 트리 | O(log n) | O(log n) | O(log n) | O(n) |
| 힙 | O(log n) | O(log n) | O(n) | O(n) |
시간 복잡도의 쉬운 예시
예시 1: 배열 검색
- 배열에서 원하는 숫자를 찾는다고 생각해보세요. 배열의 크기가 n일 때,
모든 숫자를 하나씩 확인하는 경우 최악의 시간 복잡도는 O(n)입니다.
이는 배열이 클수록 시간이 더 많이 걸린다는 뜻입니다.
예시 2: 버블 정렬
- 친구들의 키 순서대로 줄을 세우는 것을 버블 정렬이라고 생각해보세요.
키가 더 큰 친구를 뒤로 보내는 작업을 여러 번 반복합니다.
친구가 n명이라면, 최악의 경우 n * (n-1) / 2번 비교해야 합니다.
시간 복잡도는 O(n^2)입니다.
예시 3: 해시 테이블
- 학교에 있는 모든 학생의 이름을 빠르게 찾고 싶다면,
해시 테이블을 사용할 수 있습니다.
해시 테이블은 각 학생의 이름을 키로 사용해서 그 이름이 저장된 위치를 바로 알 수 있게 해줍니다.
검색, 삽입, 삭제 모두 평균적으로 O(1)의 시간 복잡도를 갖게 됩니다.
결국 궁극적으로 계속해서 시간복잡도에 맞는 자료구조나 정렬 알고리즘을 활용하여
개발하는것이 제가 원하는 일이죠~!
웹에서 시간 복잡도를 줄일 수 있는 방법
1. 캐싱
- Spring Boot에서는 캐싱을 통해 데이터베이스 접근을 줄이고 시간 복잡도를 낮출 수 있습니다. 예를 들어, @Cacheable 어노테이션을 사용해서 자주 조회하는 데이터를 메모리에 저장하고 빠르게 접근할 수 있습니다.
- 실제로 코드를 짤때 @Cacheable은 어디에서도 쓰이지 않았으며, 한번도 사용해본적은 없습니다.
하지만 시간복잡도를 낮출수 있다고 하니,,, 적절한 상황이 뭐가 있는지 고민을 해보겠습니다.
2. 데이터베이스 인덱싱
- 데이터베이스에서 인덱스를 사용하면 검색 시간을 줄일 수 있습니다.
Spring Data JPA에서는 @Indexed 어노테이션을 사용해 인덱스를 쉽게 추가할 수 있습니다.
이는 데이터 검색 시간 복잡도를 O(log n)으로 낮춰줍니다. - 저는 mybatis를 사용했으므로, 실제 xml에 쿼리문을 작성하고 데이터베이스 설계시에
테이블에 적절한 인덱스를 활용하여, 큰 데이터를 검색할 때에 유용하게 쓰였습니다.
3. 스트림 API
- 자바 스트림 API를 사용하면 컬렉션의 데이터를 효율적으로 처리할 수 있습니다.
예를 들어, 병렬 스트림(parallelStream())을 사용하면 대용량 데이터를 병렬로 처리하여
시간을 단축할 수 있습니다.
이는 멀티코어 프로세서를 활용하여 처리 시간을 O(n/k)로 낮출 수 있습니다.
여기서 k는 코어의 개수입니다.
이렇게 시간 복잡도를 이해하고, 효율적인 알고리즘과 자료구조를 사용하면 웹 애플리케이션의 성능을 크게 향상시킬 수 있습니다.
저도 이제 배우는 단계라고 생각을 하기 때문에,
현재는 백엔드 개발 1년차의 기록이지만,
앞으로 알고리즘 공부를 통해 더 효율적이고 빠른 백엔드 웹 개발자가 되기를 기대합니다.
꾸준히 포스팅하며 성장하는 과정을 공유할 테니, 많은 관심과 응원 부탁드립니다!
'주니어 기초 코딩공부 > 알고리즘에 대하여' 카테고리의 다른 글
| [part1] 웹 로딩 시간 복잡도를 줄이기 위해서 무엇을 할 수 있을까? (1) | 2024.08.16 |
|---|---|
| [자주 쓰는 알고리즘 문법 정리] Stack, Queue, Collection Binary Search (73) | 2024.08.07 |