개발자는 기록이 답이다

알고리즘 할때 ArrayList를 자주 썼는데, 내부적으로는 어떻게 동작하는지 알아보기 위해 해당 포스팅을 작성해보려고 한다. ArrayList란? Java의 동적 배열인 ArrayList는 내부적으로 배열을 기반으로 하는 자료 구조이다. 크기를 동적으로 조절 가능하여 원소의 추가와 삭제가 용이하며, 랜덤 액세스에 강점을 가지고 있다. 중간에 원소를 추가하거나 삭제할 때는 다른 원소들을 이동시켜야 하므로 성능 저하가 있을 수 있다. 크기 조절은 현재 크기의 1.5 배로 확장하는 방식을 사용한다. 특히 동적인 데이터 크기 및 빈번한 원소 조작이 필요한 상황에서 적합한 자료구조이다. ArrayList의 동적 크기 확장의 메커니즘 ArrayList의 동적 크기 확장은 내부적으로 배열을 사용하며, 배열이 가득 ..

4. Least Recently Used 예시 입력 1 5 9 1 2 3 2 6 2 3 5 7 예시 출력 1 7 5 3 2 6 각 문제 풀이에 대한 설명은 주석으로 달아놓음. list로 풀수도 있지만, 왠만하면 정렬로 푸는 연습을 해라. 왜냐하면 코드 구현력이 어느정도인지 확인하기 위함이다. 문제에 대한 이해도가 중요했음,, 내가 푼 풀이 1 (ArrayList) - Time: 164ms Memory: 27MB import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class ListExample { public int[] solution(int size, int n, int[] arr) { int[] an..

13. 경로탐색(인접리스트, ArrayList) 예시 입력 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 예시 출력 1 6 정점이 1000개 10000개로 들어온다면 인접행렬로는 비효율적이다. 왜냐하면 정점이 5라고하고 5행 5열로 잡으면 된다. 1번 정점에서 갈 수 있는 정점이 어디인지 탐색하는데, 100개 정도까지는 괜찮지만 1000개 10000개라고 하면 인접행렬이라는 그래프로 할때 10000x10000을 해야해서 메모리를 크게 잡습니다. 그리고 1번 정점에서 갈 수 있는걸 찾으려면 1부터 10000까지 for문을 다 돌아야 합니다. 메모리랑 시간복잡도 면에서 너무 비효율적입니다. 그래서 이럴때 인접리스트를 사용합니다. N이 5라고 가정했을때, 1번 리스트부터 5번 리스..