ArrayList가 가변배열이라는 건 알겠는데 한 번 늘 때 얼마나 늘어날까? 궁금해서 알아보았습니다. ArrayList 평소 알고리즘을 풀거나 비즈니스 로직을 개발하다보면 List 인터페이스를 구현한 ArrayList 혹은 LinkedList 클래스를 사용할 때가 많았습니다. 오늘은 문득 ArrayList.add() 라는 메서드를 수행하면 내부적으로 어떤 일들이 일어나는지, 배열 길이를 넘는 데이터를 저장할 때 어떤식으로 가변 동작이 일어나는지 궁금해서 클래스 내부를 한번 들여다보았고 한번 정리해보았습니다. ArrayList Concept 순서가 있는 데이터의 집합으로 ArrayList는 내부적으로 배열을 사용하여 데이터를 연속적으로 저장합니다. 또한 내부가 배열로 이루어져있다보니 길이를 넘어서는 데이..

문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 누적합 및 자료구조를 활용한 풀이 접근법 A수열과 B수열에서 나올 수 있는 모든 부 배열을 누적합을 활용하여 구함 Map 자료구조를 활용하여 해당 누적합 값이 기존에 들어가있다면 value증가, 없다면 put A의 부 배열 개수만큼 반복문을 돌면서 목표값 T - A[i](부 배열 원소) 값이 B 부 배열 M..

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 Dijkstra를 활용한 풀이 접근법 조건 - 첫번째 컴퓨터는 슈퍼컴퓨터로써 반드시 복구해야합니다. - 슈퍼 컴퓨터로부터 나머지 N-1개의 컴퓨터까지 최단 경로로 통신이 가능해야합니다. - 양방향 그래프 풀이 간단한 데이크스트라를 통해 슈퍼 컴퓨터를 시작노드로 나머지 노드까지의 최단경로를 우선순위 큐를 통해 탐색. 탐색하는 과정에서 방문체크를 같이 진행. 이전..

문제 https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 풀이 그리디 방식을 활용한 풀이 접근법 전처리 입력이 거리순으로 들어오지 않을 수 있으니 거리를 기준으로 정렬 조건 각 사람까지의 거리의 합 마을이 없는 위치에 우체국을 세울 수 없음 마을 위치, 인구 수 입력의 범위는 최대 1,000,000,000 마을 거리의 합이 아니라 각 사람까지의 거리의 합이 최소가 되..